ZeroJudge 解題筆記：f699. 品嘉的茶葉蛋

作者：王一哲
日期：2025年10月19日


ZeroJudge 題目連結：f699. 品嘉的茶葉蛋

解題想法

標準的 BFS 題目。因為不想檢查是否出界，我在地圖周圍加上 2 作為哨兵。另外開一個陣列儲存步數。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m，最右側、最下方加上 2 作為哨兵
grid = [list(map(int, input().split())) + [2] for _ in range(n)]
grid.append([2]*(m+1))  # 最下方加 m+1 個 2
steps = [[0]*m for _ in range(n)]  # 記錄步數用的二維串列
ans = []  # 答案
que = deque([(0, 0)])  # 待走訪佇列
grid[0][0] = 2  # (0, 0) 設定為 2
while que:  # 如果 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
        if grid[nr][nc] == 2: continue  # 如果此格是 2 找下一格
        steps[nr][nc] = steps[r][c] + 1  # (nr, nc) 的步數為 (r, c) 的步數加 1
        if grid[nr][nc] == 1: ans.append(steps[nr][nc])  # 如果此格是 1，將 (nr, nc) 的步數加入 ans
        grid[nr][nc] = 2  # 此格設定為 2
        que.append((nr, nc))  # (nr, nc) 加入 que
if not ans: print("嘉油！")  # 沒有找到茶葉蛋
else:  # 有找到茶葉蛋，印出 ans 的內容
    for a in ans: print(a)

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main() {
    int n, m; scanf("%d %d", &n, &m);  // 地圖 n*m，四周加上 2 作為哨兵
    vector<vector<int>> grid (n+2, vector<int> (m+2, 2));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) scanf("%d", &grid[i][j]);
    }
    vector<vector<int>> steps (n+2, vector<int> (m+2, 0));
    vector<int> ans;  // 答案
    queue<pair<int, int>> que; que.push(make_pair(1, 1));  // 待走訪佇列
    grid[1][1] = 2;  // (1, 1) 設定為 2
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    while(!que.empty()) {  // 如果 que 還有資料繼續執行
        int r = que.front().first, c = que.front().second; que.pop();  // 從 que 開頭讀取並移除資料
        for(int i=0; i<4; i++) {  // 四方向檢查
            int nr = r+dr[i], nc = c+dc[i];  // 要檢查 (nr, nc)
            if (grid[nr][nc] == 2) continue;  // 如果此格是 2 找下一格
            steps[nr][nc] = steps[r][c] + 1;  // (nr, nc) 的步數為 (r, c) 的步數加 1
            if (grid[nr][nc] == 1) ans.push_back(steps[nr][nc]);  // 如果此格是 1，將 (nr, nc) 的步數加入 ans
            grid[nr][nc] = 2;  // 此格設定為 2
            que.push(make_pair(nr, nc));  // (nr, nc) 加入 que
        }
    }
    if (ans.empty()) {  // 沒有找到茶葉蛋
        printf("嘉油！\n");
    } else {  // 有找到茶葉蛋，印出 ans 的內容
        for(auto a : ans) printf("%d\n", a);
    }
    return 0;
}