P1126 机器人搬重物【洛谷算法习题】-拓冰网站定制

P1126 机器人搬重物

网页链接

P1126 机器人搬重物

题目描述

机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6 1.61.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N × M N\times MN×M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：

向前移动1 11步（Creep）；
向前移动2 22步（Walk）；
向前移动3 33步（Run）；
向左转（Left）；
向右转（Right）。

每个指令所需要的时间为1 11秒。请你计算一下机器人完成任务所需的最少时间。

输入格式

第一行为两个正整数N , M ( 1 ≤ N , M ≤ 50 ) N,M\ (1\le N,M\le50)N,M(1≤N,M≤50)，下面N NN行是储藏室的构造，0 00表示无障碍，1 11表示有障碍，数字之间用一个空格隔开。接着一行有4 44个整数和1 11个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E \tt EE，南S \tt SS，西W \tt WW，北N \tt NN），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式

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

输入输出样例 #1

输入 #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

输出 #1

解题思路

本题是带方向状态的最短路径搜索问题。机器人是一个直径1.6 1.61.6米的球，中心始终位于格点上，因此它实际占据的是以中心点为中心的2 × 2 2 \times 22×2个格子。我们需要在网格中移动机器人，每次可以向前走1 11、2 22或3 33步，或者向左/向右转，每个指令耗时1 11秒。求从起点到终点的最少时间，方向任意。

1. 问题等价转化

机器人占据的格子：设中心位于格点( i , j ) (i, j)(i,j)（1 ≤ i < N , 1 ≤ j < M 1 \le i < N,\ 1 \le j < M1≤i<N,1≤j<M），则机器人覆盖的四个格子为( i , j ) , ( i + 1 , j ) , ( i , j + 1 ) , ( i + 1 , j + 1 ) (i,j), (i+1,j), (i,j+1), (i+1,j+1)(i,j),(i+1,j),(i,j+1),(i+1,j+1)。只要这四个格子中任意一个为障碍（值为1 11），该中心点就不可用。
因此，可以预处理一个二维布尔数组B[i][j]，表示中心在( i , j ) (i,j)(i,j)是否可行：B[i][j] = A[i][j] | A[i+1][j] | A[i][j+1] | A[i+1][j+1]。其中A为原始障碍矩阵。
状态定义：机器人的状态由中心位置( x , y ) (x, y)(x,y)和当前朝向d i r dirdir组成。朝向用0 ∼ 3 0 \sim 30∼3表示：0 00北，1 11东，2 22南，3 33西。
移动规则：
- 向前移动1 11、2 22或3 33步，每步都必须检查新位置的B是否为假（可行）。若某一步不可行，则更远的步数也必然不可行，可直接break。
- 左转或右转：改变朝向，耗时1 11秒，位置不变。
目标：到达终点( E 1 , E 2 ) (E1, E2)(E1,E2)，朝向任意，求最小耗时。

2. 算法实现（BFS）

预处理：
- 读入N , M N, MN,M和障碍矩阵A AA。
- 构建B[i][j]，其中i ii从1 11到N − 1 N-1N−1，j jj从1 11到M − 1 M-1M−1。
初始化：
- 读入起点( S 1 , S 2 ) (S1, S2)(S1,S2)、终点( E 1 , E 2 ) (E1, E2)(E1,E2)和初始朝向字符。
- 将字符转换为方向编号d：N->0, E->1, S->2, W->3。
- 距离数组D[x][y][dir]初始化为极大值，D[S1][S2][d] = 0。
- 将初始状态入队。
BFS 过程：
- 从队列取出状态( x , y , d i r ) (x, y, dir)(x,y,dir)。
- 若( x , y ) = ( E 1 , E 2 ) (x, y) = (E1, E2)(x,y)=(E1,E2)，直接输出D[x][y][dir]并结束。
- 前进：根据当前朝向dir，确定移动方向向量。例如：
  - 北：x xx减少，y yy不变；
  - 东：y yy增加，x xx不变；
  - 南：x xx增加，y yy不变；
  - 西：y yy减少，x xx不变。
    循环步数s t e p = 1 ∼ 3 step = 1 \sim 3step=1∼3：
  - 计算新坐标( n x , n y ) (nx, ny)(nx,ny)。
  - 若越界或B[nx][ny]为真，则break（后续步数不可行）。
  - 若D[nx][ny][dir] > D[x][y][dir] + 1，则更新并入队。
- 转向：左转dir_left = (dir + 3) % 4，右转dir_right = (dir + 1) % 4。若距离可更新，则更新并入队。
输出：若队列空仍未到达，输出-1。

3. 复杂度分析

状态数：中心点最多( N − 1 ) × ( M − 1 ) (N-1) \times (M-1)(N−1)×(M−1)个，方向4 44种，总状态数O ( N M ) O(NM)O(NM)。
转移：每个状态最多尝试3 33种前进和2 22种转向，常数次操作。
时间复杂度：O ( N M ) O(NM)O(NM)，N , M ≤ 50 N, M \le 50N,M≤50，运算量极小。
空间复杂度：距离数组O ( N M × 4 ) O(NM \times 4)O(NM×4)，队列O ( N M ) O(NM)O(NM)，空间消耗可忽略。

总结

本题的关键在于正确理解机器人占据的2 × 2 2 \times 22×2格子，并预处理出所有可行的中心点。将朝向作为状态的一部分，用 BFS 逐层扩展，向前移动时注意障碍物阻挡，转向直接改变朝向。由于状态数很少，BFS 可以快速求出最短时间。

代码简要说明

数组A和B：A存储原始障碍，B存储中心点是否可行。
结构体Node：包含坐标x, y和方向z。
距离数组D：D[x][y][z]记录到达状态的最短时间，初始化为0x3f。
BFS 循环：
- 取出队首，若到达终点则输出。
- 根据方向z处理前进：z=0向北，z=1向东，z=2向南，z=3向西。对每个方向尝试1 ∼ 3 1 \sim 31∼3步，检查B并更新距离。
- 处理转向：左转(z+3)%4，右转(z+1)%4，耗时1 11秒。
输出：若队列空仍未到达，输出-1。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;boolA[55][55],B[55][55];ll n,m,D[55][55][5],S1,S2,E1,E2;charW;structNode{ll x,y,z;Node(ll a,ll b,ll c):x(a),y(b),z(c){}};queue<Node>Q;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)cin>>A[i][j];cin>>S1>>S2>>E1>>E2>>W;for(ll i=1;i<n;i++)for(ll j=1;j<m;j++)B[i][j]=A[i][j]|A[i+1][j]|A[i][j+1]|A[i+1][j+1];memset(D,0x3f,sizeof(D));ll d=(W=='N'?0:(W=='E'?1:(W=='S'?2:3)));Q.push({S1,S2,d});D[S1][S2][d]=0;while(!Q.empty()){Node c=Q.front();Q.pop();if(c.x==E1&&c.y==E2){cout<<D[c.x][c.y][c.z];return0;}if(c.z==0)for(ll j=1;j<=3;j++)if(D[c.x][c.y][c.z]+1<D[c.x-j][c.y][c.z])if(!B[c.x-j][c.y]&&c.x-j>=1){D[c.x-j][c.y][c.z]=D[c.x][c.y][c.z]+1;Q.push({c.x-j,c.y,c.z});}elsebreak;if(c.z==1)for(ll j=1;j<=3;j++)if(D[c.x][c.y][c.z]+1<D[c.x][c.y+j][c.z])if(!B[c.x][c.y+j]&&c.y+j<m){D[c.x][c.y+j][c.z]=D[c.x][c.y][c.z]+1;Q.push({c.x,c.y+j,c.z});}elsebreak;if(c.z==2)for(ll j=1;j<=3;j++)if(D[c.x][c.y][c.z]+1<D[c.x+j][c.y][c.z])if(!B[c.x+j][c.y]&&c.x+j<n){D[c.x+j][c.y][c.z]=D[c.x][c.y][c.z]+1;Q.push({c.x+j,c.y,c.z});}elsebreak;if(c.z==3)for(ll j=1;j<=3;j++)if(D[c.x][c.y][c.z]+1<D[c.x][c.y-j][c.z])if(!B[c.x][c.y-j]&&c.y-j>=1){D[c.x][c.y-j][c.z]=D[c.x][c.y][c.z]+1;Q.push({c.x,c.y-j,c.z});}elsebreak;for(ll j:{-1,1})if(D[c.x][c.y][c.z]+1<D[c.x][c.y][(c.z+j+4)%4]){Q.push({c.x,c.y,(c.z+j+4)%4});D[c.x][c.y][(c.z+j+4)%4]=D[c.x][c.y][c.z]+1;}}cout<<-1;return0;}

资讯详情

P1126 机器人搬重物【洛谷算法习题】