ZeroJudge 解題筆記：f148. 2. 定向越野 (Orienteering)

作者：王一哲
日期：2025年3月1日



ZeroJudge 題目連結：f148. 2. 定向越野 (Orienteering)

解題想法

如果使用 Python，可以將目標點的字母、x 座標、y 座標組成數組，再加到串列之中，排序時會用數組最前面的資料為基準。如果使用 C++，要先自訂結構體，將目標點的字母、x 座標、y 座標存到結構體之中，再放入陣列，排序時可以用 lambda function 指定要以結構體之中的哪一項資料排序。

Python 程式碼

使用時間約為 26 ms，記憶體約為 3.3 MB，通過測試。

w, h = map(int, input().split())  # 地圖 w 列、h 欄
n = int(input())  # 要找 n 個目標
target = []  # 目標，(字母, x, y)
for r in range(w):  # 執行 w 次
    line = list(input().split())  # 讀取一行資料
    for c, s in enumerate(line):  # 從 line 依序讀取字元 s，索引值 c
        if s != '0': target.append((s, r, c))  # 如果 s 不等於 0，(s, r, c) 加入 target
target.sort()  # 依照開頭的字母排序
if len(target) < n:  # 如果 target 數量小於 n
    print("Mission fail.")  # 印出 Mission fail.
else:  # 任務成功，印出 target 前 n 個的座標
    for (_, r, c) in target[:n]:
        print(f"{r:d} {c:d}")

C++ 程式碼

使用時間約為 3 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    char s;
    int x, y;
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int w, h; cin >> w >> h;  // 地圖 w 列、h 欄
    int n; cin >> n;  // 要找 n 個目標
    vector<Node> target;  // 目標，(字母, x, y)
    for(int r=0; r<w; r++) {  // 執行 w 次
        for(int c=0; c<h; c++) {  // 執行 h 次
            char s; cin >> s;  // 讀取字元 s
            if (s != '0') {  // 如果 s 不等於 0
                Node p; p.s = s; p.x = r; p.y = c;  // 新的節點 p
                target.push_back(p);  // p 加入 target
            }
        }
    }
    sort(target.begin(), target.end(), [] (Node a, Node b) {
        return a.s < b.s; } );  // 依照開頭的字母排序
    if ((int)target.size() < n) {  // 如果 target 數量小於 n
        cout << "Mission fail.\n";  // 印出 Mission fail.
    } else {  // 任務成功，印出 target 前 n 個的座標
        for(int i=0; i<n; i++) cout << target[i].x << " " << target[i].y << "\n";
    }
    return 0;
}