蒐集寶石 (APCS 2024-10 中級)

小田設計了一個機器人來玩蒐集寶石的遊戲，遊戲的場地是一個 \(M \times N\) 的二維陣列，每個元素 \((i, j)\) 對應在第 \(i\) 橫列第 \(j\) 直行的格子，其中橫列由上而下，直行由左往右，皆由 \(0\) 開始編號。某些格子是牆壁，機器人無法進入，其他的格子機器人可以進入，這些格子內有若干寶石，但某些格子的寶石數量可能是 \(0\)，場地四周視為被牆壁包圍，也就是機器人不能走出界外。遊戲開始時，機器人從編號 \((r, c)\) 的格子開始，初始的方向為面向東方（右方），初始得分與擁有的寶石數量皆為 \(0\)。機器人會記錄目前的得分以及行進的方向。機器人的行動規則如下，請計算出機器人在停止時所獲得的寶石數量，其中 \(K\) 是一個輸入的正整數：

1. 如果走到的格子內無寶石，則停止遊戲；否則
2. 將得分加上該格子目前的寶石數量，並取得一顆寶石。該格子的剩餘寶石數量就會減少一顆；
3. 如果總得分是 \(K\) 的倍數，則向右轉（順時針轉 \(90\) 度）；
4. 若前方是牆壁或者前方是界外，則向右轉；持續本步驟直到前方的格子在場地範圍內且非牆壁；
5. 進入前方的格子，並回到步驟 1 繼續。

請注意，在原地右轉時並不算再次走到該格子。

以下圖為例，場地是一個 \(4 \times 5\) 的二維陣列，起點在 \((2, 1)\)，起始方向朝東，假設 \(K = 4\)。機器人一開始會行經 \((2, 1) \rightarrow (2, 2) \rightarrow (2, 3)\)，此時得分為 \(3 + 2 + 3 = 8\)，為 \(K\) 的倍數，因此會右轉，方向改為朝南。接下來往南一步走到 \((3, 3)\)，此時得分為 \(11\)，但往前是界外，因此會右轉朝西，此時前方 \((3, 2)\) 的位置為牆壁，所以繼續右轉朝北。

再前進時到達 \((2, 3)\)，這個格子一開始有 \(3\) 顆寶石，但之前經過一次拿走一顆，所以只剩下 \(2\) 顆，故總得分為 \(11 + 2 = 13\)。接著會往北走兩次，總得分分別為 \(15\) 與 \(16\)，在 \((0, 3)\) 時右轉到 \((0, 4)\)，然後會右轉兩次朝西，最後走到 \((0, 3)\) 時，該格子的寶石已被取走，剩下 \(0\) 顆寶石，遊戲停止。總共獲得的寶石的數量即是停止前所走的總步數（\(7\) 步）加上起始位置的 \(1\) 顆，一共是 \(8\) 顆。

輸入格式

第一行有五個整數 \(M, N, K, r, c\)（\(1 \le M \le 100, 2 \le N \le 100, 2 \le K \le 20\)），其中 \((r, c)\) 為起始位置。接下來 \(M\) 行，每行有 \(N\) 個整數，為每一個格子由上而下，由左而右的值，其中 \(-1\) 表示牆壁，否則為寶石數量，寶石數量介於 \(0\) 到 \(K - 1\) 之間，同一行兩個數值間以一個空白間隔。起始點 \((r, c)\) 的位置保證不是牆，且起始點不會四周均無路可走，機器人最終一定會停下來。

輸出格式

輸出一個整數，為機器人所蒐集到的寶石數。

範例輸入 1

1 7 3 0 4
1 -1 2 1 2 1 0

範例輸出 1

5

範例說明 1

經過的格子依序為 \((0, 4)\)、\((0, 5)\)、\((0, 4)\)、\((0, 3)\)、\((0, 2)\)，接下來到達 \((0, 3)\) 已無寶石。共取得 \(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 0

範例輸出 2

8

範例說明 2

此為題目中之範例。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過測資筆數給分。其中：

• 第 1 子題組 60 分：\(M = 1\)。請留意 \(M = 1\) 時，如遇到右轉必然會連續轉兩次，也就是說右轉即是迴轉。
• 第 2 子題組 40 分：無額外限制。

題目來源

APCS 程式實作中級題本範例，程式實作 2024 年 10 月。

• APCS 官方中級題本範例
• ZeroJudge o712