[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;
}