链接$ \to $P1141 01迷宫
吐槽
其实这题就是一道比较模板的BFS，只不过多了一个计数数组，一个记忆化，还有就是加了个状态~也不算难其实if里面多写点东西就是了~
核心逻辑解释
在这道题中，移动规则是：\(0 \to 1\) 或 \(1 \to 0\)。如果你从点 \(A\) 出发能走到点 \(B\)，那么根据规则，点 \(B\) 也一定能通过原路返回走到点 \(A\)。这意味着，所有能够互相到达的点组成了一个连通块（Connected Component）。在这个块里的任何一个点作为起点，它能遍历到的范围都是整个连通块。所以，当你用 BFS 跑完一次，数出了这个块里一共有 cnt 个格子时，这个块里所有的坐标对应的答案都应该是 cnt。这也就是那个BFS函数后面那个for循环的作用
具体的实现方法：
记忆化数组 mem：初始化为 -1。如果 bfs(x, y) 发现 mem[x][y] 不为 -1，说明这个点所在的连通块已经计算过了，直接返回答案。
连通块记录 visited：在 BFS 过程中，用一个容器（如 vector）记录下所有能走到的坐标。
结果同步：BFS 结束后，这个连通块里所有的点能到达的格子数都是一样的。所以我们遍历 visited，把所有这些坐标在 mem 里的值都设为 cnt。
访问标记 vis：配合 pos 变量使用。每次开启新的 BFS，pos++。若 vis[i][j] != pos，则表示在当前这轮搜索中该点未被访问
#include <bits/stdc++.h>
using namespace std ;#define int long long char a[1005][1005] ;
int vis[1005][1005] ;
int mem[1005][1005] ;
const int dir[4][2] = { {1,0},{0,1},{-1,0} ,{0,-1} } ;
int n, m ;int pos = 0 ;bool inmap(int x, int y)
{return x >= 0 && x < n && y >= 0 && y < n ;
}int bfs(int x, int y)
{if(mem[x][y] != -1) return mem[x][y];pos ++ ; vector<pair<int,int>> visited;queue<pair<int,int>> q;q.push({x, y});visited.push_back({x, y});vis[x][y] = pos; int cnt = 1;while(!q.empty()){int dx = q.front().first;int dy = q.front().second;q.pop();for(int i = 0; i < 4; i++){int indx = dx + dir[i][0];int indy = dy + dir[i][1];if(inmap(indx, indy) && vis[indx][indy] != pos) {if(a[dx][dy] != a[indx][indy]){vis[indx][indy] = pos;cnt++;visited.push_back({indx, indy});q.push({indx, indy});}}}}for(auto [xx, yy] : visited) {mem[xx][yy] = cnt;}return cnt;
}signed main()
{ios::sync_with_stdio(false), cin.tie(nullptr); cin >> n >> m ;memset(mem, -1, sizeof(mem));memset(vis, 0, sizeof(vis));for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> a[i][j] ;}}for(int i = 0; i < m; i++){int x, y;cin >> x >> y ;x--; y-- ;cout << bfs(x, y) << "\n" ;}return 0 ;
}
