问题 25571. -- 乐乐的棋盘

25571: 乐乐的棋盘

时间限制: 1 Sec  内存限制: 128 MB
献花: 0  解决: 0
[献花][花圈]

题目描述

 

问题描述:

乐乐有一个棋盘,共有mn列,一只棋子从左上角开始,向右下角移动,每次只能向下或向右移动一次。然而这个棋盘中有一些障碍物,这些障碍物使得这个棋子不能进入这些格子,问这个棋子从左上角到达右下角共有多少种不同的移法?如果到达不了,则输出0

输入格式:

第一行两个整数mn0<mn100

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

输出格式:

求得的方案数。

输入输出样例:

样例1

样例2

输入样例

4 5

0 0 1 0 0

0 1 0 0 0

0 0 0 0 0

0 1 0 0 0

3 3

1 0 1

1 1 0

0 0 0

输出样例

3

0

数据规模

对于80%的数据,0<mn<20

对于100%的数据,0<mn100

输入

输出

提示

来源

[献花][花圈]