8.23总结

wangxiaoyi1118 · 2025-08-23 16:20:00 · 个人记录

T6

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[5050][5050],ans=1,dx[4]={1, -1, 0, 0},dy[4]={0, 0, 1, -1},vis[5050][5050],cnt, color;
void dfs(int x, int y) 
{
    for (int i=0;i<4;i++) 
    {
        int p=x+dx[i],q=y+dy[i];
        if (p<1||p>n||q<1||q>m||vis[p][q]==color||a[p][q]==1) //判定 
        {
            continue;
        }
        vis[p][q]=color;//染色 
        cnt++;//结果加一 
        if (a[p][q]==2) 
        {
            continue;
        }
        dfs(p, q);
    }
}

int main() 
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) 
    {
        for (int j=1;j<=m;j++) 
        {
            char c;
            cin>>c;
            if (c=='#') //当前位置是障碍 
            {
                a[i][j]=1;
            }
            else 
            a[i][j]=0;
        }
    }
    for (int i=1;i<=n;i++) 
    {
        for (int j=1;j<=m;j++) 
        {
            if (a[i][j]==1) 
            {
                continue;
            }
            if(a[i-1][j]==1||a[i+1][j]==1||a[i][j-1]==1||a[i][j+1]==1) //不能动的位置 
            {
                a[i][j]=2;
            }
        }
    }

    for (int i=1;i<=n;i++) 
    {
        for (int j=1;j<=m;j++) 
        {
            if(vis[i][j]==0&&a[i][j]==0) 
            {
                cnt=1;
                color++;
                vis[i][j]=color;//启点染色 
                dfs(i,j);
                ans=max(ans, cnt);
            }
        }
    }
    cout<<ans;
    return 0;
}