题解 P1126 【机器人搬重物】

```cpp #include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<string> #include<queue> #include<algorithm> using namespace std; int main() { bool mapx[100][100]; //Map queue<int> quex,quey,quedir; //Queue of Line,Row & Direction int sx,sy,ex,ey,dir,n,m; char dx; int timex[100][100][4]={0}; //HASH int cachex,cachey,cachedir,cachedir2,cachego=0; //Caches int wayx[4]={-1,0,1,0},wayy[4]={0,1,0,-1}; //Direction Table memset(mapx,true,sizeof(mapx)); scanf("%d%d",&n,&m); for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { scanf("%d",&mapx[i][j]); } } scanf("%d%d%d%d %c",&sx,&sy,&ex,&ey,&dx);//可以在%c前面加个空格来吸收读入的时候的空格 switch(dx)//把字符形式的坐标转化成数字（我使用了方向表 直接用dir的值查表，再乘以前进的步数，就是坐标变化量 ！） { case 'N': dir=0; break; case 'E': dir=1; break; case 'S': dir=2; break; case 'W': dir=3; break; } sx--; sy--; ex--; ey--;//处理成数组下标的形式（数组下标从0开始） timex[sx][sy][dir]=0;/*初始化HASH*/ quex.push(sx); quey.push(sy); quedir.push(dir); //初始值入队列 while (quex.size()>0) { cachex=quex.front(); cachey=quey.front(); cachedir=quedir.front(); cachego=1; //队首值缓存一下，便于处理 if (cachex==ex && cachey==ey) //采用判断队首值的方法，起点和终点重合就不用加特判了 { printf("%d",timex[cachex][cachey][cachedir]); return 0; } for (int i=1;i<=5;i++)//五种命令 { if (i<=3/*如果是前三种*/ && cachex+wayx[cachedir]*i>=0 && cachex+wayx[cachedir]*i<n-1 && cachey+wayy[cachedir]*i>=0 && cachey+wayy[cachedir]*i<m-1/*没有越界*/ && cachego==i/*前面的移动成立*/) if (mapx[cachex+wayx[cachedir]*i][cachey+wayy[cachedir]*i]==0 && mapx[cachex+wayx[cachedir]*i+1][cachey+wayy[cachedir]*i]==0 && mapx[cachex+wayx[cachedir]*i+1][cachey+wayy[cachedir]*i+1]==0 && mapx[cachex+wayx[cachedir]*i][cachey+wayy[cachedir]*i+1]==0) //移动之后不越界 新的xy坐标是i（i同时代表了前进的步数 有1、2、3步）乘以方向表里目前的方向前进一步的xy坐标变化量 { cachego++;//前一步不能走，有一种情况是Hash表的这个位置已经存在一个更短的耗时。但这不代表这一步不能走，也不代表走这一步的耗时不是最短的（因为方向问题） if (timex[cachex+wayx[cachedir]*i][cachey+wayy[cachedir]*i][cachedir]==0) //Hash表内这个位置没有被访问过（如果访问过，则Hash表内一定是一个最短的耗时 { timex[cachex+wayx[cachedir]*i][cachey+wayy[cachedir]*i][cachedir]=timex[cachex][cachey][cachedir]+1;//根据结点所在层数写入Hash表 quex.push(cachex+wayx[cachedir]*i); quey.push(cachey+wayy[cachedir]*i); quedir.push(cachedir);//入队列 } } if (i==4) //Left { cachedir2=cachedir-1; if (cachedir2==-1) cachedir2=3;//如果由North转到West，就重置方向缓存 if (timex[cachex][cachey][cachedir2]==0) //Hash表内这个位置没有被访问过（如果访问过，则Hash表内一定是一个最短的耗时 { timex[cachex][cachey][cachedir2]=timex[cachex][cachey][cachedir]+1;//根据结点所在层数写入Hash表 quex.push(cachex); quey.push(cachey); quedir.push(cachedir2);//入队列 } } if (i==5) //Right 同上 { cachedir2=cachedir+1; if (cachedir2==4) cachedir2=0; if (timex[cachex][cachey][cachedir2]==0) { timex[cachex][cachey][cachedir2]=timex[cachex][cachey][cachedir]+1; quex.push(cachex); quey.push(cachey); quedir.push(cachedir2); } } } quex.pop(); quey.pop(); quedir.pop();//出队列 } cout<<-1<<endl; return 0; } ```