內容
X大購物中心設置了一個遊戲區，裡頭備有一塊N×N的正方形地墊(N為邊長)，小朋友們可把他們喜愛的機器人放置於地墊上的任一位置中。機器人會直線前進，但不能轉彎，並且每一秒只能前進一格。前進方向有八種選擇(如下面圖一所示)，一旦選定後就不能改變。圖二為一個範例：機器人在時間t = 0被置於座標(2, 1)的位置，前進方向為SE，2秒過後(t = 2)機器人的座標為(4, 3)。當機器人走到地墊邊界時，就會停止前進。上述例子中機器人在t = 3之後都在座標(5, 4)的位置。
現在有一群小朋友帶著他們的機器人來到了遊戲區，各自把機器人放到地墊上，一開始機器人都在不同的位置，並且他們的前進方向可能都不一樣。請你寫一個程式來預測機器人是否會碰撞？碰撞的定義為同一時間兩個或多個機器人在同一個位置。在上述例子中，若有另一機器人被擺至(2, 4)位置，其前進方向為E，則t = 3時兩個機器人將發生碰撞。再舉一例，在上述例子中若另一機器人被擺在(1, 4)位置，其前進方向為E，其碰撞時間為t = 4。
當碰撞發生時，發生碰撞的機器人則停止前進。但尚未發生碰撞的機器人則會繼續行走。因此發生碰撞的時間及位置可能不只一組。
輸入說明
第一行有一個正整數N (5 ≤ N ≤ 100)，N代表地墊的邊長。
第二行有一個正整數M (2 ≤ M ≤ 10)，M代表機器人的個數。
第三行開始，每行有四個正整數，第一個數字表示機器人的編號(編號從1開始)，第二個數字表示機器人的起始位置(X, Y)座標中X的值，第三個數字表示機器人的起始位置(X, Y)座標中Y的值，第四個數字表示機器人的前進方向(以圖一括號內的數字表示，例如1代表N、2代表NE、3代表E……)，每個數字中間皆以一個空白分開。
輸出說明
如果將有碰撞情況發生，請輸出將發生碰撞的機器人編號(編號由小排到大列出)，以及發生碰撞的最早時間(t = ?)，同組碰撞情況只能有一組輸出。編號間請以一個空白分開，最後一個編號與時間請以一個逗號分開。若沒有碰撞情況，則輸出No collision!
範例輸入
#1
輸入範例一 5 2 1 2 1 4 2 2 4 3 輸入範例二 5 3 1 1 1 5 2 2 2 3 3 5 3 6
範例輸出
#1
輸出範例一 1 2,3 輸出範例二 No collision!
測資資訊：
記憶體限制：
512
MB
提示 ：
- 碰撞的「位置」或「時間」不同時，視為不同組的碰撞。
- 當碰撞不只一組時，請先按時間順序，再按編號的字典順序輸出。
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||