侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 655 篇文章
  • 累计创建 127 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】01迷宫

GabrielxD
2022-12-19 / 0 评论 / 0 点赞 / 45 阅读 / 832 字
温馨提示:
本文最后更新于 2022-12-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1141 01迷宫


题目描述

有一个仅由数字0011组成的n×nn \times n格迷宫。若你位于一格00上,那么你可以移动到相邻44格中的某一格11上,同样若你位于一格11上,那么你可以移动到相邻44格中的某一格00上。

你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。

输入格式

11行为两个正整数n,mn,m

下面nn行,每行nn个字符,字符只可能是00或者11,字符之间没有空格。

接下来mm行,每行22个用空格分隔的正整数i,ji,j,对应了迷宫中第ii行第jj列的一个格子,询问从这一格开始能移动到多少格。

输出格式

mm行,对于每个询问输出相应答案。

样例 #1

样例输入 #1

2 2
01
10
1 1
2 2

样例输出 #1

4
4

提示

所有格子互相可达。

对于20%20\%的数据,n10n≤10

对于40%40\%的数据,n50n≤50

对于50%50\%的数据,m5m≤5

对于60%60\%的数据,n100,m100n≤100,m≤100

对于100%100\%的数据,n1000,m100000n≤1000,m≤100000

解题

方法一:记忆化BFS

思路

按照题目要求对每个查询点进行 BFS 并统计步数。

但这样做一旦点足够多便会超时。我们发现 BFS 某个点时「经过的点能走的步数」其实与该点能走的步数是相同的(类似于并查集中点的合并),那么我们在 BFS 的过程中记录经过的点,在最后一齐更新所有点的步数即可。对于每个查询,如果其步数在 memos 查得到便可以直接取出来用,否则再去 BFS 走一遍。

代码

#include <iostream>
#include <limits>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m;
bool g[N][N], vis[N][N];
int memos[N][N];
queue<PII> que;

int bfs(int x, int y) {
    que.push({x, y});
    vis[x][y] = true;
    int step = 1;
    vector<PII> seen;
    while (!que.empty()) {
        auto pr = que.front();
        que.pop();
        int x = pr.first, y = pr.second;
        bool curr = g[x][y];
        for (auto& DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            if (nx > 0 && nx <= n && ny > 0 && ny <= n && !vis[nx][ny] && g[nx][ny] != curr) {
                que.push({nx, ny});
                vis[nx][ny] = true;
                ++step;
                seen.push_back({nx, ny});
            }
        }
    }
    for (auto& pr : seen) memos[pr.first][pr.second] = step;
    memos[x][y] = step;
    return step;
}

int main() {
    memset(memos, -1, sizeof(memos));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        for (int j = 1; j <= n; ++j) {
            char c;
            scanf("%c", &c);
            g[i][j] = c - '0';
        }
    }
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (!~memos[x][y]) bfs(x, y);
        printf("%d\n", memos[x][y]);
    }

    return 0;
}
0

评论区