[luogu p1126] 机器人搬重物
题面
题目描述
机器人移动学会(RMI
)现在正尝试用机器人搬运物品。机器人的形状是一个直径\(1.6\)米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个 \(N \times M\) 的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动\(1\)步(Creep
);向前移动2步(Walk
);向前移动\(3\) 步(Run
);向左转(Left
);向右转(Right
)。每个指令所需要的时间为\(1\) 秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式
第一行为两个正整数\(N,M(N,M \le 50)\),下面\(N\)行是储藏室的构造,\(0\)表示无障碍,\(1\)表示有障碍,数字之间用一个空格隔开。接着一行有\(4\)个整数和\(1\)个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东\(E\),南\(S\),西\(W\),北\(N\)),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式
一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出\(-1\)。
输入输出样例
输入样例 #1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 7 S
输出样例 #1
12
分析
这道题一看就是个广搜,思维没有难度,但是细节确实很多,需要注意的是:
- 障碍物在格子上,机器人在格点上。
- 机器人有直径,所以不可以活动到储藏室的外围部分。实际的一个障碍物会导致机器人的中心有四个点不可取,不只是一个,还有障碍物的四个角。
- 向前走的时候,如果遇到墙,我们应该 立刻
break
循环,停止一步到三步的枚举,而不是continue
。 因为continue
会导致机器人在接下来的循环中可能会穿墙而走,现实中这当然不可取。 - 机器人在旋转时也需要1s的时间。
- 记忆化搜索的时候,我们会有一个标记数组
vis
,我一开始想的是读到障碍物就把四个点的vis
数组标记为true
,但是在实际编码中我发现了这样存在的问题,刚才说了,如果遇到墙,我们应该 立刻break
循环,停止一步到三步的枚举,而不是continue
。 但是已经访问的点却不一定要这样,这一点需注意。如果样例的输出是7
,很可能就是如此导致的。
分析完这么多细节,是时候上代码了。
代码
广搜,bfs
。
#include <iostream> #include <cstdio> #include <cstdlib> #include <queue> int n,m; int startx,starty,endx,endy,dir; bool vis[20005]; int state[55][55]; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; struct node{ int x,y,d,step; }; std :: queue <node> q; int getkey(int x,int y,int dir){ return dir * 2500 + x * 50 + y; }//这就保证了每一个x,y在dir方向上都有一个对应的key,便于记忆化。 bool valid(int x,int y,int dir){ if(x <= 0 || y <= 0 || x >= n || y >= m || state[x][y] || state[x+1][y] || state[x+1][y+1] || state[x][y+1]) return false; return true; }//判断是否超出边界,或者是有没有墙 void bfs(){ switch(dir){ case 'N': dir = 0; break; case 'E': dir = 1; break; case 'S': dir = 2; break; case 'W': dir = 3; break; default: dir = 10086; break; } node now; now.x = startx; now.y = starty; now.d = dir; now.step = 0; q.push(now); while(!q.empty()){ now = q.front(); q.pop(); int nowx = now.x; int nowy = now.y; int dir = now.d; //printf("%d %d %d \n",nowx,nowy,dir); int key = getkey(nowx,nowy,dir); if(nowx == endx && nowy == endy){ printf("%d\n",now.step); exit(0); } //std :: cout << "Getting key done:"<<key << std :: endl; if(vis[key]) continue; vis[key] = true; //这两句是记忆化的部分。 node nxt; nxt.step = now.step + 1; int nxtx = now.x; int nxty = now.y; nxt.x = nxtx; nxt.y = nxty; nxt.d = (dir + 3) % 4; q.push(nxt); nxt.d = (dir + 5) % 4; q.push(nxt); nxt.d = dir; for(int i = 1; i <= 3; i++){ nxtx = nowx + dx[dir] * i; nxty = nowy + dy[dir] * i; if(!valid(nxtx,nxty,dir)) break;//千万不能是continue,原因刚刚说了 nxt.x = nxtx; nxt.y = nxty; q.push(nxt); } } printf("-1\n"); return ; } int main(){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ scanf("%d",&state[i][j]); if(!state[i][j]) continue; for(int dir = 0; dir <= 3; dir++){ state[i][j] = true; state[i+1][j] = true; state[i+1][j+1] = true; state[i][j+1] = true; } } scanf("%d %d %d %d %c",&startx,&starty,&endx,&endy,&dir); bfs(); return 0; }
评测结果
AC 100
:R30912296
over.