[Daimayuan] 走不出的迷宫（C++，图论，DP）

有一个 $H$ 行 $W$ 列的迷宫（行号从上到下是 $1-H$，列号从左到右是 $1-W$），现在有一个由 . 和 # 组成的 H 行 W 列的矩阵表示这个迷宫的构造，. 代表可以通过的空地，# 代表不能通过的墙。

现在有个人从 起点 $(1,1)$ 开始走，他每一步只能往右走一格或者往下走一格，并且他不能跨越迷宫的边界。他会一直走，直到没有可以走的路时停下来。

请问这个人最多可以经过多少个格子？

输入格式

第一行两个整数 $H$，$W$，表示迷宫有 $H$ 行 $W$ 列。

接下来一个 $H$ 行 $W$ 列的由 . 和 # 组成的矩阵，表示迷宫的构造。

注意：保证 $(1,1)$ 的位置一定是 .。

输出格式

一个整数，表示最多步数。

样例输入1

3 4
.#..
..#.
..##

样例输出1

4

样例输入2

1 1
.

样例输出2

1

样例输入3

5 5
.....
.....
.....
.....
.....

样例输出3

9

数据规模

对于全部数据保证 $1\le H,W\le 100$

解题思路

主体思路为动态规划，时间复杂度为$O(H\ast W)$。

由题意可知，我们到达一个格子的方式只有从左边和上边到达两种情况，那么我们就继承这两种情况中步数更多的一种$+1$来更新：

sum[i][j] = max(sum[i - 1][j], sum[i][j - 1]) + 1;

采用二重循环遍历整张图，由循环顺序，显而易见：在我们到达(i, j)之前，已经到达了(i - 1, j)和(i, j - 1)。

for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {sum[i][j] = max(sum[i - 1][j], sum[i][j - 1]) + 1;}
}

但是需要注意两点：

（1）注意障碍物的存在，以下代码采用的方式是掩码把墙的sum置为$0$；

（2）注意寻找最大步数时还需要进行一次$BFS$，因为我们可能到达不了某些格子，从而导致我们得到的答案并不是sum数组中的最大值。

AC代码如下：

#include <iostream>
#include <queue>
using namespace std;
const int max_h = 100;
const int max_w = 100;bool map[max_h + 1][max_w + 1], book[max_h][max_w];
long long sum[max_h + 1][max_w + 1];
long long h, w, ans = 1;
struct node { int x, y; };
queue<node>q;inline void read() {string str;cin >> h >> w;for (int i = 1; i <= h; i++) {cin >> str;for (int j = 1; j <= w; j++) {if (str[j - 1] == '.') map[i][j] = true;else map[i][j] = false;}}
}void bfs() {q.push(node{ 1,1 });book[1][1] = true;int step[2][2] = { {1,0}, {0,1} }, temp_x, temp_y;while (!q.empty()) {node temp = q.front(); q.pop();for (int i = 0; i < 2; i++) {temp_x = step[i][0] + temp.x;temp_y = step[i][1] + temp.y;if (temp_x > h || temp_y > w) continue;if (!map[temp_x][temp_y]) continue;if (book[temp_x][temp_y]) continue;q.push(node{ temp_x,temp_y });book[temp_x][temp_y] = true;ans = max(ans, sum[temp_x][temp_y]);}}
}inline void solve() {for (int i = 1; i <= h; i++) {for (int j = 1; j <= h; j++) {sum[i][j] = max(sum[i - 1][j] * map[i - 1][j],sum[i][j - 1] * map[i][j - 1]) + 1;}}bfs();cout << ans << endl;
}int main() {read();solve();return 0;
}

免费商用字体