愛德華是個好勝的小孩子，而明天正好是他參加的一個機器人營隊的最後一天，營隊表示要舉辦一個「機器人障礙賽」來驗收大家學習的成果。
好勝的愛德華當然想勝利，他事先調查好了障礙賽會用到的地圖分布，想要試著模擬當時他要怎麼走才能最快到達終點。
首先是規則的熟讀：
1.比賽為計時制，每輪都將會有一位選手上台，將他的機器人放在迷宮指定的起點裡，並且面向終點列。
2.當大會宣布開始時即開始計時，選手的機器人必須開始試著行走，並到達指定的終點，到達後停止計時。
3.不可以破壞障礙物。
4.不可以回頭，即走過一列後，台上會有機關封鎖此列。
5.機器人的大小必須能被一格容納。
6.n=1的時候機器人一開始會面對牆壁。
愛德華現在只要模擬完策略就有87%能獲勝了，可是問題來了，要怎麼做才可以讓機器人走的最快呢？聰明的愛德華馬上就想到了一個關鍵點──轉彎！
轉彎是拖延時間的一個關鍵點，因為要在原地旋轉90度必須先停下來，慢慢轉完才可以繼續走，這樣太耗時了。
於是愛德華想要一個程式，可以快速算出從指定起點走到終點最少要轉幾次彎，請你幫幫他！
輸入首行會有兩個正整數n、m，代表地圖的大小n、m，座標範圍是(0~n-1,0~m-1)。
第二行會有兩個整數b、e，代表比賽起點的座標位於(0,b)；終點的座標位於(n-1,e)。
第三行會有一個非負整數k，代表有k個障礙物。
接下來會有k行，每行有兩個整數(xi,yi)，代表第i個障礙物的所在位置。
k＜(n-2)×m，0＜xi＜n-1，0≦b、e、yi＜m，n≦1000，m≦100。
輸入將有多筆測資，不超過5筆。
對於每組測資輸出從起點走到終點機器人最少要轉幾次彎，每組測資一行。
機器人不能往回走，因為這樣會發生不可預期的意外。
3 3 0 2 2 1 0 1 2 6 2 0 1 0
3 1
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
上圖為第一組測資的地圖，起點為A，終點為B，黑色的是障礙物，紅線即為擁有最少轉彎次數的路線。
機器人一開始固定會朝向終點列(即上圖的下方)，故一開始機器人必須還得先轉彎一次才能開始移動。
30%的測資，n、m≦10。
60%的測資，n、m≦100。
100%的測資，無特別限制。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||