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

解释

难点一：格点 vs 格子（坐标系处理）

题目输入的是N×M的方格（Cells），有障碍物的地方是 1。
但是，题目说机器人是走在**格点（Intersections/Grid lines）**上的。

N行M列的格子，实际上只有(N − 1) × (M − 1)个可走的内部交叉点。

边界判断：nx < 1 || nx >= N || ny < 1 || ny >= M （有效坐标范围是 1 到 N − 1，1 到 M − 1）。

难点二：胖机器人（预处理地图）

机器人是有体积的（占 2×2 个格子）。
如果把机器人看作一个质点（比如看作机器人的左上角坐标 (r,c)），那么只有当该点右下方的 4 个格子[(r,c)，(r,c + 1)，(r + 1,c)，(r + 1,c + 1)全都是空地(0)]时，这个点才是合法的。

难点三：状态定义（三维数组）

普通的迷宫只需要记录 visited[x][y]。
但这道题中，“在 (x,y) 面向北”和“在 (x,y) 面向东”是两种完全不同的状态。因为转向需要消耗时间，且不同朝向能去的下一步不同。

AC代码

#include<bits/stdc++.h>
using namespace std;
 
struct Pos
{
    int x;
    int y;
    int Dir;
    int time;
};
 
int N,M;
constexpr int MAXNUM = 55;
vector<vector<int>> Grid;
vector<vector<bool>> CanGo;
int visited[MAXNUM][MAXNUM][4];
int Sx,Sy,Ex,Ey;
int sDir;
 
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
 
int bfs()
{
    queue<Pos> Q;
    Q.push({Sx,Sy,sDir,0});
    visited[Sx][Sy][sDir] = 0;
    while (!Q.empty())
    {
        Pos cur = Q.front();
        Q.pop();
 
        if (cur.x == Ex && cur.y == Ey)
        {
            return cur.time;
        }
 
        // 直行
        for (int i = 1;i <= 3;i++)
        {
            int nx = cur.x + dx[cur.Dir] * i;
            int ny = cur.y + dy[cur.Dir] * i;
 
            if (nx < 1 || nx >= N || ny < 1 || ny >= M)
            {
                break;
            }
 
            if (!CanGo[nx][ny])
            {
                break;
            }
 
            if (visited[nx][ny][cur.Dir] == -1)
            {
                visited[nx][ny][cur.Dir] = cur.time + 1;
                Q.push({nx,ny,cur.Dir,cur.time + 1});
            }
        }
 
        // 左转
        int leftDir = (cur.Dir + 3) % 4;
        if (visited[cur.x][cur.y][leftDir] == -1)
        {
            visited[cur.x][cur.y][leftDir] = cur.time + 1;
            Q.push({cur.x,cur.y,leftDir,cur.time + 1});
        }
 
        // 右转
        int rightDir = (cur.Dir + 1) % 4;
        if (visited[cur.x][cur.y][rightDir] == -1)
        {
            visited[cur.x][cur.y][rightDir] = cur.time + 1;
            Q.push({cur.x,cur.y,rightDir,cur.time + 1});
        }
    }
 
    return -1;
}
 
int main()
{
    cin >> N >> M;
    Grid.resize(N + 1,vector<int>(M + 1));
    CanGo.resize(N + 1,vector<bool>(M + 1));
 
    for (int i = 1;i <= N;i++)
    {
        for (int j = 1;j <= M;j++)
        {
            cin >> Grid[i][j];
        }
    }
 
    for (int i = 1;i < N;i++)
    {
        for (int j = 1;j < M;j++)
        {
            if (Grid[i][j] == 0 && Grid[i][j + 1] == 0 && Grid[i + 1][j] == 0 && Grid[i + 1][j + 1] == 0)
            {
                CanGo[i][j] = true;
            }
        }
    }
 
    char SDir;
    cin >> Sx >> Sy >> Ex >> Ey >> SDir;
    switch (SDir)
    {
        case 'N': sDir = 0; break;
        case 'E': sDir = 1; break;
        case 'S': sDir = 2; break;
        case 'W': sDir = 3; break;
        default: sDir  = -1; break;
    }
    memset(visited,-1,sizeof(visited));
 
    cout << bfs() << endl;
}