01迷宫题解（bfs，联通块）

题目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[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char room[1001][1001];
int wx,hy,num,cnt[1000001],way;
int _map[1001][1001];
struct node {int x,y;};
int bfs(int dx,int dy)
{
    num=1;
    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]=='1'||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=0;i<4;i++)
        {
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            //cout<<next.x<<" "<<next.y<<endl;
            if(check(next.x,next.y)&&room[next.x][next.y]=='0')
            {
                num++;
                room[next.x][next.y]='.';
                q.push(next);
            }
        }
        }
        else if(room[start.x][start.y]=='0'||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=0;i<4;i++)
        {
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            //cout<<next.x<<" "<<next.y<<endl;
            if(check(next.x,next.y)&&room[next.x][next.y]=='1')
            {
                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=0;i<n;i++)
        cin>>room[i];
for(way=2;way<=m+1;way++)
{
    cin>>dx>>dy;
    dx=dx-1;
    dy=dy-1;
    if(room[dx][dy]=='0'||room[dx][dy]=='1')
        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 0;
}