【普及-】93771题解

题意过于简单，这里不在累赘。

思路

对于大多数要求求，最多或最少，或者方案数的题都用DP（动态规划）解决。
因此考虑DP解决。

设 $dp_{i,j}$ 为第 $i$ 行第 $j$ 列不同的路径数

初始状态

第 $1$ 行第 $1$ 列，作为起始点一定有且只有一种路径（即刚开始）。也就是 $dp_{1,1} = 1$。

很明显，第 $1$ 行在第 $1$ 个障碍物之前所有的路径数也一定为 $1$。也就是 $dp_{1,j} = 1$ 其中 $j \in [1,k)$，$k$ 为第 $1$ 行第一个障碍物的位置。原因很简单，由于不能往上走，所以第 $1$ 只能一直往左走才可能到达。

同样的，第 $1$ 列在第 $1$ 个障碍物前所有的路径数一定为 $1$。也就是 $dp_{j,1} = 1$ 其中 $j \in [1,k)$，$k$ 为第 $1$ 行列第一个障碍物的位置。

动态方程

首先，障碍物无法到达，因此障碍物处的所有路径数为 $0$，也就是 $dp_{i,j} = 0$，其中 $i,j$ 是所有障碍物的行数以及列数。

对于非障碍物，有两种到达方法，从它的正上方到达，和它的左边到达，因此其路径数为正上方与左边的路径数之和。即 $dp_{i,j} = dp_{i - 1,j} + dp_{i , j- 1}$ 其中 $i,j$ 分别为大于1的所有非障碍物坐标。

因此我们得出代码：

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const int MOD = 1e9 + 7;
int dp[N][N] , w , h ;
char ma[N][N];
signed main(){
	cin >> h >> w;
	for(int i = 1;i <= h;i ++){
		for(int j = 1;j <= w;j ++) cin >> ma[i][j];
	}
	for(int i = 1;i <= h;i ++){
		dp[i][1] = 1;
	}for(int j = 1;j <= w;j++) dp[1][j] = 1;
	for(int i = 2;i <= h;i ++){
		for(int j = 2;j <= w;j ++){
			if(ma[i][j] == '.'){
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
	}
	for(int i = 1;i <= h;i ++){
		for(int j = 1;j <+ w;j ++){
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}抄代码私募
	cout << dp[i][j];
	return 0;
}