【洛谷 P1141】01迷宫 题解（深度优先搜索+记忆化搜索+位集合）

本文主要是介绍【洛谷 P1141】01迷宫 题解（深度优先搜索+记忆化搜索+位集合），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01迷宫

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

2 2
01
10
1 1
2 2

样例输出 #1

4
4

提示

对于样例，所有格子互相可达。

• 对于 $20\%$ 的数据，$n\le 10$；
• 对于 $40\%$ 的数据，$n\le 50$；
• 对于 $50\%$ 的数据，$m\le 5$；
• 对于 $60\%$ 的数据，$n,m\le 100$；
• 对于 $100\%$ 的数据，$1\le n\le 1000$，$1\le m\le 100000$。

---

思路

首先，定义几个全局变量，包括迷宫的大小 n，查询次数 m，迷宫 ch，结果 ans，以及标记访问状态的 vis。其中，ans 用来存储每个格子可以到达的格子数量，vis 用来标记每个格子是否已经被访问过。此外，定义了一个结构体 P 来表示方向，以及一个数组 dir 来存储四个可能的移动方向。

在 main 函数中，首先读取迷宫的大小 n 和查询次数 m。然后，读取迷宫，并将 ans 初始化为 -1，表示尚未计算过结果。

接着，对每一个查询，首先读取查询的格子坐标 x 和 y。如果 ans[x][y] 不为 -1，表示已经计算过结果，直接输出结果。否则，调用 init 函数重置 vis，然后调用 dfs 函数从 (x, y) 开始进行深度优先搜索。

在 dfs 函数中，首先检查当前格子 x, y 是否已经被访问过，如果已经被访问过，直接返回 false。然后，检查 ans[x][y] 是否不为 -1，如果不为 -1，表示已经计算过结果，将结果的坐标存入 r，并返回 true。否则，将当前格子标记为已访问，并对四个方向进行遍历。如果相邻的格子在迷宫内，且与当前格子的数字不同，那么对相邻的格子进行深度优先搜索。如果搜索返回 true，那么停止搜索并返回 true。否则，继续搜索。如果四个方向都搜索完毕，返回 false。

回到 main 函数，如果 dfs 返回 true，那么 ans[x][y] 就是 ans[r.x][r.y]。否则，对 vis 进行统计，得到 ans[x][y]。最后，输出 ans[x][y]。

注意

记忆化搜索是一种优化技术，可以将已经计算过的结果存储起来，避免重复计算。需要使用记忆化搜索优化，否则部分测试点报超时。

---

AC代码

#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>using namespace std;
using ll = long long;const int N = 1e3 + 7;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;struct P {ll x, y;
};
const P dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};ll n, m;
char ch[N][N];
ll ans[N][N];
P r;
bitset<N> vis[N];void init() {for (int i = 1; i <= n; i++) {vis[i].reset();}
}bool dfs(ll x, ll y) {ll cnt = 0;if (vis[x][y]) {return false;}if(~ans[x][y]) {r = {x, y};return true;}vis[x][y] = 1;cnt++;for (int i = 0; i < 4; i++) {ll xx = x + dir[i].x;ll yy = y + dir[i].y;if (xx < 1 || xx > n || yy < 1 || yy > n || ch[xx][yy] == ch[x][y]) {continue;}bool ret = dfs(xx, yy);if(ret) {return true;}}return false;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(ans, -1, sizeof(ans));cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> ch[i][j];}}for (int i = 1; i <= m; i++) {ll x, y;cin >> x >> y;if(!~ans[x][y]) {init();bool ret = dfs(x, y);if(ret) {ans[x][y] = ans[r.x][r.y];} else {ans[x][y] = 0;for(int i = 1; i <= n; i++) {ans[x][y] += vis[i].count();}}}cout << ans[x][y] << "\n";}return 0;
}

这篇关于【洛谷 P1141】01迷宫 题解（深度优先搜索+记忆化搜索+位集合）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---