A25 - Number of Routes
Editorial
/ 
/ 
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
縦 H 行、横 W 列のマス目があります。
上から i 行目・左から j 列目のマス (i, j) は色 c_{i, j} で塗られています。
ここで c_{i, j} が . ならば白、c_{i, j} が # ならば黒を意味します。
マス (1, 1) から出発し、右方向または下方向の移動のみを繰り返して、マス (H, W) まで行く方法は何通りありますか。
ただし、黒いマスを通ることはできないものとします。
制約
- 2 \leq H \leq 30
- 2 \leq W \leq 30
- c_{i, j} は
.または#である - c_{1, 1} は
.である - c_{H, W} は
.である
入力
入力は以下の形式で標準入力から与えられます。
H W
c_{1,1}c_{1,2}\cdotsc_{1,W}
c_{2,1}c_{2,2}\cdotsc_{2,W}
:
c_{H,1}c_{H,2}\cdotsc_{H,W}
出力
何通りの移動方法があるか、整数で出力してください。
入力例 1
4 8 .....#.. ........ ..#...#. #.......
出力例 1
35
入力例 2
2 8 ....#... ....#...
出力例 2
0
入力例 3
30 30 .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. ..............................
出力例 3
30067266499541040