P2864题解

· · 题解

基本思路

bfs的应用范围是找从一个点到另一个点的最短距离，但题目是要从起点绕一圈再回去，所以正好矛盾，所以题有问题，但是，只要在别处选一个点并放个墙，就像下面的图一样：

可以看到计算机就会去绕远道，既然找出了远道的最短路线，再找出到墙下面的最短路线，他俩加起来那不就是最短的路径了吗？

细节处理

关于墙放在哪里：

我个人觉得放在最下面或者最上面树的旁边就好，就像下面这张图片：

可以看到我把墙放在了最下面树的右边，而墙的上面的三个点是我们要比较的较远的路线的步数的点（就是选上面三个点里面步数最小的），而墙的下方是要比较的较近的路线的步数的点（也就是选下面三个点里面最小的），从图中可以看到，从上面点到下面的点一定是要走两步才能链接起来的，所以最后输出的时候要把两条线路较小的加起来再加上个2。

关于queue队列(会的自行跳过)：

queue是c++独有的一个stl函数，用它来写bfs简直不要太简单，下面是关于此函数的一些用法：

定义：queue<数据类型>队列名

如：queue<int>q 定义了一个名为q的int类型的队列

q.back() 返回最后一个元素

q.empty() 如果队列空则返回真

q.front() 返回第一个元素

q.pop() 删除第一个元素

q.push() 在末尾加入一个元素

q.size() 返回队列中元素的个数

你问我头文件是什么？那当然是万能头#include<queue>

其实可以用结构体但我不会

关于0x3f3f3f

这个东西就是一个无穷大的值，一开始我用的0，然后全爆空间了。。

代码实现

代码中的墙是放在了最后一颗树的下面，因为比较好处理

数据比较水，这是不特判起点会被墙覆盖，ac代码

#include<bits/stdc++.h> 
using namespace std;
int m,n,ax,ay,bx,by,dis[51][51];//dis是用来存贮步数的 
int dx[8]={0,0,1,-1,1,1,-1,-1};//控制向八个方向移动 
int dy[8]={1,-1,0,0,1,-1,1,-1};
char a[51][51];//存储输入的地图 
void bfs(int x,int y,int z)//此函数用来计算步数 
{
    queue<int>xx;//定义三个数列存横纵坐标和步数 
    queue<int>yy;
    queue<int>zz;
    memset(dis,0x3f3f3f3f,sizeof(dis));//给dis数组都赋一个值，0x3f3f3f3f是一个无穷大的数 
    xx.push(x);//把各项初值给相应的队列 
    yy.push(y);
    zz.push(z);
    dis[x][y]=0;//把起点的步数的值赋上0；因为前面赋了一个无穷大的值 
    while(!xx.empty())//只要队列不空就一直循环 
    {
        int xxx=xx.front();//把最上面的横纵坐标和步数取出来 
        int yyy=yy.front();
        int zzz=zz.front();
        xx.pop();yy.pop();zz.pop();//把刚刚取出来的去掉 
        for(int i=0;i<=7;i++)//从第一个方向开始一个一个走 
        {
            int tx=xxx+dx[i];//计算移动后的横纵坐标 
            int ty=yyy+dy[i];
            if(dis[tx][ty]!=0x3f3f3f3f) continue;//如果等于刚刚赋的值就往下进行循环，否则已经有了值，就直接跳过，开始下一次循环 
            if(a[tx][ty]=='X'||tx<0||ty<0||tx>m||ty>n||a[tx][ty]=='|') continue;//判断是否越界和是否是墙或者树，是就跳过，开始下一次循环 
            xx.push(tx);//把计算出的符合要求的横纵坐标放入队列 
            yy.push(ty);
            dis[tx][ty]=zzz+1;//计算到达此点所用的步数 
            zz.push(zzz+1);//把当前的步数放入zz数列(如果难理解就换成zz.push(dis[tx][ty])  ) 
        }
    }
    return ;//循环完了要退出 
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='*') ax=i,ay=j;//找到起点（终点）位置 
            if(a[i][j]=='X') bx=i,by=j;//这个主要是找到最后一颗树的位置 
        }
    }
    bx++;//不加一就下面i=bx+1，墙不能建在树上 
    for(int i=bx;i<=m;i++) a[i][by]='|';//建好墙 
    bfs(ax,ay,0);//开始搜索 
    int k1=min(dis[bx-1][by-1],min(dis[bx][by-1],dis[bx+1][by-1]));//找出答案 
    int k2=min(dis[bx-1][by+1],min(dis[bx][by+1],dis[bx+1][by+1]));
    cout<<k1+k2+2<<endl;//输出 
    return 0;//好习惯 
}

下面是特判后的ac代码

#include<bits/stdc++.h>
using namespace std;
int m,n,ax,ay,bx,by,dis[51][51];
int dx[8]={0,0,1,-1,1,1,-1,-1};//控制向八个方向移动 
int dy[8]={1,-1,0,0,1,-1,1,-1};
char a[51][51];
bool flag=0;
void bfs(int x,int y,int z)
{
    queue<int>xx;
    queue<int>yy;
    queue<int>zz;
    memset(dis,0x3f3f3f3f,sizeof(dis));
    xx.push(x);
    yy.push(y);
    zz.push(z);
    dis[x][y]=0;
    while(!xx.empty())
    {
        int xxx=xx.front();
        int yyy=yy.front();
        int zzz=zz.front();
        xx.pop();yy.pop();zz.pop();
        for(int i=0;i<=7;i++)
        {
            int tx=xxx+dx[i];
            int ty=yyy+dy[i];
            if(dis[tx][ty]!=0x3f3f3f3f) continue;
            if(a[tx][ty]=='X'||tx<0||ty<0||tx>m||ty>n||a[tx][ty]=='|') continue;
            xx.push(tx);
            yy.push(ty);
            dis[tx][ty]=zzz+1;
            zz.push(zzz+1);
        }
    }
    return ;
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='*') ax=i,ay=j;
            if(a[i][j]=='X') bx=i,by=j;
        }
    }
    bx++;
    if(by==ay&&ax>bx)
    {
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            if(a[i][j]=='X'&&flag==0)
            {
                bx=i;
                by=j;
                flag=1;
                break;
            }
        bx--;
        for(int i=1;i<=bx;i++) a[i][by]='|';
    bfs(ax,ay,0);
    int k1=min(dis[bx-1][by-1],min(dis[bx][by-1],dis[bx+1][by-1]));
    int k2=min(dis[bx-1][by+1],min(dis[bx][by+1],dis[bx+1][by+1]));
    cout<<k1+k2+2<<endl;
    return 0;
    }
    for(int i=bx;i<=m;i++) a[i][by]='|';
    bfs(ax,ay,0);
    int k1=min(dis[bx-1][by-1],min(dis[bx][by-1],dis[bx+1][by-1]));
    int k2=min(dis[bx-1][by+1],min(dis[bx][by+1],dis[bx+1][by+1]));
    cout<<k1+k2+2<<endl;
    return 0;
}