洛谷 P1126 机器人搬重物题解

佚名 6年前 (2019-04-16) 随笔 1014人围观抢沙发百度已收录

P1126 机器人搬重物

题目链接

P1126 机器人搬重物

题解

一道非常裸的SPFA的题目

没有学过SPFA的小伙伴可以用DFS也可以。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

dst[i][j][k]表示走到第i行的第j列这一次走k步的最优解

p数组控制方向，不懂的理解一下

dst[i][j][k]要往4个方向扫一下

别的就是SPFA不解释了吧

#include<bits/stdc++.h>
#define maxn 55
using namespace std;
int n,m,sx,sy,ex,ey,sw;
int p[4][2]={{-1,0},{0,1},{1,0},{0,-1}},dst[maxn][maxn][4],ans,INF;  //p数组存方向，dst存每个格子每个方向的最短路，多开的一维是方向
bool mp[maxn][maxn],vis[maxn][maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void work(){ //SPFA
    memset(dst,63,sizeof dst);
    ans=INF=dst[0][0][0];
    dst[sx][sy][sw]=0;
    bool flg=1;
    while(flg){
        flg=0;
        for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
        for(int k=0;k<4;k++){  //k枚举方向
            if(mp[i][j]||INF==dst[i][j][k]) continue;
            for(int s=1;s<4;s++){ //s枚举移动的距离
                int x=i+s*p[k][0],y=j+s*p[k][1];
                if(mp[x][y]) break;
                if(dst[x][y][k]>dst[i][j][k]+1)dst[x][y][k]=dst[i][j][k]+1,flg=1;
            }
            if(dst[i][j][(k+1)%4]>dst[i][j][k]+1) dst[i][j][(k+1)%4]=dst[i][j][k]+1,flg=1;
            if(dst[i][j][(k+3)%4]>dst[i][j][k]+1) dst[i][j][(k+3)%4]=dst[i][j][k]+1,flg=1;
        }
    }
}
int main(){
//  freopen("robot.in","r",stdin);
//  freopen("robot.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) vis[i][j]=read();
    for(int i=1;i<n;i++)
    for(int j=1;j<m;j++) if(!vis[i][j]&&!vis[i+1][j]&&!vis[i][j+1]&&!vis[i+1][j+1]) mp[i][j]=0;else mp[i][j]=1;
    sx=read(),sy=read(),ex=read(),ey=read();
    if(sx==ex&&sy==ey){
        printf("0\n");
        return 0;
    }
    char ch=getchar();
    while(ch!='E'&&ch!='W'&&ch!='S'&&ch!='N') ch=getchar();
    if(ch=='N') sw=0;else
    if(ch=='E') sw=1;else
    if(ch=='S') sw=2;else
    if(ch=='W') sw=3;

    work();
    for(int i=0;i<4;i++) ans=min(dst[ex][ey][i],ans);
    if(ans==INF) printf("-1\n");else
    printf("%d\n",ans);
    return 0;
}