CF877D 题解

· · 题解

思路讲解

本题是一道模板迷宫最短路线题的加强版，所以思路也就自然很明显了，本题应该使用广度优先搜索 BFS。

因为本题一次可以走 k 步以内，所以我们就只需要将 k 个新点一一进行判断合法性，然后将不出格且不是 # 的格子放到队列里就行了。其他的和模板 BFS 没什么区别了。

不过有一些容易使代码不 AC 的点：

  1. 如果往一个方向遍历从 1 步到 k 步究竟走多少步合法时，如果遇到一个出格，那么直接 break，因为再往后遍历也一定出格；同理，只要有一个是 #，那么直接停止遍历，因为就算一次走多个格也是不能穿墙的。

  2. 本题疑问一次可以走 k 步 以内，所以需要放进队列的比较多，所以可以在加入新结点时就判断一下是不是到达了终点，如果到了就直接输出，这样可以防止再多循环遍历一次而造成的 TLE。

说了这么多，上代码：

AC CODE：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int maxn=1000+5;
char a[maxn][maxn],vis[maxn][maxn];
int pos[4][2]={-1,0,0,-1,1,0,0,1};//增加新节点
int p1,m1,p2,m2; 
struct Node
{
    int x,y;
    int step;
};//存结点
queue<Node> q;
void bfs()
{
    Node now,nt;
    now.x=p1;now.y=m1;now.step=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x==p2&&now.y==m2)//到终点
        {
            cout<<now.step;
            return;

        }
        for(int i=0;i<4;i++)
        {
            for(int j=1;j<=k;j++)
            {
                int nx=now.x+pos[i][0]*j;
                int ny=now.y+pos[i][1]*j;//新增结点
                if(nx<1||ny<1||nx>n||ny>m)break;//出格
                if(a[nx][ny]=='#')break;//是墙
                if(vis[nx][ny]==0)
                {
                    if(nx==p2&&ny==m2)//到终点
                    {
                        cout<<now.step+1;
                        return;
                    }
                    vis[nx][ny]=1;
                    nt.x=nx;
                    nt.y=ny;
                    nt.step=now.step+1;
                    q.push(nt);//加到队列里
                }
            }
        }
    } 
    cout<<-1;//没有可行路线
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    cin>>p1>>m1>>p2>>m2;
    memset(vis,0,sizeof(vis));
    bfs();
    return 0;
}