CF877D 题解

BlackPanda · 2022-04-08 11:04:37 · 题解

题目传送门

题意：

给定一个 N×M 的迷宫和 K，然后给定起点和终点，每次可以像四个方向走 1-K 步（只能走.的格子），求从起点到终点的最小时间，如不能到达输出 -1。

思路：

这道题求的是最小时间，可以用 BFS 加剪枝来做，建一个 STL 的队列，把每次向外扩展的四个点分别判断是否合法，如果没有出界并且合法就压入队列，每次取出队头判断是否到达终点，如果到达就输出答案并退出程序，如果直到队列为空都没有找到答案，就输出 -1。

注意：

• 如果碰到了墙壁，直接 break，而不是 continue，因为就算向此方向走多个格依然是碰到墙壁的，而不会穿过它。

• 为了防止 TLE，我们可以在新加入的结点中就进行判断，节约时间。

• 一定要在判断向外扩展点是否是 # 之前先判断是否越界，否则就会 RE！！！！！

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node{
    ll x,y,step;
};

ll n,m,k;
ll sx,sy,ex,ey;
char c[1005][1005];
bool vis[1005][1005];
ll xx[]={0,0,1,-1};
ll yy[]={1,-1,0,0};
queue<Node> q;

void bfs(){
    Node f,r;
    r={sx,sy,0};
    q.push(r);
    while(!q.empty()){
        f=q.front();
        q.pop();
        if(f.x==ex && f.y==ey){
            cout<<f.step;
            return ;
        }
        for(ll i=0;i<4;i++){
            for(ll j=1;j<=k;j++){
                ll dx=xx[i]*j+f.x;
                ll dy=yy[i]*j+f.y;
                if(dx<1 || dx>n || dy<1 || dy>m)
                    break;
                if(c[dx][dy]=='#')  break; 
                if(!vis[dx][dy]){
                    if(dx==ex && dy==ey){
                        cout<<f.step+1;
                        return ;
                    }
                    vis[dx][dy]=1; 
                    r={dx,dy,f.step+1};
                    q.push(r);
                }
            }
        }
    }
    cout<<-1;
}

int main(){
    cin>>n>>m>>k;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>c[i][j];
        }
    }
    cin>>sx>>sy>>ex>>ey;
    bfs();
    return 0;
}