分享到plurk 分享到twitter 分享到facebook

[POJ] 2766 - Laserbox

網址

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 )