题目描述
有一个仅由数字 0 与 1 组成的n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式
有一个仅由数字 0 与 1组成的n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输出格式
m 行，对于每个询问输出相应答案。
输入输出样例
输入
2 2
01
10
1 1
2 2
输出
4
4
说明/提示
所有格子互相可达。
对于 20% 的数据，n≤10；
对于 40% 的数据，n≤50；
对于50% 的数据，m≤5；
对于60% 的数据，n,m≤100；
对于 100% 的数据,n≤1000,m≤100000。
#include<bits/stdc++.h> using namespace std; const int M=1010; int n,m; int vis[M][M]; bool mp[M][M]; int xx[]={0,1,-1,0}; int yy[]={1,0,0,-1}; int color,cnt,ans[1000010]; void bfs(int x,int y) { queue<int>h; queue<int>l; h.push(x); l.push(y); vis[x][y]=color; while(!l.empty()) { for(int i=0;i<4;i++) { int dx=h.front()+xx[i]; int dy=l.front()+yy[i]; if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&!vis[dx][dy]&&mp[dx][dy]!=mp[h.front()][l.front()]) { h.push(dx); l.push(dy); vis[dx][dy]=color; } } h.pop(); l.pop(); cnt++; } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { char x; cin>>x; if(x=='1') mp[i][j]=1; else mp[i][j]=0; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(!vis[i][j]) { color++; bfs(i,j); ans[color]=cnt; cnt=0; } } } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; cout<<ans[vis[x][y]]<<endl; } return 0; }
