c148: 機器人障礙賽
Tags :
Accepted rate : 24人/60人 ( 40% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-02-27 14:27

Content

  愛德華是個好勝的小孩子,而明天正好是他參加的一個機器人營隊的最後一天,營隊表示要舉辦一個「機器人障礙賽」來驗收大家學習的成果。

  好勝的愛德華當然想勝利,他事先調查好了障礙賽會用到的地圖分布,想要試著模擬當時他要怎麼走才能最快到達終點。

  首先是規則的熟讀:

    1.比賽為計時制,每輪都將會有一位選手上台,將他的機器人放在迷宮指定的起點裡,並且面向終點列。

    2.當大會宣布開始時即開始計時,選手的機器人必須開始試著行走,並到達指定的終點,到達後停止計時。

    3.不可以破壞障礙物。

    4.不可以回頭,即走過一列後,台上會有機關封鎖此列。

    5.機器人的大小必須能被一格容納。

    6.n=1的時候機器人一開始會面對牆壁。

  愛德華現在只要模擬完策略就有87%能獲勝了,可是問題來了,要怎麼做才可以讓機器人走的最快呢?聰明的愛德華馬上就想到了一個關鍵點──轉彎!

  轉彎是拖延時間的一個關鍵點,因為要在原地旋轉90度必須先停下來,慢慢轉完才可以繼續走,這樣太耗時了。

  於是愛德華想要一個程式,可以快速算出從指定起點走到終點最少要轉幾次彎,請你幫幫他!

Input

  輸入首行會有兩個正整數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筆。

Output

  對於每組測資輸出從起點走到終點機器人最少要轉幾次彎,每組測資一行。

  機器人不能往回走,因為這樣會發生不可預期的意外。

Sample Input #1
3 3
0 2
2
1 0
1 2
6 2
0 1
0
Sample Output #1
3
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#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
Hint :

上圖為第一組測資的地圖,起點為A,終點為B,黑色的是障礙物,紅線即為擁有最少轉彎次數的路線。

機器人一開始固定會朝向終點列(即上圖的下方),故一開始機器人必須還得先轉彎一次才能開始移動。

30%的測資,n、m≦10。

60%的測資,n、m≦100。

100%的測資,無特別限制。

Tags:
出處:
[管理者:
s955101 (puppy)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」