题解：CF877D Olya and Energy Drinks

· · 题解

此题解使用的是朴素的剪枝。

首先直接想到 BFS，每次出队列要转移 k 次，注意判断边界和撞墙，也可以再加一个标记数组判断是否走过，时间复杂度是 O(nmk) 的。

想一下怎么剪。

搞一个数组 dis，表示到这个点的答案，出队列后，从这个点 (x,y) 开始往外找，假如到了 (x_1,y_1)，如果 (x_1,y_1) 的 dis 值本来就小于等于 (x,y) 的 dis 值，直接不管他了，我们求的一直是最小值，注意要先赋极大值。

代码

#include<bits/stdc++.h>
#define ll long long
#define R register
#define il inline
using namespace std;
#define rep(x,l,r) for(R int x=l;x<=r;++x)
#define per(x,l,r) for(R int x=l;x>=r;--x)
#define linf LLONG_MAX
#define N 2010
il ll read() {
    ll k=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {k=(k<<1)+(k<<3)+(c^48);c=getchar();}return f*k;
}int n,m,k,sx,sy,ex,ey,ans[N][N];
char a[N][N];
struct node{
    int x,y;
}temp;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
il void bfs(){
    queue<node>mine;
    mine.push({sx,sy});
    memset(ans,0x3f,sizeof ans);
    ans[sx][sy]=0;
    while(!mine.empty()){
        temp=mine.front();
        mine.pop();
        int x=temp.x,y=temp.y;
        if(x==ex&&y==ey){
            printf("%d\n",ans[x][y]);
            exit(0);
        }
        rep(i,0,3){
            rep(p,1,k){
                int xx=x+p*dx[i];
                int yy=y+p*dy[i];

                if(xx<1||xx>n||yy<1||yy>m) break;
                if(ans[xx][yy]<=ans[x][y]) break;
                if(a[xx][yy]=='#') break;
                if(ans[xx][yy]==0x3f3f3f3f){
                    ans[xx][yy]=ans[x][y]+1;
                    mine.push({xx,yy});
                }

            }
        }
    }puts("-1");
}
int main() {
    n=read();m=read();k=read();
    rep(i,1,n){
        scanf("%s",a[i]+1);
    }
    sx=read();sy=read();
    ex=read();ey=read();
    bool flag=0;
    rep(i,1,n){
        rep(j,1,m){
            if(a[i][j]=='#'){
                flag=1;
                break;
            }
        }if(flag) break;
    }
    if(!flag){
        ll ans=0;
        ans+=abs(sx-ex)/k;
        if(abs(sx-ex)%k) ans++;
        ans+=abs(sy-ey)/k;
        if(abs(sy-ey)%k) ans++;
        printf("%lld\n",ans);
    }
    else bfs();

    return 0;
}