APCS實作題2024年1月第2題：蜜蜂觀察

# APCS實作題2024年1月第2題：蜜蜂觀察 > 日期：2024年1月29日 > 作者：王一哲 > 題目來源：2024年1月實作題第2題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m932) ## 題目 ### 問題描述蜜蜂 Bob 在一個大小是 $m \times n$ 的蜂巢 (見範例說明圖示），並且每個蜂巢格上會有一個代表字母（大小或小寫英文字母）。 Bob 一開始在蜂巢左下角，行走方向定義如圖：0 是往右上; 1 是往右邊; 2 是往右下; 3 是往左下; 4 是往左邊; 5 是往左上。輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。 <img height="30%" width="30%" src="https://imgur.com/F3Wvoxd.png" style="display: block; margin-left: auto; margin-right: auto;"/> ### 輸入說明第一行包含三個整數 $m$、$n$、$k$，$(1 \leq m, n \leq 20)$，$(1 \leq k \leq 100)$，表示蜂巢的大小是 $m \times n$，Bob 的行走路徑有 $k$ 步。接下來的 $m$ 行，每行包含 $n$ 個字母（大小寫英文字母），代表蜂巢的狀態。最後一行包含 $k$ 個整數，表示 Bob 的移動路徑方向。子題分數： - 60%：滿足 $m=2$。 - 40%：無額外限制。 ### 輸出格式各輸出一行，包含兩個部分： - 由 Bob 每步經過的每格代表字母所組成的字串。 - 經過字元的種類數（大小寫視為相異），用一個整數表示。 ### 範例輸入1 ``` 2 4 5 TyuI ABaB 0 1 2 3 0 ``` <img height="35%" width="35%" src="https://imgur.com/rOL6X1h.png" style="display: block; margin-left: auto; margin-right: auto;"/> ### 範例輸出1 ``` Tyaau 4 ``` ### 範例輸入2 ``` 4 6 11 rMmnis LRveEX ZexDoc HAdbHA 0 1 5 1 1 0 3 0 0 1 0 ``` <img height="60%" width="60%" src="https://imgur.com/mA5GKy2.png" style="display: block; margin-left: auto; margin-right: auto;"/> ### 範例輸出2 ``` ZeLRvmvmmnn 7 ``` ## Python 程式碼在題目給的蜂巢資料最右側、最下方加上不是英文字母的字元作為哨兵，以下的程式中使用的是 "@"，如果讀到這個字元代表已出界，這樣的作法會比檢查索引值本身還簡單。由於 Python 的串列索引值 -1 會對應到最後一個元素，所以只要圍右側、下方即可。費時最久約為 19 ms，使用記憶體最多約為 3.4 MB，通過測試。 ```python= m, n, k = map(int, input().split()) # 讀取 m, n, k hive = [list(input()) for _ in range(m)] # 讀取蜂巢資料 steps = list(map(int, input().split())) # 讀取行走步驟資料 for i in range(m): hive[i].append("@") # 於每一列最後面加上 @ 作為哨兵 hive.append(["@"]*(n+1)) # 於最下方加上 n+1 個 @ 作為哨兵，可能往右下方移動，如果只加 n 個 @ 可能會出界 ans = "" # 路徑上的字母，預設為空字串 chars = set() # 集合，儲存出現過的字母 r, c = m-1, 0 # 起始位置 dirs = ((-1, 0), (0, 1), (1, 1), (1, 0), (0, -1), (-1, -1)) # 移動方向，分別代表右上、右、右下、左下、左、左上 for step in steps: # 由 steps 依序讀取移動方向 if hive[r + dirs[step][0]][c + dirs[step][1]] != "@": # 先檢測下一格是否出界，如果沒出界就更新位置 r += dirs[step][0] c += dirs[step][1] ch = hive[r][c] # 讀取這格的字母 ans += ch # 將 ch 加到 ans 最後面 chars.add(ch) # 將 ch 加入集合 chars print(ans) # 印出路徑上的字母 print(len(chars)) # 印出不同的字母數量 ``` ## C++ 程式碼在題目給的蜂巢資料四周加上不是英文字母的字元作為哨兵，以下的程式中使用的是 "@"，如果讀到這個字元代表已出界，這樣的作法會比檢查索引值本身還簡單。由於 C++ 的 vector 索引值不能是 -1，這樣會遇到 IndexError。費時最久約為 2 ms，使用記憶體最多約為 336 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <string> #include <set> using namespace std; int main() { int m, n, k; cin >> m >> n >> k; // 讀取 m, n, k /* 蜂巢資料，産生 (m*2) * (n+2) 的二維 vector， * * 預設值皆為 @，由測資讀取資料時再取代對應的位置。 */ vector<vector<char>> hive (m+2, vector<char> (n+2, '@')); for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { char ch; cin >> ch; hive[i][j] = ch; } } vector<int> steps (k, -1); // 行走步驟資料 for(int i=0; i<k; i++) { int step; cin >> step; steps[i] = step; } string ans = ""; // 路徑上的字母，預設為空字串 set<char> chars; // 集合，儲存出現過的字母 int r = m, c = 1; // 起始位置為左下角，因為四周有加上哨兵，列、欄索引值都要加1 int dirs[6][2] = {{-1, 0}, {0, 1}, {1, 1}, {1, 0}, {0, -1}, {-1, -1}}; // 移動方向，分別代表右上、右、右下、左下、左、左上 for(int i=0; i<k; i++) { // 由 steps 依序讀取移動方向 int step = steps[i]; if (hive[r + dirs[step][0]][c + dirs[step][1]] != '@') { // 先檢測下一格是否出界，如果沒出界就更新位置 r += dirs[step][0]; c += dirs[step][1]; } char ch = hive[r][c]; // 讀取這格的字母 ans += ch; // 將 ch 加到 ans 最後面 chars.insert(ch); // 將 ch 加入集合 chars } cout << ans << "\n"; // 印出路徑上的字母 cout << chars.size() << "\n"; // 印出不同的字母數量 return 0; } ``` --- ###### tags:`APCS`、`Python`、`C++`