题目描述

乐乐有一个棋盘，共有 m 行 n 列，一只棋子从左上角开始，向右下角移动，每次只能向下或向右移动一次。

然而这个棋盘中有一些障碍物，这些障碍物使得这个棋子不能进入这些格子，问这个棋子从左上角到达右下角共有多少种不同的移法？如果到达不了，则输出 0 。

输入格式

第一行：两个整数 m，n (0 < m，n <= 100)

后面有 m 行，每行有 n 个数( 0 或 1 )，如果是 1 ，则表示这个方格中有障碍物。

数据范围

对于 80% 的数据，0 < m ，n < 20 ；

对于 100% 的数据，0 < m，n ≤ 100 。

输出格式

求得的方案数。

样例

4 5
0 0 1 0 0
0 1 0 0 0
0 0 0 0 0
0 1 0 0 0

3

3 3
1 0 1
1 1 0
0 0 0

0

完善程序

#include<bits/stdc++.h>
using namespace std;
long long dp[101][101];
int x[101][101];
int main()
{
	int n,m,i,j;

	scanf("%d%d",&m,&n);

	for(i=1;i<=m;i++)  
		for(j=1;j<=n;j++)
			scanf("%d",&x[i][j]);
	
	dp[0][1] = 填空(1);
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			if(x[i][j]==0)
				dp[i][j] = 填空(2);
			else
				dp[i][j] = 填空(3);
		}
	
	printf("%lld",填空(4));

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}