洛谷1162机器人搬重物
程序员文章站
2022-06-12 09:37:25
...
题目描述
机器人移动学会（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。
输入输出样例
广搜吧，但我思路简单，代码复杂度挺大的，纪念人生第一道码农题
把转身和走合并起来算两次时间，同理向后走算作三次时间
#include<bits/stdc++.h>
using namespace std;
queue <int> qx,qy;
queue <char> fx;
int n,m;
int qxx,qyy,zx,zy;
int s[550][550];
int ans[550][550];
char p;
bool check(int x,int y) {
if(x>=1&&y>=1&&x<n&&y<m)
return 1;
return 0;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
scanf("%d",&s[i][j]);
if(s[i][j]==1)
s[i-1][j]=s[i][j-1]=s[i-1][j-1]=1;
}
for(int i=0; i<=n; i++)
for(int j=0; j<=m; j++)
ans[i][j]=20021109;
scanf("%d%d%d%d",&qxx,&qyy,&zx,&zy);
cin>>p;
qx.push(qxx),qy.push(qyy),fx.push(p);
ans[qxx][qyy]=0;
while(!qx.empty()) {
int x=qx.front(),y=qy.front();
char pos=fx.front();
qx.pop(),qy.pop(),fx.pop();
if(pos=='S') {
if(check(x+1,y))
if(ans[x][y]+1<=ans[x+1][y] &&s[x+1][y]==0) {
ans[x+1][y]=ans[x][y]+1;
qx.push(x+1);
qy.push(y);
fx.push('S');
}
if(check(x+2,y))
if(ans[x][y]+1<=ans[x+2][y] &&s[x+1][y]==0 && s[x+2][y]==0) {
ans[x+2][y]=ans[x][y]+1;
qx.push(x+2);
qy.push(y);
fx.push('S');
}
if(check(x+3,y))
if(ans[x][y]+1<=ans[x+3][y] &&s[x+1][y]==0 && s[x+2][y]==0 &&s[x+3][y]==0) {
ans[x+3][y]=ans[x][y]+1;
qx.push(x+3);
qy.push(y);
fx.push('S');
}
if(check(x,y+1))
if(ans[x][y]+2<=ans[x][y+1] &&s[x][y+1]==0) {
ans[x][y+1]=ans[x][y]+2;
qx.push(x);
qy.push(y+1);
fx.push('E');
}
if(check(x,y+2))
if(ans[x][y]+2<=ans[x][y+2] &&s[x][y+1]==0 && s[x][y+2]==0) {
ans[x][y+2]=ans[x][y]+2;
qx.push(x);
qy.push(y+2);
fx.push('E');
}
if(check(x,y+3))
if(ans[x][y]+2<=ans[x][y+3] &&s[x][y+1]==0 && s[x][y+2]==0 &&s[x][y+3]==0) {
ans[x][y+3]=ans[x][y]+2;
qx.push(x);
qy.push(y+3);
fx.push('E');
}
if(check(x,y-1))
if(ans[x][y]+2<=ans[x][y-1] &&s[x][y-1]==0) {
ans[x][y-1]=ans[x][y]+2;
qx.push(x);
qy.push(y-1);
fx.push('W');
}
if(check(x,y-2))
if(ans[x][y]+2<=ans[x][y-2] &&s[x][y-1]==0 && s[x][y-2]==0) {
ans[x][y-2]=ans[x][y]+2;
qx.push(x);
qy.push(y-2);
fx.push('W');
}
if(check(x,y-3))
if(ans[x][y]+2<=ans[x][y-3] &&s[x][y-1]==0 && s[x][y-2]==0 &&s[x][y-3]==0) {
ans[x][y-3]=ans[x][y]+2;
qx.push(x);
qy.push(y-3);
fx.push('W');
}
if(check(x-1,y))
if(ans[x][y]+3<=ans[x-1][y] &&s[x-1][y]==0) {
ans[x-1][y]=ans[x][y]+3;
qx.push(x-1);
qy.push(y);
fx.push('N');
}
if(check(x-2,y))
if(ans[x][y]+3<=ans[x-2][y] &&s[x-1][y]==0 && s[x-2][y]==0) {
ans[x-2][y]=ans[x][y]+3;
qx.push(x-2);
qy.push(y);
fx.push('N');
}
if(check(x-3,y))
if(ans[x][y]+3<=ans[x-3][y] &&s[x-1][y]==0 && s[x-2][y]==0 &&s[x-3][y]==0) {
ans[x-3][y]=ans[x][y]+3;
qx.push(x-3);
qy.push(y);
fx.push('N');
}
}
if(pos=='N') {
if(check(x-1,y))
if(ans[x][y]+1<=ans[x-1][y] &&s[x-1][y]==0) {
ans[x-1][y]=ans[x][y]+1;
qx.push(x-1);
qy.push(y);
fx.push('N');
}
if(check(x-2,y))
if(ans[x][y]+1<=ans[x-2][y] &&s[x-1][y]==0 && s[x-2][y]==0) {
ans[x-2][y]=ans[x][y]+1;
qx.push(x-2);
qy.push(y);
fx.push('N');
}
if(check(x-3,y))
if(ans[x][y]+1<=ans[x-3][y] &&s[x-1][y]==0 && s[x-2][y]==0 &&s[x-3][y]==0) {
ans[x-3][y]=ans[x][y]+1;
qx.push(x-3);
qy.push(y);
fx.push('N');
}
if(check(x,y+1))
if(ans[x][y]+2<=ans[x][y+1] &&s[x][y+1]==0) {
ans[x][y+1]=ans[x][y]+2;
qx.push(x);
qy.push(y+1);
fx.push('E');
}
if(check(x,y+2))
if(ans[x][y]+2<=ans[x][y+2] &&s[x][y+1]==0 && s[x][y+2]==0) {
ans[x][y+2]=ans[x][y]+2;
qx.push(x);
qy.push(y+2);
fx.push('E');
}
if(check(x,y+3))
if(ans[x][y]+2<=ans[x][y+3] &&s[x][y+1]==0 && s[x][y+2]==0 &&s[x][y+3]==0) {
ans[x][y+3]=ans[x][y]+2;
qx.push(x);
qy.push(y+3);
fx.push('E');
}
if(check(x,y-1))
if(ans[x][y]+2<=ans[x][y-1] &&s[x][y-1]==0) {
ans[x][y-1]=ans[x][y]+2;
qx.push(x);
qy.push(y-1);
fx.push('W');
}
if(check(x,y-2))
if(ans[x][y]+2<=ans[x][y-2] &&s[x][y-1]==0 && s[x][y-2]==0) {
ans[x][y-2]=ans[x][y]+2;
qx.push(x);
qy.push(y-2);
fx.push('W');
}
if(check(x,y-3))
if(ans[x][y]+2<=ans[x][y-3] &&s[x][y-1]==0 && s[x][y-2]==0 &&s[x][y-3]==0) {
ans[x][y-3]=ans[x][y]+2;
qx.push(x);
qy.push(y-3);
fx.push('W');
}
if(check(x+1,y))
if(ans[x][y]+3<=ans[x+1][y] &&s[x+1][y]==0) {
ans[x+1][y]=ans[x][y]+3;
qx.push(x+1);
qy.push(y);
fx.push('S');
}
if(check(x+2,y))
if(ans[x][y]+3<=ans[x+2][y] &&s[x+1][y]==0 && s[x+2][y]==0) {
ans[x+2][y]=ans[x][y]+3;
qx.push(x+2);
qy.push(y);
fx.push('S');
}
if(check(x+3,y))
if(ans[x][y]+3<=ans[x+3][y] &&s[x+1][y]==0 && s[x+2][y]==0 &&s[x+3][y]==0) {
ans[x+3][y]=ans[x][y]+3;
qx.push(x+3);
qy.push(y);
fx.push('S');
}
}
if(pos=='E') {
if(check(x,y+1))
if(ans[x][y]+1<=ans[x][y+1] &&s[x][y+1]==0) {
ans[x][y+1]=ans[x][y]+1;
qx.push(x);
qy.push(y+1);
fx.push('E');
}
if(check(x,y+2))
if(ans[x][y]+1<=ans[x][y+2] &&s[x][y+1]==0 && s[x][y+2]==0) {
ans[x][y+2]=ans[x][y]+1;
qx.push(x);
qy.push(y+2);
fx.push('E');
}
if(check(x,y+3))
if(ans[x][y]+1<=ans[x][y+3] &&s[x][y+3]==0 && s[x][y+2]==0 &&s[x][y+1]==0) {
ans[x][y+3]=ans[x][y]+1;
qx.push(x);
qy.push(y+3);
fx.push('E');
}
if(check(x-1,y))
if(ans[x][y]+2<=ans[x-1][y] &&s[x-1][y]==0) {
ans[x-1][y]=ans[x][y]+2;
qx.push(x-1);
qy.push(y);
fx.push('N');
}
if(check(x-2,y));
if(ans[x][y]+2<=ans[x-2][y] &&s[x-1][y]==0 && s[x-2][y]==0) {
ans[x-2][y]=ans[x][y]+2;
qx.push(x-2);
qy.push(y);
fx.push('N');
}
if(check(x-3,y))
if(ans[x][y]+2<=ans[x-3][y] &&s[x-1][y]==0 && s[x-2][y]==0 &&s[x-3][y]==0) {
ans[x-3][y]=ans[x][y]+2;
qx.push(x-3);
qy.push(y);
fx.push('N');
}
if(check(x+1,y))
if(ans[x][y]+2<=ans[x+1][y] &&s[x+1][y]==0) {
ans[x+1][y]=ans[x][y]+2;
qx.push(x+1);
qy.push(y);
fx.push('S');
}
if(check(x+2,y));
if(ans[x][y]+2<=ans[x+2][y] &&s[x+1][y]==0 && s[x+2][y]==0) {
ans[x+2][y]=ans[x][y]+2;
qx.push(x+2);
qy.push(y);
fx.push('S');
}
if(check(x+3,y))
if(ans[x][y]+2<=ans[x+3][y] &&s[x+1][y]==0 && s[x+2][y]==0 &&s[x+3][y]==0) {
ans[x+3][y]=ans[x][y]+2;
qx.push(x+3);
qy.push(y);
fx.push('S');
}
if(check(x,y-1))
if(ans[x][y]+3<=ans[x][y-1] &&s[x][y-1]==0) {
ans[x][y-1]=ans[x][y]+3;
qx.push(x);
qy.push(y-1);
fx.push('W');
}
if(check(x,y-2))
if(ans[x][y]+3<=ans[x][y-2] &&s[x][y-1]==0 && s[x][y-2]==0) {
ans[x][y-2]=ans[x][y]+3;
qx.push(x);
qy.push(y-2);
fx.push('W');
}
if(check(x,y-3))
if(ans[x][y]+3<=ans[x][y-3] &&s[x][y-1]==0 && s[x][y-2]==0 &&s[x][y-3]==0) {
ans[x][y-3]=ans[x][y]+3;
qx.push(x);
qy.push(y-3);
fx.push('W');
}
}
if(pos=='W') {
if(check(x,y-1))
if(ans[x][y]+1<=ans[x][y-1] &&s[x][y-1]==0) {
ans[x][y-1]=ans[x][y]+1;
qx.push(x);
qy.push(y-1);
fx.push('W');
}
if(check(x,y-2))
if(ans[x][y]+1<=ans[x][y-2] &&s[x][y-1]==0 && s[x][y-2]==0) {
ans[x][y-2]=ans[x][y]+1;
qx.push(x);
qy.push(y-2);
fx.push('W');
}
if(check(x,y-3))
if(ans[x][y]+1<=ans[x][y-3] &&s[x][y-1]==0 && s[x][y-2]==0 &&s[x][y-3]==0) {
ans[x][y-3]=ans[x][y]+1;
qx.push(x);
qy.push(y-3);
fx.push('W');
}
if(check(x-1,y))
if(ans[x][y]+2<=ans[x-1][y] &&s[x-1][y]==0) {
ans[x-1][y]=ans[x][y]+2;
qx.push(x-1);
qy.push(y);
fx.push('N');
}
if(check(x-2,y))
if(ans[x][y]+2<=ans[x-2][y] &&s[x-1][y]==0 && s[x-2][y]==0) {
ans[x-2][y]=ans[x][y]+2;
qx.push(x-2);
qy.push(y);
fx.push('N');
}
if(check(x-3,y))
if(ans[x][y]+2<=ans[x-3][y] &&s[x-1][y]==0 && s[x-2][y]==0 &&s[x-3][y]==0) {
ans[x-3][y]=ans[x][y]+2;
qx.push(x-3);
qy.push(y);
fx.push('N');
}
if(check(x+1,y))
if(ans[x][y]+2<=ans[x+1][y] &&s[x+1][y]==0) {
ans[x+1][y]=ans[x][y]+2;
qx.push(x+1);
qy.push(y);
fx.push('S');
}
if(check(x+2,y))
if(ans[x][y]+2<=ans[x+2][y] &&s[x+1][y]==0 && s[x+2][y]==0) {
ans[x+2][y]=ans[x][y]+2;
qx.push(x+2);
qy.push(y);
fx.push('S');
}
if(check(x+3,y))
if(ans[x][y]+2<=ans[x+3][y] &&s[x+1][y]==0 && s[x+2][y]==0 &&s[x+3][y]==0) {
ans[x+3][y]=ans[x][y]+2;
qx.push(x+3);
qy.push(y);
fx.push('S');
}
if(check(x,y+1))
if(ans[x][y]+3<=ans[x][y+1] &&s[x][y+1]==0) {
ans[x][y+1]=ans[x][y]+3;
qx.push(x);
qy.push(y+1);
fx.push('E');
}
if(check(x,y+2))
if(ans[x][y]+3<=ans[x][y+2] &&s[x][y+1]==0 && s[x][y+2]==0) {
ans[x][y+2]=ans[x][y]+3;
qx.push(x);
qy.push(y+2);
fx.push('E');
}
if(check(x,y+3))
if(ans[x][y]+3<=ans[x][y+3] &&s[x][y+3]==0 && s[x][y+2]==0 &&s[x][y+1]==0) {
ans[x][y+3]=ans[x][y]+3;
qx.push(x);
qy.push(y+3);
fx.push('E');
}
}
if(ans[zx][zy]!=20021109) {
printf("%d",ans[zx][zy]);
return 0;
}
}
printf("-1");
return 0;
}