回分類題庫
g063: E.糾結的水管
關鍵字: NPSC 2009 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 31 Times / 30 Users | Submit : 72 Times / 36 Users | Accepted rate : 83%
題目加入時間 : 2011-12-26 15:11

Content: 简体中文

正直DE 是個很正直的青年,每天他都會到鄰近的大街小巷中幫老爺爺老奶奶整理院子和花圃。

有天他正要澆花時發現李爺爺院子裡的好多條塑膠水管全部都打結成一團了,怎麼解都解不開。好在這些水管還是能通,只要找出某一頭的另一端在哪就可以使用。

 

上圖代表多條糾結的水管,其中:
  ‘.’代表這個位置是空的,沒有水管
  ‘A’~‘H’代表水管的端點,也就是出入口
  ‘-’和 ‘|’各代表橫向和縱向的水管
  ‘+’代表水管的轉彎處
  ‘#’代表在這個點上有兩條水管交叉,兩條水管之間不會互相影響

若我們從A 注水進去,水會從另一端G 出來;若從F 端注水則水會從E 端出來。

因為DE 實在是太正直了,面對這種糾纏不清的問題反而不知道怎麼解決,所以他現在要脅你在五個小時以內給他一個程式解決這個問題:問你從某個端點注水進去,水會從哪個端點出來?

Input:

第一行有一個整數T(T<=20),代表總共有幾筆測試資料。
每筆測試資料的第一行包含N(0<N<=20),M(0<M<=20)
接下來N 行,每行有M 個字元,描述水管的糾纏狀況。
接下來會有一個數字Q(1<=Q<=20),代表問題的數量。
接下來Q行每行包含一個字元(在A到Z 之間),代表要從這個端點注水進去。
你可以假設:
  不會有兩條同方向且重疊的水管,也不會在端點上交叉
  不會有兩條水管在同一個點上轉彎
  兩條不同水管的轉彎點不會相鄰
  一個端點的上下左右必定剛好只有一個管子和它相連
  水管除了端點以外最少有1 的長度
每兩筆測試資料之間會有一個空白行。

Output:

對於每個問題,輸出一行包含:
  注水端點 -> 出水端點
端點名稱同input 描述。
每組測試資料間要有一個空白行。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
10 10
..........
.A--+.....
....|.B+..
+---#--#-C
|...|..|..
+-D.|..|..
.+--+..|..
.|.E---#-F
.+---G.|..
.......+-H
2
A
C
3 3
...
A-B
...
1
A

Sample Output :

A->G
C->D

A->B

Hint :

Author :

NPSC 2009 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum