分数:75

题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。



输入
先输入n和m代表地图为n*m（n,m<=100)

再输入一个二维数组来表示地图。

输出
有多少条路径

样例输入
3 3
0 0 0
0 1 0
0 0 0
样例输出
2

#include <iostream>
using namespace std;
int m; int n; int a[101][101]; int DP[101][101];
int main(){
	cin >> m; cin >> n;
	for(int i = 1; i < m + 1; ++ i) { for(int j = 1; j < n + 1; ++ j) { cin >> a[i][j]; } }
	for(int i = 1; i < m + 1; ++ i) { for(int j = 1; j < n + 1; ++ j) {
		if(i == 1 or j == 1){ if(not a[i][j]) { DP[i][j] = 1; continue; } }
		if(a[i][j]) { DP[i][j] = 0; continue; }
//		else { DP[i][j] = DP[i - 1][j] + DP[i][j - 1]; }
		else {
			if(i - 1 == 0 and j - 1 == 0) { DP[i][j] = 0; }
			else if(i - 1 == 0) { DP[i][j] = DP[i][j - 1]; }
			else if(j - 1 == 0) { DP[i][j] = DP[i - 1][j]; }
			else { DP[i][j] = DP[i - 1][j] + DP[i][j - 1]; }
	} } }
	cout << DP[m][n] << '\n';
}