1284: 01迷宫

http://tjuacm.chaosheng.top/problem.php?id=1284
https://www.luogu.com.cn/problem/P1141
下面这个是按tju的数据范围，AC。
这里用的还是bfs，但是dfs也可，因为是求最大能到达的数量。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 410; 

int n, m, cnt;
char matrix[N][N];
bool visit[N][N];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0}; 

struct pos{
    int x, y;
    //int cnt;
};

int bfs(int x, int y){
    memset(visit, false, sizeof(visit));
    queue<pos> q;
    pos f, v;
    f.x = x;
    f.y = y;
    cnt = 1;
    visit[f.x][f.y] = true;
    q.push(f);

    while(q.size()){
        f = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            v.x = f.x + dx[i];
            v.y = f.y + dy[i];
            //printf("v.x = %d v.y = %d\n", v.x, v.y);
            if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < n && !visit[v.x][v.y] && matrix[v.x][v.y] != matrix[f.x][f.y]) {
                visit[v.x][v.y] = true;
                cnt++;
                //v.cnt = f.cnt + 1;
                q.push(v);
            }
        }            
    }
}

int main(){
    string s;
    while(cin >> n >> m){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
            } 
        }

        int x, y;
        for(int i = 0; i < m; i++){
            cin >> x >> y;
            bfs(x-1, y-1);
            printf("%d\n", cnt);
        }
    }
    return 0;
}

而洛谷部分测试数据n达到1000，直接把N 改为1010，会超时。所以应该优化算法。
解法一： https://blog.csdn.net/weixin_43175029/article/details/90489425
这是对bfs的优化。里面提到连通的格子之间的答案是一样的，即求连通分量。在这里我们用fx[maxn][maxn]数组和fy[maxn][maxn]数组记录该格子的祖父（fx,fy），即该格子是从（fx,fy）通过BFS扩展来的，类似于并查集。ans[maxn][maxn]数组记录格子的答案。

解法二：
https://blog.csdn.net/weixin_33777877/article/details/93512673
https://blog.csdn.net/T13629119629/article/details/109402156
使用dfs