题目传送们

题目大意：
给定一个n*m的图，每个点是”.”和”#”中的一种。
如果到达某个点后，该点的四联通中有”#”就不能再移动。
移动方法为去到任意一个四联通的点
问这张图上，能够到达最多点的点能到达多少个点

样例：

in:
3 5
.#...
.....
.#..#

out:
9

思路：
考虑到如果到达”#”周围的点之后就不能继续移动，所以可以大致划分一下边界，现在题目就变成了求最大连通块的大小了
只不过大小的定义稍有不同，是按四联通走”.”能到达的点数（含起点）以及不跨越”@”能走到的”@”数（”@”为”#”周围的格子）
然后就可以无脑dfs了

但是，如果你不会dfs的话也可以这样写

 #include<iostream>
using namespace std;
int n,m;
const int N=1005;
char mp[N][N];
int k;
int vis[N][N];
const int wy[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int que_x[N*N],que_y[N*N];
int top;
int tot;
int jl_x[N*N],jl_y[N*N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>mp[i][j];
        }
    }
    int w=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(mp[i][j]=='#'){//标记"@",注意不要把"#"覆盖了
                ++w;
                if(mp[i-1][j]!='#') mp[i-1][j]='@';
                if(mp[i+1][j]!='#') mp[i+1][j]='@';
                if(mp[i][j-1]!='#') mp[i][j-1]='@';
                if(mp[i][j+1]!='#') mp[i][j+1]='@';
            }
        }
    }
    int dmax=min(1,n*m-w);
    /*
    这个地方是这样的：
    因为我们后面没考虑"@"的连通块大小（大小为1）
    所以这个地方直接把目前的最大值设为1
    但是考虑到可能会全是"#"，所以简单判断一下
    */
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(mp[i][j]=='#'||mp[i][j]=='@'){
                continue;
            }
            if(vis[i][j]==1) continue;
            k=1;
            top=0;
            vis[i][j]=1;
            que_x[++top]=i;
            que_y[top]=j;
            //找到一个可以作为起点的点，开始计算连通块大小
            while(top){
                int x=que_x[top],y=que_y[top];
                --top;
                for(int i=0;i<4;++i){//按照四联通的方法走
                    int jx=x+wy[i][0],jy=y+wy[i][1];
                    if(jx<1||jx>n||jy<1||jy>m) continue;//判断出界
                    if(mp[jx][jy]=='@'&&vis[jx][jy]==0){//判断边界
                        ++k;
                        vis[jx][jy]=1;
                        jl_x[++tot]=jx;
                        jl_y[tot]=jy;
                        continue;
                    }
                    else if(mp[jx][jy]=='.'&&vis[jx][jy]==0){
                        vis[jx][jy]=1;
                        ++k;
                        //找到的点可以继续走，所以记一下
                        que_x[++top]=jx;
                        que_y[top]=jy;
                    }
                    //vis数组保证不会重复经过同一个点，既保证了答案的正确性，又保证了时间复杂度的正确性
                }
            }
            dmax=max(dmax,k);
            while(tot!=0){//注意：这里只需要把"@"的vis还原，因为只有"@"还会被走到
                int x=jl_x[tot],y=jl_y[tot];
                vis[x][y]=0;
                --tot;
            }
            //因为标记了"@"所以在同一个连通块里的点可以互相到达，就节约很多时间
        }
    }
    cout<<dmax<<endl;
    return 0;
}