948 . Reflecmino
TopCoder
Tags
Description
Mango 很喜歡玩一款叫做 ReflecMino 的遊戲，遊戲裡面會有兩條光線，並且要擺放包含平面鏡的積木，讓光線經過格子和平面鏡到達邊界的終點。以下是遊戲畫面:
遊戲的時候，會顯示藍色光線經過的格子以及橘色光線經過的格子
如果橘色和藍色的格子同時經過同一個格子 (像右下角) 則會顯示為白色
Mango 想要寫一個程式，讓他能夠模擬現在的地圖中平面鏡的所有擺放位置和角度，並且計算出光線的行走路線，為了簡化，他把積木的元素去除掉了，只留下平面鏡和格子。
現在在一個 $n\times m$ 的方格世界外圍，各有一個入射點：B（藍色光束）與 G（橘色光束）。格子中有三種物件：
\與/：平面鏡，兩者均為 45° 角鏡面，滿足「入射角＝反射角」；.：空白，不改變光束方向；- 邊界上恰有一個
B和一個G。
光束從邊界入射後，每步沿當前方向前進一格：
- 遇到空白
.保持原方向； - 遇到鏡子
\或/，依鏡面方向反射； - 再次到達邊界即離開。
Input Format
第一行為兩個整數 $n$, $m$。
接下來 $n+2$ 行，每行 $m+2$ 個字元，其中：
- 邊界中恰有一個
B和一個G； - 其他位置為鏡面
\、鏡面/或空白.。
資料範圍：
- $1 \leq n,m \leq 1000$
- 題目保證不會出現光線在鏡子形成無限迴圈反射。
- 題目保證不會有鏡子出現在邊界上或角落上。
- 保證
B,G會出現在邊界上，且不會在角落。
Output Format
在內層格子中：
- 僅被藍色光束經過的格子標記
B； - 僅被橘色光束經過的格子標記
G； - 同一格被兩束光都經過則標記
W（白光）； - 未被任何光束經過的格子標記
.。
輸出整個內層格子，地圖大小為 $n \times m$
Sample Input 1
5 5 ....B.. ....\\. G..\./. ././.\. ....... .\./... .......
Sample Output 1
..BBB GGWBB GGGGG G.G.G GGG.G
Sample Input 2
3 3 ..... ..... B..\. ././. .G...
Sample Output 2
... WWW WWW
Hints
Problem Source
YTP 2025 國中組初賽 p4
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 0~43 | 無額外限制 | 15 |