1141: [递归深入]涵涵的小棋盘

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:84 Solved:18

Description

涵涵有一个棋盘,共有m行和n列,一只棋子从左上角开始,向右下角移动,每次只能向下或向右移动一次。然后这个棋盘中有一些障碍物,这些障碍物使得这个棋子不能进入这些格子,问这个棋子从左上角到达右下角共有多少种不同的移法?

如果到达不了,则输出0。

Input

第1行:两个整数m,n(0<m,n≤2 0);
后面有m行,每行n个数(0或1),如果是1,则表示这个方格中有障碍物。

Output

求得的方案数。

Sample Input Copy

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

Sample Output Copy

3

HINT

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

Source/Category