# APCS實作題2024年10月第2題：蒐集寶石 > 日期：2024年10月28日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o712) <br /> ## 題目 ### 問題描述 有一個 $M \times N$ 的地圖，每一格的數字紀錄著寶石的數量，如果數字是 $-1$ 代表牆壁。 有一位機器人一開始位於 $(r, c)$ 的位置上且方向朝右邊，他遵循著以下規則行走。 1. 若機器人位於的格字內寶石數量為 $0$，則機器人程式終止。 2. 機器人維護著一個分數 score，將 score 加上當前格的寶石數量，並且撿起一顆寶石。 3. 若 score 是 $k$ 的倍數，則向右轉 90 度。 4. 若機器人面向的格子是牆壁或是超出邊界，則繼續向右轉 90 度直到面向的格子非牆壁或非超出邊界，並回到第 1 步。 <img style="display: block; margin-left: auto; margin-right: auto" height="70%" width="70%" src="https://zerojudge.tw/ShowImage?id=4320"> <br /> 例如機器人一開始在座標 $(2, 1)$ 且 $k=2$，向右走兩步之後分數為 $3+2+3=8$，由於 $8$ 是 $2$ 的倍數所以向右轉 90 度。接下來往下走一步分數變為 $11$，需要向右轉 2 次 90 度才不會面向牆壁或是邊界外的格子。 接下來向前走一步走到座標 $(2, 3)$，由於先前已經拿走一顆寶石，該位置的寶石數量變為 $2$，因此分數變為 $13$，再繼續往上走兩步到 $(0, 3)$ 處分數為 $16$，由於 $16$ 為 $2$ 的倍數所以向右轉 90 度。 向前走一格到 $(0, 4)$ 後需要向右轉兩次 90 度，回到 $(0, 3)$ 後由於寶石數量為 $0$，機器人停止。過程中機器人總共撿了 $8$ 顆寶石。 <br /> ### 輸入格式 第一行有 $5$ 個正整數 $M, N, k, r, c$ $$ 1 \leq M \leq 100 ~~~~~ 2 \leq N \leq 100 ~~~~~ 1 \leq k \leq 20 ~~~~~ 0 \leq r < M ~~~~~ 0 \leq c < N $$ 保證機器人初始位置不是牆壁。接下來有 $M$ 行，每一行有 $N$ 的數字，代表地圖的資訊。 子題配分 - 60%：$M = 1$ - 40%：無限制 <br /> ### 輸出格式 輸出機器人會蒐集幾個寶石。 <br /> ### 範例輸入1 ``` 1 7 3 0 4 1 -1 2 1 2 1 0 ``` ### 範例輸出1 ``` 5 ``` ### 範例輸入2 ``` 4 5 4 2 1 2 0 1 1 1 2 -1 0 2 -1 0 3 2 3 0 1 1 -1 3 1 ``` ### 範例輸出2 ``` 8 ``` <br /> ## Python 程式碼 費時最久約 0.1 s，使用記憶體最多 3.5 MB，通過測試。 ```python= M, N, k, r, c = map(int, input().split()) # 地圖列數 M、欄數 N，寶石倍數 k，起點位置 (r, c) grid = [list(map(int, input().split())) for _ in range(M)] # 讀取地圖資料 dirs = ((0, 1), (1, 0), (0, -1), (-1, 0)) # 移動方向依序為右、下、左、上 d = 0 # 移動方向 score = 0 # 分數 pick = 0 # 目前撿起的寶石數量 while grid[r][c] != 0: # 如果此格寶石數量不是0繼續執行 score += grid[r][c] # 分數加上此格的寶石數量 pick += 1 # 檢1個寶石 grid[r][c] -= 1 # 此格寶石數量減1 move = False # 是否能走到下一格 ts = 0 # 因為分數而轉向的次數，最多只會有1次 while not move: # 如果不能走到下一格繼續執行 nr, nc = r + dirs[d][0], c + dirs[d][1] # 下一格為 (nr, nc) if score%k == 0 and ts == 0: # 如果 score 是 k 的倍數而且還沒有因為分數轉向 d = (d+1)%4; ts += 1 # 轉向，ts 加 1 # 向右且 nc>= N 出界，向下且 nr>=M 出界，向左且 nc<0 出界，向上且 nr<0 出界 elif (d == 0 and nc >= N) or (d == 1 and nr >= M) or (d == 2 and nc < 0) or (d == 3 and nr < 0): d = (d+1)%4 # 轉向 elif grid[nr][nc] == -1: # 遇到牆壁 d = (d+1)%4 # 轉向 else: # 可以走到下一格 move = True # 重設為 True r, c = nr, nc # 更新 (r, c) # end of while loop print(pick) # 印出撿起的寶石數量 ``` <br /><br /> ## C++ 程式碼 費時最久約 4 ms，使用記憶體最多 380 kB，通過測試。 ```cpp= #include <iostream> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int M, N, k, r, c; cin >> M >> N >> k >> r >> c; // 地圖列數 M、欄數 N，寶石倍數 k，起點位置 (r, c) int grid[M][N]; for(int i=0; i<M; i++) for(int j=0; j<N; j++) cin >> grid[i][j]; // 讀取地圖資料 int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 移動方向依序為右、下、左、上 int d = 0, score = 0, pick = 0; // 移動方向，分數，目前撿起的寶石數量 while(grid[r][c] != 0) { // 如果此格寶石數量不是0繼續執行 score += grid[r][c]; // 分數加上此格的寶石數量 pick++; // 檢1個寶石 grid[r][c]--; // 此格寶石數量減1 bool move = false; // 是否能走到下一格 int ts = 0; // 因為分數而轉向的次數，最多只會有1次 while(!move) { // 如果不能走到下一格繼續執行 int nr = r + dirs[d][0], nc = c + dirs[d][1]; // 下一格為 (nr, nc) if (score%k == 0 && ts == 0) { // 如果 score 是 k 的倍數而且還沒有因為分數轉向 d = (d+1)%4; ts++; // 轉向，ts 加 1 // 向右且 nc>= N 出界，向下且 nr>=M 出界，向左且 nc<0 出界，向上且 nr<0 出界 } else if ((d == 0 && nc >= N) || (d == 1 && nr >= M) || (d == 2 && nc < 0) || (d == 3 && nr < 0)) { d = (d+1)%4; // 轉向 } else if (grid[nr][nc] == -1) { // 遇到牆壁 d = (d+1)%4; // 轉向 } else { // 可以走到下一格 move = true; // 重設為 True r = nr; c = nc; // 更新 (r, c) } } } cout << pick << "\n"; // 印出撿起的寶石數量 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`