题目描述
有一个仅由数字00与11组成的n\timesnn×n格迷宫。若你位于一格0上，那么你可以移动到相邻44格中的某一格11上，同样若你位于一格1上，那么你可以移动到相邻44格中的某一格00上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式
第11行为两个正整数n,mn,m。
下面nn行，每行nn个字符，字符只可能是00或者11，字符之间没有空格。
接下来mm行，每行22个用空格分隔的正整数i,ji,j，对应了迷宫中第ii行第jj列的一个格子，询问从这一格开始能移动到多少格。
输出格式
mm行，对于每个询问输出相应答案。
输入输出样例
输入#1复制
22
01
10
11
22
输出#1复制
4
4
说明/提示
所有格子互相可达。
对于20\%20%的数据，n≤10n≤10；
对于40\%40%的数据，n≤50n≤50；
对于50\%50%的数据，m≤5m≤5；
对于60\%60%的数据，n≤100,m≤100n≤100,m≤100；
对于100\%100%的数据，n≤1000,m≤100000n≤1000,m≤100000。
题解
先介绍采用裸的BFS，当然不能满分。再介绍如何优化得到满分。
1#include<iostream>
2#include<stdio.h>
3#include<math.h>
4#include<algorithm>
5#include<string.h>
6
7usingnamespacestd;
8
9structNode
10{
11intx,y;
12};
13Nodeq[1000005];
14
15constintMAXN=1005;
16intn,m,a,b,c,d,front,last,step;
17intpos[4][2]={0,1,0,-1,1,0,-1,0};
18charabc[MAXN][MAXN];//存储输入的矩阵信息
19boolvis[MAXN][MAXN];//是否已经遍历过该点
20
21
22voidbfs()
23{
24Nodenow;
25now.x=a;
26now.y=b;
27vis[a][b]=1;
28
29front=last=0;
30q[last]=now;
31last++;
32while(front<last)
33{
34now=q[front++];
35for(inti=0;i<4;i++)
36{
37intnx=now.x+pos[i][0];
38intny=now.y+pos[i][1];
39if(nx<=n&&nx>0&&ny<=n&&ny>0
40&&vis[nx][ny]==false
41&&abc[now.x][now.y]!=abc[nx][ny])
42{
43vis[nx][ny]=true;
44q[last].x=nx;
45q[last].y=ny;
46step++;
47last++;
48}
49}
50}
51}
52
53intmain()
54{
55cin>>n>>m;
56for(inti=1;i<=n;i++)
57{
58for(intj=1;j<=n;j++)
59{
60cin>>abc[i][j];
61}
62}
63for(inti=1;i<=m;i++)
64{
65cin>>a>>b;
66step=1;
67bfs();
68cout<<step<<endl;
69memset(vis,0,sizeof(vis));
70}
71return0;
72}
裸的BFS并没有什么技巧，只是注意q队列不要太小，太小会导致WA。这个代码会有3个测试点TLE。
之所以会出现TLE，主要是有很多次询问，每次询问都做了一次BFS，要优化代码就要减少BFS的次数。注意到这样一个事实：如果迷宫中存在连通块，则连通块中各格子到其他格子的个数是相同的。而求连通块本身就是利用BFS实现的。下面就是利用连通块进行优化的代码。
1#include<iostream>
2#include<stdio.h>
3#include<math.h>
4#include<algorithm>
5#include<string.h>
6
7usingnamespacestd;
8
9structNode
10{
11intx,y;
12};
13Nodeq[1000005];
14intcnt[1000005];
15
16constintMAXN=1005;
17intn,m,a,b,c,d,front,last,step,num;
18intpos[4][2]={0,1,0,-1,1,0,-1,0};
19charabc[MAXN][MAXN];//存储输入的矩阵信息
20boolvis[MAXN][MAXN];//是否已经遍历过该点
21intmap[MAXN][MAXN];//用于对连通块染色
22
23
24voidbfs()
25{
26Nodenow,next;
27now.x=a;
28now.y=b;
29map[a][b]=num;
30vis[a][b]=1;
31step=1;
32
33front=last=0;
34q[last]=now;
35last++;
36while(front<last)
37{
38now=q[front++];
39for(inti=0;i<4;i++)
40{
41intnx=now.x+pos[i][0];
42intny=now.y+pos[i][1];
43if(nx<=n&&nx>0&&ny<=n&&ny>0
44&&vis[nx][ny]==false
45&&abc[now.x][now.y]!=abc[nx][ny])
46{
47vis[nx][ny]=true;
48q[last].x=nx;
49q[last].y=ny;
50map[nx][ny]=num;
51step++;
52last++;
53}
54}
55}
56cnt[num]=step;
57num++;
58}
59
60intmain()
61{
62cin>>n>>m;
63for(inti=1;i<=n;i++)
64{
65for(intj=1;j<=n;j++)
66{
67cin>>abc[i][j];
68}
69}
70num=1;
71for(inti=1;i<=m;i++)
72{
73cin>>a>>b;
74if(map[a][b]==0)
75{
76bfs();
77}
78cout<<cnt[map[a][b]]<<endl;
79}
80return0;
81}
其中的map数组是用来存储连通块的染色信息的。如果格子对应的map数据为0，说明没有做过BFS。cnt数组存储着每个连通块所对应的格子个数。经过这次优化，就可以AC了。
如需转载，请注明文章出处和来源网址：