P1126 机器人搬重物

网页链接

P1126 机器人搬重物

题目描述

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

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

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

输入格式

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

输出格式

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出 $-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

12

解题思路

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

1. 问题等价转化

• 机器人占据的格子：设中心位于格点 $(i,j)$（$1\le i<N,1\le j<M$），则机器人覆盖的四个格子为 $(i,j),(i+1,j),(i,j+1),(i+1,j+1)$。只要这四个格子中任意一个为障碍（值为 $1$），该中心点就不可用。
• 因此，可以预处理一个二维布尔数组 B[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)$ 和当前朝向 $dir$ 组成。朝向用 $0\sim 3$ 表示：$0$ 北，$1$ 东，$2$ 南，$3$ 西。
• 移动规则：
  • 向前移动 $1$、$2$ 或 $3$ 步，每步都必须检查新位置的 B 是否为假（可行）。若某一步不可行，则更远的步数也必然不可行，可直接 break。
  • 左转或右转：改变朝向，耗时 $1$ 秒，位置不变。
• 目标：到达终点 $(E1,E2)$，朝向任意，求最小耗时。

2. 算法实现（BFS）

1. 预处理：
   • 读入 $N,M$ 和障碍矩阵 $A$。
   • 构建 B[i][j]，其中 $i$ 从 $1$ 到 $N-1$，$j$ 从 $1$ 到 $M-1$。
2. 初始化：
   • 读入起点 $(S1,S2)$、终点 $(E1,E2)$ 和初始朝向字符。
   • 将字符转换为方向编号 d：N->0, E->1, S->2, W->3。
   • 距离数组 D[x][y][dir] 初始化为极大值，D[S1][S2][d] = 0。
   • 将初始状态入队。
3. BFS 过程：
   • 从队列取出状态 $(x,y,dir)$。
   • 若 $(x,y)=(E1,E2)$，直接输出 D[x][y][dir] 并结束。
   • 前进：根据当前朝向 dir，确定移动方向向量。例如：
     • 北：$x$ 减少，$y$ 不变；
     • 东：$y$ 增加，$x$ 不变；
     • 南：$x$ 增加，$y$ 不变；
     • 西：$y$ 减少，$x$ 不变。
       循环步数 $step=1\sim 3$：
     • 计算新坐标 $(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。若距离可更新，则更新并入队。
4. 输出：若队列空仍未到达，输出 -1。

3. 复杂度分析

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

总结

本题的关键在于正确理解机器人占据的 $2\times 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\sim 3$ 步，检查 B 并更新距离。
  • 处理转向：左转 (z+3)%4，右转 (z+1)%4，耗时 $1$ 秒。
• 输出：若队列空仍未到达，输出 -1。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

bool A[55][55],B[55][55];
ll n,m,D[55][55][5],S1,S2,E1,E2;
char W;
struct Node
{
    ll x,y,z;
    Node(ll a,ll b,ll c):x(a),y(b),z(c){}
};
queue<Node> Q;

int main()
{
    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];
            return 0;
        }
        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});
                    }
                    else break;
        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});
                    }
                    else break;
        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});
                    }
                    else break;
        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});
                    }
                    else break;
        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;
    return 0;
}