机器人搬重物

机器人搬重物

时间限制: 1 Sec   内存限制: 128 MB 提交: 28   解决: 13 [ 提交][ 状态][ 讨论版]

题目描述

机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：先前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。  

输入

输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。

样例输入

9 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 7 2 2 7 S

样例输出

12

代码一,直接模拟题意，坐标位置代表左上角区块的位置。

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<queue> #define PI acos(-1.0) using namespace std; const double eps = 1e-10; int G[55][55]; int n,m; int sx,sy,ex,ey; char dirr[10] = "NSWE"; bool vis[55][55][4]; int dir; struct node{ int x,y,step; int dir; }; bool inborder(node tt){ if(tt.x >=0 && tt.x <n && tt.y>=0 && tt.y <m && tt.x-1 >=0 && tt.x-1 <n && tt.y>=0 && tt.y <m && tt.x-1 >=0 && tt.x-1 <n && tt.y-1>=0 && tt.y-1 <m && tt.x >=0 && tt.x <n && tt.y-1>=0 && tt.y-1 <m && G[tt.x][tt.y] == 0 && G[tt.x-1][tt.y] == 0 && G[tt.x-1][tt.y-1] == 0&& G[tt.x][tt.y-1] == 0 ) { return true; } return false; } void bfs(){ queue<node>Q; node st; st.x = sx; st.y = sy; st.step = 0;st.dir = dir; Q.push(st); int Find = 0; while(!Q.empty()){ node now = Q.front();Q.pop(); // cout<<now.x<<" "<<now.y<<" "<<now.dir<<" "<<now.step<<endl; if(now.x == ex && now.y == ey){ printf("%d\n",now.step);Find = 1; break; } node nt; for(int i=2;i<5;i++){ if(now.dir == 0){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x -1; aa.y =now.y; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x -2; bb.y =now.y; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x -3; cc.y =now.y; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 2; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 3; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) && !vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } else if(now.dir == 1){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x +1; aa.y =now.y; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x +2; bb.y =now.y; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x +3; cc.y =now.y; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 3; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 2; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) && !vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } else if(now.dir == 2){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x; aa.y =now.y -1; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x; bb.y =now.y -2; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x; cc.y =now.y -3; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 1; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 0; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) && !vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } else if(now.dir == 3){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x; aa.y =now.y +1; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x; bb.y =now.y +2; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x; cc.y =now.y +3; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 0; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 1; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) &&!vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } } } if(!Find){ printf("-1\n"); } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ memset(G,0,sizeof(G)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++) scanf("%d",&G[i][j]); } char dd; memset(vis,0,sizeof(vis)); scanf("%d%d%d%d %c",&sx,&sy,&ex,&ey,&dd); for(int i=0;i<4;i++){ if(dd == dirr[i]) dir = i; } vis[sx][sy][dir] = 1; bfs(); } return 0 ; } 代码二

修改地图，以区块的边界线作为节点，这样输入的时候从1 1 开始读入地图，空出一行来。然后由于机器人边界问题，所以坐标活动范围只能是 1 ~ n-1 1 ~ m-1;

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<queue> #define PI acos(-1.0) using namespace std; const double eps = 1e-10; int G[55][55]; int n,m; int sx,sy,ex,ey; char dirr[10] = "NSWE"; bool vis[55][55][4]; int dir; struct node{ int x,y,step; int dir; }; bool inborder(node tt){ if(tt.x >0 && tt.x <n && tt.y>0 && tt.y <m && G[tt.x][tt.y] == 0 ) { return true; } return false; } void bfs(){ queue<node>Q; node st; st.x = sx; st.y = sy; st.step = 0;st.dir = dir; Q.push(st); int Find = 0; while(!Q.empty()){ node now = Q.front();Q.pop(); // cout<<now.x<<" "<<now.y<<" "<<now.dir<<" "<<now.step<<endl; if(now.x == ex && now.y == ey){ printf("%d\n",now.step);Find = 1; break; } node nt; for(int i=2;i<5;i++){ if(now.dir == 0){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x -1; aa.y =now.y; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x -2; bb.y =now.y; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x -3; cc.y =now.y; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 2; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 3; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) && !vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } else if(now.dir == 1){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x +1; aa.y =now.y; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x +2; bb.y =now.y; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x +3; cc.y =now.y; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 3; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 2; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) && !vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } else if(now.dir == 2){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x; aa.y =now.y -1; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x; bb.y =now.y -2; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x; cc.y =now.y -3; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 1; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 0; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) && !vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } else if(now.dir == 3){ if(i < 3){ node aa ,bb ,cc; aa.x = now.x; aa.y =now.y +1; aa.step = now.step+1;aa.dir = now.dir; bb.x = now.x; bb.y =now.y +2; bb.step = now.step+1;bb.dir = now.dir; cc.x = now.x; cc.y =now.y +3; cc.step = now.step+1;cc.dir = now.dir; if(inborder(aa) && !vis[aa.x][aa.y][aa.dir]){ Q.push(aa); vis[aa.x][aa.y][aa.dir] = 1; } if(inborder(aa) && inborder(bb) && !vis[bb.x][bb.y][bb.dir]){ Q.push(bb); vis[bb.x][bb.y][bb.dir] = 1; } if(inborder(aa) && inborder(bb) && inborder(cc) && !vis[cc.x][cc.y][cc.dir]){ Q.push(cc); vis[cc.x][cc.y][cc.dir] = 1; } continue; } else if(i == 3){ nt.dir = 0; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } else if(i ==4){ nt.dir = 1; nt.x = now.x; nt.y = now.y; nt.step = now.step + 1; } if(inborder(nt) &&!vis[nt.x][nt.y][nt.dir]){ Q.push(nt); vis[nt.x][nt.y][nt.dir] = 1; } } } } if(!Find){ printf("-1\n"); } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ memset(G,0,sizeof(G)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) scanf("%d",&G[i][j]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) if(G[i][j] == 1){ G[i-1][j] = 1; G[i-1][j-1] = 1; G[i][j-1] = 1; } } char dd; memset(vis,0,sizeof(vis)); scanf("%d%d%d%d %c",&sx,&sy,&ex,&ey,&dd); for(int i=0;i<4;i++){ if(dd == dirr[i]) dir = i; } vis[sx][sy][dir] = 1; bfs(); } return 0 ; } 代码略丑。。