切換
舊版
前往
大廳
主題

ZeroJudge - f148: 2. 定向越野 (Orienteering) 解題心得

Not In My Back Yard | 2020-07-11 00:16:36 | 巴幣 0 | 人氣 344

題目連結:


題目大意:
輸入第一列給定兩正整數 W 、 H (1 ≦ W 、 H ≦ 10),代表地圖由上至下有 W 列、由左至右有 H 行。左上角座標為 (0, 0),右下角座標為 (W - 1, H - 1)。

接著的一列輸入給定一正整數 N (1 ≦ N ≦ 26),代表要尋找的目標個數。

再接著有 W 列輸入,每列給定 H 個字元,代表地圖每個位置的內容物。字元可能是數字「0」或是小寫英文字母 a ~ z (字母不會重複出現)。數字 0 代表該格為空、小寫英文字母代表目標。

目標要以字典序小到大,也就是從 a 、 b 、 c 、 ……開 始找(如果 a 、 b 、 c 等等存在的話)。

請找到 N 個目標,並輸出他們的座標。如果地圖中的目標數目不夠 N ,則輸出「Mission fail.」



範例輸入:
輸入範例一:
5 5
5
0 0 a 0 0
0 b 0 0 0
c 0 0 0 0
0 d 0 0 0
0 0 e 0 0

輸入範例二:
2 2
4
g e
f d

輸入範例三:
4 4
5
z 0 0 0
c 0 0 0
a 0 0 0
g 0 0 0

輸入範例四:
3 3
6
x c a
b 0 y
0 g 0

輸入範例五:
5 5
10
f g h i j
k l m n o
a b c d e
p q r s t
u v w x y


範例輸出:
輸出範例一:
0 2
1 1
2 0
3 1
4 2

輸出範例二:
1 1
0 1
1 0
0 0

輸出範例三:
Mission fail.

輸出範例四:
0 2
1 0
0 1
2 1
0 0
1 2

輸出範例五:
2 0
2 1
2 2
2 3
2 4
0 0
0 1
0 2
0 3
0 4


解題思維:
宣告幾個大小為 26 的陣列,用來表示 a ~ z 字母有無出現在地圖上、位置為何等等(a 對應到位置 0 、 b 對應到位置 1 ……以此類推)。

掃過一次地圖並找到以上資訊,並統計地圖中的目標個數(不是「0」的字元之數目)。

如果地圖中的目標個數 < N ,則輸出「Mission fail.」;反之,從 a 開始找。每找到一個存在的字元就輸出該字元在地圖中的座標,直到找滿 N 個目標。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作