【BFS】01迷宫

题目

P1141 01迷宫

---

题目描述

有一个仅由数字$0$与$1$组成的$n \times n$格迷宫。若你位于一格$0$上，那么你可以移动到相邻$4$格中的某一格$1$上，同样若你位于一格$1$上，那么你可以移动到相邻$4$格中的某一格$0$上。

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

输入格式

第$1$行为两个正整数$n,m$。

下面$n$行，每行$n$个字符，字符只可能是$0$或者$1$，字符之间没有空格。

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

输出格式

$m$行，对于每个询问输出相应答案。

样例 #1

样例输入 #1

2 2
01
10
1 1
2 2

样例输出 #1

4
4

提示

所有格子互相可达。

对于$20\%$的数据，$n≤10$；

对于$40\%$的数据，$n≤50$；

对于$50\%$的数据，$m≤5$；

对于$60\%$的数据，$n≤100,m≤100$；

对于$100\%$的数据，$n≤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;
}