Labyrinth｜MGblog

题目：Labyrinth

题目描述：
你正在玩一款电脑游戏。在其中一关，你位于一个 n 行 m 列的迷宫。每个格子要么是可以通过的空地，要么是障碍。迷宫的起点位于第 r 行第 c 列。你每一步可以向上、下、左、右中的一个方向移动一格，前提是那一格不是障碍。你无法越出迷宫的边界。不幸的是，你的键盘快坏了，所以你只能向左移动不超过 x 格，并且向右移动不超过 y 格。因为上下键情况良好，所以对向上和向下的移动次数没有限制。现在你想知道在满足上述条件的情况下，从起点出发，有多少格子可以到达（包括起点）。

输入描述：

第一行：两个整数 n 和 m（1 \leq n, m \leq 2000），表示迷宫的行数和列数。
第二行：两个整数 r 和 c（1 \leq r \leq n, 1 \leq c \leq m），表示起点位于第 r 行第 c 列。
第三行：两个整数 x 和 y（1 \leq x, y \leq 10^9），表示最多向左或向右移动的次数。
接下来 n 行：每行为一个长为 m 的由 . 和 * 组成的字符串。. 表示空地，* 表示障碍。输入保证起点不是障碍。

输出描述：
输出一个整数，表示从起点出发可以到达的格子数，包括起点本身。

样例输入：

4 5
3 2
1 2
.....
.***.
...**
*....

样例输出：

题目简化大意：
从迷宫中的一个起点出发，满足左右移动次数的限制，计算能到达的格子数。

思路：双端队列优化的广搜（BFS）

用 BFS 算法进行广度优先搜索，起点入队。
双端队列用于保证尽量优先扩展不需要左右移动的方向（上下移动），以减少左右移动的代价。
记录每个点到达时的左右移动次数，若左右移动次数不超过限制，继续扩展。
最终统计所有可达格子的数量。

AC代码：

#include<bits/stdc++.h>
#define N 1001
using namespace std;
int n, m, r, c, kx, ky, vis[N][N], step[N][N], cnt;
char a[N][N];
int dx[] = {0, 1, -1, 0};
int dy[] = {0, 0, 0, -1, 1};
deque<int> q, q2, q3, q4;

void bfs(int x, int y) {
    q.push_front(x);
    q2.push_front(y);
    q3.push_front(kx);
    q4.push_front(ky);
    while (!q.empty()) {
        int xx = q.back(), yy = q2.back(), fx = q3.back(), fy = q4.back();
        q.pop_back(); q2.pop_back(); q3.pop_back(); q4.pop_back();
        cnt++;
        for (int i = 1; i <= 4; i++) {
            int nx = xx + dx[i], ny = yy + dy[i];
            if (nx > 0 && nx <= n && ny > 0 && ny <= m && a[nx][ny] == '.' && !vis[nx][ny]) {
                if (i == 3 && fx > 0) {
                    vis[nx][ny] = 1;
                    step[nx][ny] = step[xx][yy] + 1;
                    q.push_front(nx); q2.push_front(ny); q3.push_front(fx - 1); q4.push_front(fy);
                } else if (i == 4 && fy > 0) {
                    vis[nx][ny] = 1;
                    step[nx][ny] = step[xx][yy] + 1;
                    q.push_front(nx); q2.push_front(ny); q3.push_front(fx); q4.push_front(fy - 1);
                } else if (i == 1 || i == 2) {
                    vis[nx][ny] = 1;
                    step[nx][ny] = step[xx][yy] + 1;
                    q.push_back(nx); q2.push_back(ny); q3.push_back(fx); q4.push_back(fy);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    cin >> r >> c;
    cin >> kx >> ky;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    step[r][c] = 1;
    vis[r][c] = 1;
    bfs(r, c);
    cout << cnt;
    return 0;
}

时间复杂度: O(n \times m)
空间复杂度: O(n \times m)

Labyrinth

题目：Labyrinth

热门文章