Luogu P1141 01迷宫（DFS联通块）

Luogu DFS 连通块

楼下都说这题是什么并查集什么的，其实DFS联通块就可以了，没有那么复杂，速度也快。
时间：216ms 单个点时间：68ms 空间：36MB
时间复杂度O(n^2)+O(m)

主要思路

很容易就可以发现，所有连接在一起的格子的答案是一样的。
所以，只需要用DFS找到所有的联通块，联通块内所有的格子的答案都是这个联通块的格子数目。

程序实现

记录每个格子是否被搜过（在某个连通块中）。
两重循环，如果这格没搜过就从这个格子开始搜。
每搜到一个格子当前答案加1，数组记录当前格子位置，每次都向4个方向的满足条件的格子扩展。
搜完一块后把数组记录的格子的答案赋成连通块总的格子数。
读入时有个小技巧，对于二维字符数组a，scanf("%s",a[i]+1)可以以1下标读入一行。
(gets,strlen等同理，如strlen(s+1)1下标字符串长度）

关键代码

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) if(!v[i][j]){ //枚举格子，没有访问过就DFS
        v[i][j]=true;                   //这格被访问
        now=0;                          //总数记为0
        dfs(i,j);                       //从这格开始搜索
        for(int i=1;i<=now;i++) f[ans[i][0]][ans[i][1]]=now; //依次赋值，重复使用并没有问题
    }

#define nx x+dx[i] //增量数组表示下一个的x
#define ny y+dy[i] //增量数组表示下一个的y
#define check(x,y) (x>0&&x<=n&&y>0&&y<=n) //越界检查
void dfs(int x,int y){
    now++; //记录答案
    ans[now][0]=x,ans[now][1]=y; //记录连通块的格子
    for(int i=0;i<4;i++){ //搜索下一格
        if(check(nx,ny)&&!v[nx][ny]&&a[x][y]!=a[nx][ny]){
            //越界、访问、颜色判断
            v[nx][ny]=true; //记录访问状态
            dfs(nx,ny);     //下一格
        }
    }
}

完整代码（快读+快输）

#include <stdio.h>
#include <ctype.h>
#define check(x,y) (x>0&&x<=n&&y>0&&y<=n)
#define nx (x+dx[i])
#define ny (y+dy[i]) 
char a[1005][1005]; int f[1005][1005]; bool v[1005][1005];
int n,m,dx[]={1,0,-1,0},dy[]={0,1,0,-1},now;
int ans[1000005][2],Count; //变量定义防止太长压了行
void dfs(int x,int y){
    now++;
    ans[now][0]=x,ans[now][1]=y;
    for(int i=0;i<4;i++){
        if(check(nx,ny)&&!v[nx][ny]&&a[x][y]!=a[nx][ny]){
            v[nx][ny]=true;
            dfs(nx,ny);
        }
    }
}
int res;
char ch;
inline int read(){
    res=0;
    while(isspace(ch=getchar()));
    do res=res*10+ch-'0'; while(isdigit(ch=getchar()));
    return res;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) if(!v[i][j]){
            v[i][j]=true;now=0;
            dfs(i,j);
            for(int i=1;i<=now;i++) f[ans[i][0]][ans[i][1]]=now; 
        }
    register int x,y;
    for(int i=1;i<=m;i++){
        x=read();y=read();
        write(f[x][y]);
        putchar('\n');
    }
    return 0;
}