算法
(坐标型dp) $O(HW)$
可以考虑从右下角开始向左上方走
记 dp[i][j]
表示到达点 $(i, j)$ 之时所走的最大步数
转移方程:
$$ dp[i][j] = \max(dp[i+1][j], dp[i][j+1]) + 1 $$
最后的答案就是 $dp[1][1]$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
vector dp(h, vector<int>(w));
for (int i = h-1; i >= 0; --i) {
for (int j = w-1; j >= 0; --j) {
if (s[i][j] == '#') continue;
dp[i][j] = 1;
if (i+1 < h) chmax(dp[i][j], dp[i+1][j] + 1);
if (j+1 < w) chmax(dp[i][j], dp[i][j+1] + 1);
}
}
cout << dp[0][0] << '\n';
return 0;
}