1417 . PCC 上學

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Fysty

User's AC Ratio

84.2% (16/19)

Submission's AC Ratio

29.6% (24/81)

Tags

ioicamp ioicamp-2026

Description

PCC 24 歲，是學生，要去學校上學。

PCC 喜歡分享，所以平常都會開著定位系統，現在你可以即時看到 PCC 在哪裡，還有他怎麼移動的。

學校的地圖是一個 $N \times M$ 的方格，PCC 每次可以上下左右移動一格，地圖上有三種區域：

  • 空地 .：校園的馬路和走道，PCC 可以自由走動。
  • 牆壁 #：這是建築物的實體結構，PCC 在學習穿牆但是還沒有學會，只能繞過它。
  • 入口 $：這是進入建築的感應門，PCC 可以走到那個格子，選擇要不要進入該建築物。
  • 入口格子 $ 和空地格子 . 可以走上去， 牆壁格子 # 則不能走上去。

學校裡有多棟建築物，每一棟建築都有入口，有可能會有多個入口。

  • 每一棟建築物由 # 和 $ 組成，上下左右有互相連接的牆壁 # 和入口 $ 屬於同一棟建築，沒有互相連接的則屬於不同建築。
  • 只要 PCC 走到屬於某棟建築的任意一個入口格子 $ 上，PCC 就可以選擇進入建築物 (也可以選擇不要進入)。
  • 入口 $ 不一定會在建築周圍，有可能因為施工等原因導致該入口被牆壁包圍起來無法到達。

PCC 有學過最短路徑演算法，如果他要去別的建築物的話，都只會走最短路徑，也就是他會盡量走最少的格子到目標建築的任一個入口 $。
因此，可以透過這個特性來預測 PCC 要去哪個地方躲起來讀書或是鬼混。

現在系統傳來了 $Q$ 筆資料，每一筆資料包含 PCC 的起始位置以及一段他剛剛走過的移動路徑，你需要算出 PCC 接下來有可能要去哪些建築物，計算符合條件的建築物數量。

對於每一筆資料，請根據 PCC 的移動路徑判斷他可能的目的地數量 $S$，或者是路徑有誤，並輸出對應的訊息：

  1. 路徑錯誤或 $S = 0$：
    • 代表 PCC 撞牆 (走到屬於牆壁的格子)、走出地圖邊界，或是該路徑無法以最短路徑抵達任何建築物。
    • 請輸出 "GPS is broken" (不含引號)。
  2. $S = 1$：
    • 代表 PCC 的意圖非常明顯，只有唯一的建築物符合他的移動路徑。
    • 請輸出 "PCC is caught" (不含引號)。
  3. $S > 1$：
    • 代表有多個建築物都符合這條路徑，還無法確定他到底要去哪裡。
    • 請輸出可能的建築物數量 $S$。

Input Format

第一行包含兩個正整數 $N, M$ ，代表地圖的大小。

接下來 $N$ 行，每行包含一個長度為 $M$ 的字串，由字元 ., #, $ 組成，代表學校的地圖。

接下來一行包含一個正整數 $Q$，代表詢問次數。

接下來 $Q$ 行，每行包含兩個整數 $r_i, c_i$ 和一個字串 $S_i$：

  • $r_i, c_i$ ：PCC 的起點座標，代表 PCC 一開始在從上往下數的第 $r_i$ 列和從左往右數的第 $c_i$ 行。
  • $S_i$：由字元 U (上), D (下), L (左), R (右) 組成的字串，代表 PCC 移動的路徑序列。

  • $1 \le N, M \le 300$
  • $1 \le Q \le 10^ 5$
  • $1 \le r_i \le N, 1 \le c_i \le M$
  • $len(S_i) \ge 1$
  • 保證 $\sum len(S_i) \le 10^ 6$
  • 地圖上的建築物數量不超過 $300$ 棟。
  • 地圖保證至少有一棟建築物。

Output Format

請輸出 $Q$ 行，代表某一筆詢問的答案。

Sample Input 1

5 5
#$.$#
##..$
#....
....$
....#
6
5 1 RU
3 5 LLULL
2 3 D
3 2 RR
3 2 DDD
3 2 U

Sample Output 1

3
GPS is broken
PCC is caught
2
GPS is broken
GPS is broken

Hints

範例測資解釋：

圖中有三棟建築物，分別在左上角、右上角以及右下角。

在第一筆詢問中，PCC 一開始在 $(5, 1)$ 也就是最左下角的位置，往上移了一步，根據這個移動路徑 PCC 三棟建築物都有可能前往，因此輸出 $3$。

在第二筆詢問中，PCC 一開始從 $(3, 5)$ 的位置開始移動，在第四步移動到 $(2, 2)$ 時撞到了牆，因此輸出 GPS is broken。

在第三筆詢問中，PCC 只有可能要前往右下角的建築物，因此輸出 PCC is caught。

在第四筆詢問中，PCC 有可能要前往右上角或是右下角的建築，因此輸出 $2$。

在第五筆詢問中，PCC 超出了學校地圖範圍，因此輸出 GPS is broken。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~12 $N, M \le 20, Q \le 100$ 20
3 13~30 每棟建築物恰好只有 1 個入口 40
4 0~60 無其他限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 2 4
1 4000 262144 65536 2 4
2 4000 262144 65536 2 4
3 4000 262144 65536 2 4
4 4000 262144 65536 2 4
5 4000 262144 65536 2 4
6 4000 262144 65536 2 4
7 4000 262144 65536 2 4
8 4000 262144 65536 2 4
9 4000 262144 65536 2 4
10 4000 262144 65536 2 4
11 4000 262144 65536 2 4
12 4000 262144 65536 2 4
13 4000 262144 65536 3 4
14 4000 262144 65536 3 4
15 4000 262144 65536 3 4
16 4000 262144 65536 3 4
17 4000 262144 65536 3 4
18 4000 262144 65536 3 4
19 4000 262144 65536 3 4
20 4000 262144 65536 3 4
21 4000 262144 65536 3 4
22 4000 262144 65536 3 4
23 4000 262144 65536 3 4
24 4000 262144 65536 3 4
25 4000 262144 65536 3 4
26 4000 262144 65536 3 4
27 4000 262144 65536 3 4
28 4000 262144 65536 3 4
29 4000 262144 65536 3 4
30 4000 262144 65536 3 4
31 4000 262144 65536 4
32 4000 262144 65536 4
33 4000 262144 65536 4
34 4000 262144 65536 4
35 4000 262144 65536 4
36 4000 262144 65536 4
37 4000 262144 65536 4
38 4000 262144 65536 4
39 4000 262144 65536 4
40 4000 262144 65536 4
41 4000 262144 65536 4
42 4000 262144 65536 4
43 4000 262144 65536 4
44 4000 262144 65536 4
45 4000 262144 65536 4
46 4000 262144 65536 4
47 4000 262144 65536 4
48 4000 262144 65536 4
49 4000 262144 65536 4
50 4000 262144 65536 4
51 4000 262144 65536 4
52 4000 262144 65536 4
53 4000 262144 65536 4
54 4000 262144 65536 4
55 4000 262144 65536 4
56 4000 262144 65536 4
57 4000 262144 65536 4
58 4000 262144 65536 4
59 4000 262144 65536 4
60 4000 262144 65536 4
Submit
Back to Top