ZeroJudge 解題筆記：i376. 尋寶 (Treasure)

作者：王一哲
日期：2025年4月9日



ZeroJudge 題目連結：i376. 尋寶 (Treasure)

解題想法

我是先掃過每一列找出最高處，將這些位置的座標加入一個集合 cand 之中；再掃過每一欄，找每欄的最低點，如果此處的座標在 cand 之中，表示已經找到答案。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 地圖 n*n
    grid = [list(map(int, input().split())) for _ in range(n)]  # 地圖資料
    cand = []  # 可能的地點
    for r in range(n):  # 先找每列最高處放入 cand，可能有多個最高處
        imax = max(grid[r])  # 第 r 列的最大值
        for c in range(n):  # 依序掃過每欄
            if grid[r][c] == imax:  # 如果此格等於 imax
                cand.append((r, c))  # (r, c) 加入 cand
    found = False  # 是否找到答案
    for c in range(n):  # 依序找每欄的最低處在第幾列
        imin = min([grid[i][c] for i in range(n)])  # 第 c 欄的最小值
        for r in range(n):  # 依序掃過每列
            if grid[r][c] == imin and (r, c) in cand:  # 如果此格等於 imin 而且在 cand 之中
                found = True  # 找到答案
                print(r, c)  # 印出 (r, c)
                break  # 中止迴圈
        if found: break  # 如果已經找到答案，中止迴圈    
    if not found: print("NO")  # 如果沒有找到答案印出 NO

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 地圖 n*n
    while(cin >> n) {
        vector<vector<int>> grid (n, vector<int> (n));  // 地圖資料
        for(int r=0; r<n; r++) {
            for(int c=0; c<n; c++) cin >> grid[r][c];
        }
        set<pair<int, int>> cand;  // 可能的地點
        for(int r=0; r<n; r++) {  // 先找每列最高處放入 cand，可能有多個最高處
            int imax = *max_element(grid[r].begin(), grid[r].end());  // 第 r 列的最大值
            for(int c=0; c<n; c++) {  // 依序掃過每欄
                if (grid[r][c] == imax) cand.insert(make_pair(r, c));  // 如果此格等於 imax，(r, c) 加入 cand
            }
        }
        bool found = false;  // 是否找到答案
        for(int c=0; c<n; c++) {  // 依序找每欄的最低處在第幾列
            int imin = 10000;  // 此欄的最小值，預設為超過題目範圍的值
            for(int r=0; r<n; r++) imin = min(imin, grid[r][c]);  // 找最小值
            for(int r=0; r<n; r++) {  // 依序掃過每列
                if (grid[r][c] == imin && cand.count(make_pair(r, c)) == 1) { //# 如果此格等於 imin 而且在 cand 之中
                    found = true;  // 找到答案
                    cout << r << " " << c << "\n";  // 印出 (r, c)
                    break;  // 中止迴圈
                }
            }
            if (found) break;  // 如果已經找到答案，中止迴圈    
        }
        if (!found) cout << "NO\n";  // 如果沒有找到答案印出 NO
    }
    return 0;
}