p1126

题解

机器人是一个直径1.6米的球，其中心必须位于格点上，且距离障碍物和边界至少0.8米（半径）。因此，机器人的中心只能位于满足以下条件的格子上：

• 该格子不在边界上（即行号在1到N-2之间，列号在1到M-2之间）。
• 以该格子为中心的3×3区域内（共9个格子）均无障碍物。

机器人的状态包括位置（行、列）和朝向（东、南、西、北）。每个指令（前移1/2/3步、左转、右转）耗时1秒。使用BFS（广度优先搜索）求解从起点到终点的最少时间，因为BFS天然适合求解无权图的最短路径。

步骤

1. 输入处理：读取网格大小N、M，网格数据，起点、终点坐标及初始朝向。
2. 预处理有效位置：计算每个格子是否可作为机器人中心（valid数组）。
3. 起点终点检查：若起点或终点位置无效，直接输出-1。
4. BFS初始化：起点状态（位置、朝向）入队，距离数组初始化。
5. BFS过程：
   • 检查当前状态是否到达终点，若是则输出当前时间。
   • 尝试5种指令：
     • 左转/右转：改变朝向，位置不变。
     • 前移1/2/3步：沿当前朝向移动k步，需检查路径上每一步的位置是否有效（在网格内且valid为真）。
   • 更新新状态的距离并入队。
6. 结果处理：BFS结束后，若未到达终点，输出-1。

代码实现

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAXN = 55;
const int INF = INT_MAX;
int grid[MAXN][MAXN];
bool valid[MAXN][MAXN];
int dist[MAXN][MAXN][4]; // 0:E, 1:S, 2:W, 3:N
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> grid[i][j];
        }
    }

    memset(valid, false, sizeof(valid));
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < M - 1; j++) {
            bool flag = true;
            for (int x = i - 1; x <= i + 1; x++) {
                for (int y = j - 1; y <= j + 1; y++) {
                    if (grid[x][y] == 1) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) break;
            }
            valid[i][j] = flag;
        }
    }

    int sx, sy, tx, ty;
    char dir_char;
    cin >> sx >> sy >> tx >> ty >> dir_char;
    sx--; sy--; tx--; ty--;

    if (sx < 0 || sx >= N || sy < 0 || sy >= M || tx < 0 || tx >= N || ty < 0 || ty >= M ||
        !valid[sx][sy] || !valid[tx][ty]) {
        cout << -1 << endl;
        return 0;
    }

    int sd;
    if (dir_char == 'E') sd = 0;
    else if (dir_char == 'S') sd = 1;
    else if (dir_char == 'W') sd = 2;
    else if (dir_char == 'N') sd = 3;
    else sd = 0; // 默认情况，理论上不会发生

    memset(dist, 0x3f, sizeof(dist));
    queue<tuple<int, int, int>> q;
    dist[sx][sy][sd] = 0;
    q.push(make_tuple(sx, sy, sd));

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = get<0>(cur);
        int y = get<1>(cur);
        int d = get<2>(cur);
        int cur_time = dist[x][y][d];

        if (x == tx && y == ty) {
            cout << cur_time << endl;
            return 0;
        }

        // Left turn
        int nd = (d + 3) % 4;
        if (dist[x][y][nd] > cur_time + 1) {
            dist[x][y][nd] = cur_time + 1;
            q.push(make_tuple(x, y, nd));
        }

        // Right turn
        nd = (d + 1) % 4;
        if (dist[x][y][nd] > cur_time + 1) {
            dist[x][y][nd] = cur_time + 1;
            q.push(make_tuple(x, y, nd));
        }

        // Move: creep (1), walk (2), run (3)
        for (int k = 1; k <= 3; k++) {
            int nx = x + k * dx[d];
            int ny = y + k * dy[d];
            bool can_move = true;

            for (int step = 1; step <= k; step++) {
                int cx = x + step * dx[d];
                int cy = y + step * dy[d];
                if (cx < 0 || cx >= N || cy < 0 || cy >= M) {
                    can_move = false;
                    break;
                }
                if (!valid[cx][cy]) {
                    can_move = false;
                    break;
                }
            }

            if (!can_move) continue;
            if (dist[nx][ny][d] > cur_time + 1) {
                dist[nx][ny][d] = cur_time + 1;
                q.push(make_tuple(nx, ny, d));
            }
        }
    }

    int ans = INF;
    for (int d = 0; d < 4; d++) {
        ans = min(ans, dist[tx][ty][d]);
    }
    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

复杂度分析

• 时间复杂度：
  预处理和 BFS 均为 ，常数因子在 时可忽略。
• 空间复杂度：
  主要开销为 valid 数组和 dist 数组。

优化

• 剪枝：BFS 天然具有最短路性质，首次到达终点即是最优解，可提前终止。
• 常数优化：
  • 移动操作中，一旦路径上某位置无效，立即终止后续检查。
  • 使用数组代替 STL 容器（如 vector）存储方向偏移量，减少常数开销。
• 边界处理：预处理 valid 数组时已排除边界位置，BFS 中无需额外判断越界。