TopCoder

Thumb 100
Motivation
https://www.youtube.com/playlist?list=PL0srVz2dbivUrw6S1p2wr8o0wmh0V9EJc

User's AC Ratio

40.0% (2/5)

Submission's AC Ratio

4.9% (2/41)

Description

你有玩過類似上圖的走迷宮遊戲嗎?

這種遊戲很困難,只要稍微不注意就會遇到下面這種情形

通常面對這種問題,可以使用著名的BFS或是DFS來解決。

不過這題不用這麼麻煩,

現在給你一個由斜線組成的更有趣迷宮,

請問你有多少條路徑可以從最上面走到最下面呢?

(請參照範例測資)

Input Format

本題只有一筆測資:

第一行包含兩個正整數 m, n ,代表迷宮的寬跟長

接下來有 n 行,每行有 m 個字元,代表迷宮的牆壁
(只可能有’/’以及’\’兩種字元)

( n ,m <= 4000 )

Output Format

請輸出你有多少條路徑可以從最上面走到最下面。

若不存在任何一條路徑,請輸出”I can't escape.”(不含雙引號)

Sample Input

3 3
///
\\\
///

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11