網址

http://poj.org/problem?id=2766

題目概述

Laserbox 是一個有趣的光學遊戲，該遊戲進行於一塊長與寬皆為 N 的棋盤上。在這棋盤上的某些格子上，會被放置 R 個稱為 right-turner 小裝置。當雷射光打到這些 right-turner 時，雷射光將被向右反射。題目會給定雷射光進入棋盤的座標，在雷射光進入棋盤後，可能會碰到這些 right-turner，試問雷射光離開棋盤的座標。

Technique details

• 棋盤長寬 N，1 ≤ N ≤ 50
• right-turne 數量 R，1 ≤ N ≤ 50

輸入格式

測試資料第一行會有一整數（T）開始，表示接下來將會有 T 筆測試資料。對於每一筆測試資料，將由兩個整數作為開頭（N R），分別表示棋盤大小與 right-turne 數量。接下來會有 R 行，每行兩個整數（x y），表示第 x 列第 y 行該位置會有 right-turne，且一個座標上不會出現兩個 right-turne。最後，會有兩個整數（x y）表示雷射進入棋盤的座標。

其中雷射進入座標與離開座標，其值會有 0 或是 N + 1 出現，表示已不在棋盤內。

輸出格式

對於每一筆測試資料，輸出兩個整數（x y）即為雷射離開棋盤之座標。另外，若雷射無法順利離開棋盤，則輸出座標（0, 0）作為答案。

解題思路

水題…。

按照題目的意思建圖，並將存在 right-turne 的位置上做標記。按照題意將雷射從進入點進去棋盤後，一步一步的移動雷射的路徑，碰到 right-turne 則右轉。一直到離開棋盤，即可輸出答案。

另外，題目提到了若是雷射無法離開棋盤，則輸出座標（0, 0）。不過，由於 right-turne 只能向右轉，僅有單一方向，一個無法離開的 cycle，該怎麼進去？所以根本沒有該情況。

時間複雜度頂多是把整張圖遍歷一次，而且也不可能遍歷每個位置，就姑且把時間複雜度算為 N :sup:2 吧。

Time Complexity: O( N :sup:2 )