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输入 #19 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输出 #112解题思路本题是带方向状态的最短路径搜索问题。机器人是一个直径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≤iN,1≤jM则机器人覆盖的四个格子为( i , j ) , ( i 1 , j ) , ( i , j 1 ) , ( i 1 , j 1 ) (i,j), (i1,j), (i,j1), (i1,j1)(i,j),(i1,j),(i,j1),(i1,j1)。只要这四个格子中任意一个为障碍值为1 11该中心点就不可用。因此可以预处理一个二维布尔数组B[i][j]表示中心在( i , j ) (i,j)(i,j)是否可行B[i][j] A[i][j] | A[i1][j] | A[i][j1] | A[i1][j1]。其中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−1j jj从1 11到M − 1 M-1M−1。初始化读入起点( S 1 , S 2 ) (S1, S2)(S1,S2)、终点( E 1 , E 2 ) (E1, E2)(E1,E2)和初始朝向字符。将字符转换为方向编号dN-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 3step1∼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和BA存储原始障碍B存储中心点是否可行。结构体Node包含坐标x, y和方向z。距离数组DD[x][y][z]记录到达状态的最短时间初始化为0x3f。BFS 循环取出队首若到达终点则输出。根据方向z处理前进z0向北z1向东z2向南z3向西。对每个方向尝试1 ∼ 3 1 \sim 31∼3步检查B并更新距离。处理转向左转(z3)%4右转(z1)%4耗时1 11秒。输出若队列空仍未到达输出-1。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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){}};queueNodeQ;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;in;i)for(ll j1;jm;j)cinA[i][j];cinS1S2E1E2W;for(ll i1;in;i)for(ll j1;jm;j)B[i][j]A[i][j]|A[i1][j]|A[i][j1]|A[i1][j1];memset(D,0x3f,sizeof(D));ll d(WN?0:(WE?1:(WS?2:3)));Q.push({S1,S2,d});D[S1][S2][d]0;while(!Q.empty()){Node cQ.front();Q.pop();if(c.xE1c.yE2){coutD[c.x][c.y][c.z];return0;}if(c.z0)for(ll j1;j3;j)if(D[c.x][c.y][c.z]1D[c.x-j][c.y][c.z])if(!B[c.x-j][c.y]c.x-j1){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.z1)for(ll j1;j3;j)if(D[c.x][c.y][c.z]1D[c.x][c.yj][c.z])if(!B[c.x][c.yj]c.yjm){D[c.x][c.yj][c.z]D[c.x][c.y][c.z]1;Q.push({c.x,c.yj,c.z});}elsebreak;if(c.z2)for(ll j1;j3;j)if(D[c.x][c.y][c.z]1D[c.xj][c.y][c.z])if(!B[c.xj][c.y]c.xjn){D[c.xj][c.y][c.z]D[c.x][c.y][c.z]1;Q.push({c.xj,c.y,c.z});}elsebreak;if(c.z3)for(ll j1;j3;j)if(D[c.x][c.y][c.z]1D[c.x][c.y-j][c.z])if(!B[c.x][c.y-j]c.y-j1){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]1D[c.x][c.y][(c.zj4)%4]){Q.push({c.x,c.y,(c.zj4)%4});D[c.x][c.y][(c.zj4)%4]D[c.x][c.y][c.z]1;}}cout-1;return0;}