题目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 ;

}

巴特西

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

题目https://www.luogu.org/problemnew/show/P1141

解题思路

首先说一下联通块

我本人出现的错误（一直不知道哪里错了，看了很长时间才反应过来）

说明：

完整代码

最新文章

热门文章