题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入输出格式
输入格式：
第1行为两个正整数n,m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式：
m行，对于每个询问输出相应答案。
输入输出样例
输入样例#1：2 2 01 10 1 1 2 2输出样例#1：
4 4
说明
所有格子互相可达。
对于20%的数据，n≤10；
对于40%的数据，n≤50；
对于50%的数据，m≤5；
对于60%的数据，n≤100,m≤100；
对于100%的数据，n≤1000,m≤100000。
解题思路:
很容易想到用bfs暴力模拟解决此题
代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m,ans,p,o;
4 char lk;
5 bool a[1005][1005],vis[1005][1005];//vis数组表示某个点走过没有
6 queue<int > q,q1;//q储存行号,q1储存列号
7 void bfs(int x,int y) {
8 memset(vis,0,sizeof(vis));//初始化
9 while(!q.empty() || !q1.empty()) {//保证队列为空
10 q.pop();
11 q1.pop();
12 }
13 ans = 1;
14 q.push(x);q1.push(y);
15 vis[x][y] = 1;
16 while(!q.empty()) {
17 int w = q.front(); int e = q1.front();
18 q.pop();q1.pop();
19 if(a[w][e]) {//如果这点为1
20 if(!a[w+1][e] && w+1 <= n && !vis[w+1][e]) {
21 ans++;
22 q.push(w+1);q1.push(e);
23 vis[w+1][e] = 1;
24 }
25 if(!a[w-1][e] && w-1 >= 1 && !vis[w-1][e]) {
26 ans++;
27 q.push(w-1);q1.push(e);
28 vis[w-1][e] = 1;
29 }
30 if(!a[w][e+1] && e+1 <= n && !vis[w][e+1]) {
31 ans++;
32 q.push(w);q1.push(e+1);
33 vis[w][e+1] = 1;
34 }
35 if(!a[w][e-1] && e-1 >= 1 && !vis[w][e-1]) {
36 ans++;
37 q.push(w);q1.push(e-1);
38 vis[w][e-1] = 1;
39 }
40 }
41 else {//如果这点为0
42 if(a[w+1][e] && w+1 <= n && !vis[w+1][e]) {
43 ans++;
44 q.push(w+1);q1.push(e);
45 vis[w+1][e] = 1;
46 }
47 if(a[w-1][e] && w-1 >= 1 && !vis[w-1][e]) {
48 ans++;
49 q.push(w-1);q1.push(e);
50 vis[w-1][e] = 1;
51 }
52 if(a[w][e+1] && e+1 <= n && !vis[w][e+1]) {
53 ans++;
54 q.push(w);q1.push(e+1);
55 vis[w][e+1] = 1;
56 }
57 if(a[w][e-1] && e-1 >= 1 && !vis[w][e-1]) {
58 ans++;
59 q.push(w);q1.push(e-1);
60 vis[w][e-1] = 1;
61 }
62 }
63 }
64 return ;
65 }
66 int main()
67 {
68 cin >> n >> m;
69 for(int i = 1; i <= n; i++) {//存图
70 for(int x = 1; x <= n; x++) {
71 cin >> lk;
72 if(lk == '0') a[i][x] = 0;
73 else a[i][x] = 1;
74 }
75 }
76 for(int i = 1; i <= m; i++) {//暴力找答案
77 cin >> p >> o;
78 bfs(p,o);
79 cout << ans <<endl;
80 }
81 return 0;
82 }
但是,我们会发现暴力会TLE三个点,那么我们就要想到优化.
很容易就可以发现，所有连接在一起的格子的答案是一样的。
所以，只需要用DFS找到所有的联通块，联通块内所有的格子的答案都是这个联通块的格子数目。
AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m,p,o,d,lef,righ,sum,xx,yy;
4 int vis[1005][1005],ans[1000001];//vis数组保存各个点所在的连通图，以及是否已经处理过，ans数组保存各个连通图的大小
5 bool a[1005][1005];
6 int dx[4]={0,0,-1,1};
7 int dy[4]={1,-1,0,0};//四个方向
8 char lk;
9 struct kkk{
10 int x,y;
11 }e[1000005];
12 int main()
13 {
14 cin >> n >> m;
15 for(int i = 1; i <= n; i++) //存图
16 for(int x = 1; x <= n; x++) {
17 cin >> lk;
18 a[i][x] = lk - 48;
19 }
20 for(int i = 1; i <= n; i++) {
21 for(int j = 1; j <= n; j++) {
22 if(vis[i][j] == 0) {//如果当前位置不在已知连通图中（还未处理过）
23 d++;//d用来保存当前是在第几个连通图中
24 lef = 1;
25 righ = 1;
26 e[1].x = i;
27 e[1].y = j;
28 vis[i][j] = d;
29 sum = 1;
30 while(lef <= righ) {
31 for(int o = 0; o <= 3; o++) {
32 xx = dx[o] + e[lef].x;
33 yy = dy[o] + e[lef].y;
34 if(xx <= n && xx >= 1 && yy <= n && yy >= 1 && vis[xx][yy] == 0) //判断这个位置是否在地图上
35 if((a[e[lef].x][e[lef].y] == 1 && a[xx][yy] == 0) || (a[e[lef].x][e[lef].y] == 0 && a[xx][yy] == 1)) {//判断这个位置是否能走
36 righ++;
37 sum++;
38 vis[xx][yy] = d;//这个位置在第d个联通块中
39 e[righ].x = xx;
40 e[righ].y = yy;//更新位置
41 }
42 }
43 lef++;
44 }
45 ans[d] = sum;//第d个联通块答案为sum
46 }
47
48 }
49 }
50 for(int i = 1; i <= m; i++) {
51 cin >> p >> o;
52 cout << ans[vis[p][o]] <<endl;//输出答案
53 }
54 return 0;
55 }