10021. Walking on the Safe Side

I'm a slow walker, but I never walk backwards.

背景

等這題 AC 後,我準備要回故鄉結婚等這題 AC 後,我準備要回故鄉結婚

題目描述

給一個 $N \times M$ 網格,要從左上角走到右下角,每一步只能往下或往右,有些格子有障礙物,無法經過障礙物的格子,請問有多少種方法數。

輸入格式

有多組測資,每一組第一行會有兩個整數 $N, M$,接下來會有 $N$ 行,每一行上會有 $M$ 個整數,表示座標 $(i, j)$ 上是否有障礙物,用 $1$ 表示有障礙物。

  • $1 \le N, \; M \le 100$

輸出格式

每一組測資輸出一行,輸出方法數 $S \mod 10000$ 的結果。

範例輸入

5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
6 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
6 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0

範例輸出

70
2
8

提示

高中排列組合之填表計數

Discussion