题解 P1126 【机器人搬重物】

##历时两个半小时，终于把这道题AC了。 ###核心思路：单向bfs即可，不懂bfs的可以先去学习一下，不难掌握，而且非常有用。 **这道题其实不难，但是因为要注意的地方比较多，所以硬生生从普及-的难度到了提高-...** **坑点列举：** - 注意机器人是球形且有直径，所以机器人不能到达储藏室的边缘。 - 注意样例，一个障碍物直接占满一个格子，而同样因为机器人的直径问题，不能到这些格子的格点上去。 - 在移动时机器人也需要一步一步移动，所以机器人不能跨过障碍物，即遇到障碍物就必须停止。 **程序细节：** - 判重用三维数组来判，因为这道题中，机器人的状态不只有坐标，还有方向，只记录坐标会导致无解情况出现。 - 针对【坑点列举】中的第二点，我们可以为数组加个预处理，**对于每一个障碍点（i，j），它都会使它的左上角（i-1，j-1），上方（i-1，j），左方（i，j-1）的点无法被机器人行走，利用这一点即可生成map[]数组来表示一个点能否行走。** - scanf党记得在输入起始方向时在第一个参数内+空格，如：scanf(" %c",&starttdirection);否则记录起始方向的char变量会变成空格。 以下AC代码：（注释不多，思路和细节都在前面讲了，程序内只有结构的说明） ···cpp ```cpp #include<cstdio> #include<queue> using namespace std; struct robot{ int x,y;//坐标值 int direction;//方向 int step; }; queue<robot> q; bool vis[51][51][4]; bool map[52][52]; int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; int main(){ int n,m; int sx,sy,ex,ey,sd;//起始点和终点坐标 char sdirection;//起始方向 scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&map[i][j]); if(map[i][j]){ map[i-1][j-1]=1; map[i-1][j]=1; map[i][j-1]=1; } } } //预处理 scanf("%d%d%d%d %c",&sx,&sy,&ex,&ey,&sdirection); if(sdirection=='E')sd=0; else if(sdirection=='S')sd=1; else if(sdirection=='W')sd=2; else sd=3;//将方向转化为数字便于判重 if(sx>=n || sx<1 || sy>=m || sy<1 || map[sx][sy]){printf("-1");return 0;} robot temp; temp.x=sx;temp.y=sy;temp.direction=sd;temp.step=0;//从起点开始，将起点状态塞进队列 vis[sx][sy][sd]=true;//别忘了标记起始点对应的方向 q.push(temp); while(!q.empty()){ //之后就是bfs了，枚举5种操作 并判断状态是否已被访问过，注意行走的时候的判定障碍问题 temp=q.front(); q.pop(); int nx=temp.x,ny=temp.y; if(nx==ex && ny==ey){printf("%d",temp.step);return 0;}//有了结果立即输出 for(int i=1;i<=3;i++){ //走1步~走3步 nx+=dx[temp.direction];ny+=dy[temp.direction]; //哇！此题巨坑，机器人直径1.6m... if(nx<1 || nx>=n || ny<1 || ny>=m || map[nx][ny])break; //重点，不能走到边界，也不能走到障碍点所影响的点，否则就不能继续走了，跳出循环 else if(!vis[nx][ny][temp.direction]){ vis[nx][ny][temp.direction]=true; robot cnew;cnew.x=nx;cnew.y=ny;cnew.direction=temp.direction; cnew.step=temp.step+1; q.push(cnew); //printf("%d %d - %d %d step:%d\n",temp.x,temp.y,cnew.x,cnew.y,cnew.step); } } //转向 robot cnew;cnew.x=temp.x;cnew.y=temp.y;cnew.step=temp.step+1; cnew.direction=temp.direction-1; if(cnew.direction==-1)cnew.direction=3;//如果我从东向西转，那么应该到北 if(!vis[cnew.x][cnew.y][cnew.direction]){vis[cnew.x][cnew.y][cnew.direction]=true;q.push(cnew);} cnew.direction=temp.direction+1; if(cnew.direction==4)cnew.direction=0;//如果我从北向东转，那么应该到东 if(!vis[cnew.x][cnew.y][cnew.direction]){vis[cnew.x][cnew.y][cnew.direction]=true;q.push(cnew);} } printf("-1");//无解 return 0; } ``` ```cpp