TopCoder

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

13.4% (9/67)

Tags

Description

失落的遺跡之中,有一個充滿陷阱的迷宮,在迷宮的終點藏有價值連城的寶藏,這個迷宮十分的脆弱,每一個地磚只能踩在上面一小段時間,所以規劃一個安全的路線是十分重要的,你將會得到一個空拍機從天空拍迷宮的照片,請你規劃一條沒有重複踩到的路線,取得寶藏吧!

Input Format

輸入有 $n+1$ 行,第一行包含兩個整數 $n,m$ 代表接下來地圖的長與寬

接下來的 $n$ 行會有 0,1,2,3 這四種數字:

0 代表可以走的地方, 1 代表不能走的牆壁, 2 代表起點, 3 代表終點

$3\le n,m \le 50$

Output Format

若得到的路徑長度為 $l$ ,則輸出 $l+1$ 行,第一行只有一格數字 $l$ 代表路徑長度

其餘每行包含兩個數字 $x$ 跟 $y$ 代表路徑上的座標,以空格分隔,座標由 0 開始標

輸出路徑包含起終點,並且每個踩過的座標都要輸出 (2 3=>3 2 不合格, 2 3=>3 3=>3 2 合格 )

若不幸沒辦法走到寶藏之地,請輸出 0 並換行。

Sample Input 1

5 5
1 1 1 1 1
1 0 1 0 1
1 0 2 1 1
1 0 0 3 1
1 1 1 1 1

Sample Output 1

3
2 2
3 2
3 3

Sample Input 2

5 10
1 1 1 1 1 1 1 1 1 1
1 2 1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 0 3 1
1 0 0 0 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1

Sample Output 2

15
1 1
2 1
3 1
3 2
3 3
2 3
1 3
1 4
1 5
2 5
3 5
3 6
3 7
2 7
2 8

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2