Description

丽萨参加了一个攀岩比赛，她想知道从起点到终点有多少种走法。 现在给你岩壁图，用1和0表示，其中1表示岩壁的那一处突出一块大石头，丽萨没办法从那里通过，0表示能够顺利爬过去。 丽萨只能往左爬或往上爬。 起点是在最右下角的岩壁旁的地面，丽萨只能从最右下角开始往岩壁上爬，终点是在最左上角的岩壁。 你现在需要写出一个程序统计出丽萨有多少种走法。

Input Format

第一行整数m和n，分别表示岩壁图的行数和列数，m和n的值均不超过100； 后面m行每行n个整数；

Output Format

一个整数，表示有多少种走法

3 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0​

6​

Source

动态规划