题目https://www.luogu.org/problemnew/show/P1141
这个题解主要针对我个人出现的一些问题和注意的地方。
解题思路
首先说一下联通块
联通块这个比较抽象，举个例子就是假设一条鱼在一个池塘里游泳，那么在时间不限的情况下，小鱼会游过池塘的所有位置，而这个与小鱼的出发点是无关的。
所以在本题中，假设从一个坐标开始，对他能经过的所有点进行标记，那么在剩下的询问中，如果询问的坐标已经被标记，那么它所经过的点与假设的坐标是相同的，所以就可以创建一个统计格子数目的数组cnt和一个联通图int数组_map与迷宫的坐标一一对应，假设第i次询问可以经过n个点，那么就把这个联通图所有经过的点赋值为i，并赋值cnt[i]=经过的格子数。在剩下的询问中，如果已经被标记，则直接输出_map对应的i所对应的cnt数组的值。
我本人出现的错误（一直不知道哪里错了，看了很长时间才反应过来）
一开始并没有使用_map作为联通图，而是直接在原迷宫内修改，但是在询问过多的情况下，两位数的值就不能赋值在一个位置中（当时不知道为什么这么写，有点懵），所以在情况超过9次之后就会出错。具体怎么个情况就是代码中注释的部分。
说明：
我的bfs可能比较复杂，个人习惯，但是觉得理解起来还是比较方便。
完整代码
#include <iostream>
#include<deque>
#include<queue>
#include<stdio.h>
#define CHECK(x, y) (x<wx && x>=0 && y >=0 && y<hy)
using namespace std;
int dir[][]={{-,},{,},{,-},{,}};
char room[][];
int wx,hy,num,cnt[],way;
int _map[][];
struct node {int x,y;};
int bfs(int dx,int dy)
{
num=;
queue<node> q;
node start,next;
start.x=dx;
start.y=dy;
q.push(start);
while(!q.empty())
{
start=q.front();
q.pop();
if(room[start.x][start.y]==''||room[start.x][start.y]=='#')
{
//room[start.x][start.y]='0'+way;
room[start.x][start.y]='*';
_map[start.x][start.y]=way;
for(int i=;i<;i++)
{
next.x=start.x+dir[i][];
next.y=start.y+dir[i][];
//cout<<next.x<<" "<<next.y<<endl;
if(CHECK(next.x,next.y)&&room[next.x][next.y]=='')
{
num++;
room[next.x][next.y]='.';
q.push(next);
}
}
}
else if(room[start.x][start.y]==''||room[start.x][start.y]=='.')
{
//room[start.x][start.y]='0'+way;
room[start.x][start.y]='*';
_map[start.x][start.y]=way;
for(int i=;i<;i++)
{
next.x=start.x+dir[i][];
next.y=start.y+dir[i][];
//cout<<next.x<<" "<<next.y<<endl;
if(CHECK(next.x,next.y)&&room[next.x][next.y]=='')
{
num++;
room[next.x][next.y]='#';
q.push(next);
}
}
}
//cout<<"size="<<q.size()<<" "<<num<<endl;
}
return num;
}
int main()
{
int n,m,dx,dy;
cin>>n>>m;
wx=hy=n;
for(int i=;i<n;i++)
cin>>room[i];
for(way=;way<=m+;way++)
{
cin>>dx>>dy;
dx=dx-;
dy=dy-;
if(room[dx][dy]==''||room[dx][dy]=='')
cnt[way]=bfs(dx,dy);
//cout<<cnt[room[dx][dy]-'0'];
printf("%d\n",cnt[_map[dx][dy]]);
//for(int i=0;i<n;i++)
//cout<<room[i]<<endl;
}
return ;
}