题解 CF377A 【Maze】

· · 题解

CF377A Maze

主要算法:bfs

思路:可以先把所有空地都设为新建的墙壁,再通过bfs恢复为空地.

详细方法

首先建立一个结构体 node 来储存bfs过程中的每个点的坐标:

struct node
{
    int x,y;//坐标
}st;//搜索起点,后面会用到

提到起点,有些人可能会问了,这个题没有指定起点,以哪里作为起点好呢?

嘿嘿,其实哪个点都行.因为此题没有唯一的答案,不用多虑.

同时,我们需要记录读入的地图中有多少空地,就是下面代码中的 \_cnt 变量.

这样,我们在读入每个点的时候就能完成这项工作:

    for(int i=1;i<=n;i++)//循环读入地图
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
            if(c[i][j]=='.')//如果这是空地
            {
                c[i][j]='X';//先标记为新建的墙壁
                stx=i;
                sty=j;//标记为起点(随便哪个都行)
                _cnt++;//记录空地数
            }
        }
    }
    _cnt-=k;//减去k就是应该将新建墙壁恢复为空地的个数

然后通过bfs遍历整个图,将访问的合法点由新建墙壁恢复为空地.

需要注意的是,我们只需要将 \_cnt 个新建墙壁恢复为空地,所以bfs的过程中也要建立一个变量 cnt 来记录恢复为空地的个数.如果恢复得够了就直接结束bfs:

            if(_cnt<=cnt)//这样表示恢复够了
            {
                return;
            }

bfs结束后,将最后的地图输出就可以了.

更多注释详见以下代码:

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;//坐标
}st;//搜索起点
queue<node>q;//bfs要用的队列
char c[505][505];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//两个数组一起用就可以表示4个方向
int n,m,k,cnt=0,_cnt=0,stx,sty;
void bfs(int sx,int sy)//bfs
{
    c[sx][sy]='.';//先把起点标为空地
    st=(node){sx,sy};
    q.push(st);//起点入队
    cnt++;//起点变为空地,cnt就要自增一次,不能漏
    while(!q.empty())//只要队列不为空就一直循环
    {
        node ff=q.front();//取队头
        q.pop();
        int fx=ff.x,fy=ff.y;//记录当前的坐标
        for(int i=0;i<4;i++)//枚举4个方向
        {
            int xx=fx+dx[i],yy=fy+dy[i];//当前方向下的新坐标
            if(_cnt<=cnt)//这样就表示恢复够了
            {
                return;//直接结束
            }
            if(xx<1||yy<1||xx>n||yy>m||c[xx][yy]!='X')//不能出地图边界,也不能访问原先是墙或已经访问过的点(即已经恢复为空地的点)
            {
                continue;//尝试下一个方向
            }
            //到这里就是合法访问
            node gg=(node){xx,yy};
            q.push(gg);//将合法新点入队
            c[xx][yy]='.';//恢复为空地
            cnt++;//cnt自增
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)//循环读入地图
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
            if(c[i][j]=='.')//如果这是空地
            {
                c[i][j]='X';//先标记为新建的墙壁
                stx=i;
                sty=j;//标记为起点(随便哪个都行)
                _cnt++;//记录空地数
            }
        }
    }
    _cnt-=k;//减去k就是应该将新建墙壁恢复为空地的个数
    bfs(stx,sty);//调用bfs算法
    //接下来就可以输出整个地图了
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%c",c[i][j]);
        }
        printf("\n");//输出千万条,格式第一条.换行不规范,爆零两行泪.
    }
    return 0;
}

希望大家能听懂!

篇末彩蛋