机器人搬重物

题目详情

需要把格子转化为点阵,注意机器人是有体积的(1.6m)

代码

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

struct node{
    int tx,ty,step,way;
}t1,t2;

int a[55][55],mark_way[55][55][5],n,m,tmp,x,y,nx,ny,cnt,  //注意这里不能直接标记位置,要标记位置和方向
    dx[]={0,0,0,0,1,2,3,0,0,0,-1,-2,-3},
    dy[]={0,1,2,3,0,0,0,-1,-2,-3,0,0,0};
char w;

int main(){
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            scanf("%d",&tmp);
            if (tmp==1){
                a[i][j]=a[i+1][j]=a[i][j+1]=a[i+1][j+1]=1;
            }
        }
    }
    n++; m++;
    cin>>x>>y>>nx>>ny>>w;
    for (int i=1;i<=n;++i){
        a[i][1]=1;
        a[i][m]=1;
    }
    for (int i=1;i<=m;++i){
        a[1][i]=1;
        a[n][i]=1;
    }
    x++; y++; nx++; ny++;
    queue <node> que;
    if (a[x][y]==0){
        t1.tx=x; t1.ty=y; t1.step=0;
        if (w=='E') t1.way=0;
        else if (w=='S') t1.way=1;
        else if (w=='W') t1.way=2;
        else t1.way=3;
        que.push(t1);
    }
    while (!que.empty()){
        t2=que.front();
        que.pop();
        if (t2.tx==nx&&t2.ty==ny){
            cout<<t2.step;
            return 0;
        }
        t1=t2; t1.way+=5; t1.way%=4; t1.step++; if (mark_way[t1.tx][t1.ty][t1.way]==0) {que.push(t1); mark_way[t1.tx][t1.ty][t1.way]=1;}
        t1=t2; t1.way+=3; t1.way%=4; t1.step++; if (mark_way[t1.tx][t1.ty][t1.way]==0) {que.push(t1); mark_way[t1.tx][t1.ty][t1.way]=1;}
        for (int i=1;i<=3;++i){
            t1=t2;
            int xx=t1.tx,yy=t1.ty,ww=t1.way;
            int ttx=xx+dx[ww*3+i],tty=yy+dy[ww*3+i];
            if (ttx>=1&&ttx<=n&&tty>=1&&tty<=m&&a[ttx][tty]==0&&mark_way[ttx][tty][t1.way]==0){
                mark_way[ttx][tty][ww]=1;
                t1.tx=ttx; t1.ty=tty; t1.step++; que.push(t1);
            }else break;
        }
    }
    cout<<-1;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/7/