1442 . 迷宮問題
TopCoder
Tags
Description
你有玩過類似上圖的走迷宮遊戲嗎？
這種遊戲很困難，只要稍微不注意就會遇到下面這種情形
通常面對這種問題，可以使用著名的BFS或是DFS來解決。
不過這題不用這麼麻煩，
現在給你一個由斜線組成的更有趣迷宮，
請問你有多少條路徑可以從最上面走到最下面呢？
（請參照範例測資）
Input Format
本題只有一筆測資：
第一行包含兩個正整數 m, n ，代表迷宮的寬跟長
接下來有 n 行，每行有 m 個字元，代表迷宮的牆壁
（只可能有’/’以及’\’兩種字元）
( n ,m <= 4000 )
Output Format
請輸出你有多少條路徑可以從最上面走到最下面。
若不存在任何一條路徑，請輸出”I can't escape.”（不含雙引號）
Sample Input 1
3 3
///
\\\
///
///
\\\
///
Sample Output 1
2
Hints
以範例測資來說，
從上面第一條跟上面第二條之間以及上面第二條跟上面第三條之間各有一條路徑可以通到最下面
※2008/10/08 測資範圍修正 by peter50216。
Problem Source
原TIOJ1442 / 建中校內培訓第一次模擬考試。
Problem Setter：hallogameboy、peter50216
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |