题目描述

 

　　有一个仅由数字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了。