# APCS實作題:卡牌遊戲 > 日期:2024年1月30日 > 作者:王一哲 > 題目來源:2023年10月實作題第2題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m371) ## 題目 ### 問題描述 你有一個 $n \times m$ 大小的表格,你可以從中消除具有相同數值且之間沒有障礙物的兩個元素,並獲得分數。請問你可以獲得的最大得分。 每一種數字在表格中出現恰好兩次。消除兩個相同的數字 $x$ 時,可以獲得 $x$ 分。 消除規則:你可以垂直或水平地將兩個相同數值的元素消除,但消除的兩個元素之間不能有其他尚未消除的元素。 <br /> ### 輸入說明 第一行包含兩個整數:$n$ 和 $m$,以空格分隔。它們分別代表表格的行數和列數。 接下來有 $n$ 行,每行包含 $m$ 個整數,以空格分隔,表示表格中的元素。每個元素的數值範圍介於 $[0, 1000]$ 之內,且每種數字在表格中出現恰好兩次。 輸入保證表格上的每種數字恰好出現兩次,且表格的格數為偶數。 子題分數: - 60%:滿足 $n = 1, 1 \leq m \leq 40$。 - 40%:滿足 $1 \leq n \leq 20, 1 \leq m \leq 40$ 。 <br /> ### 輸出說明 請輸出一個整數,代表你可以獲得的最大得分。 <br /> ### 範例輸入1 ``` 1 8 0 2 3 3 0 2 5 5 ``` ### 範例輸出1 ``` 8 ``` <br /> ### 範例輸入2 ``` 3 6 0 2 3 8 0 2 1 1 4 4 5 7 5 6 3 8 6 7 ``` ### 範例輸出2 ``` 29 ``` <br /> ## Python 程式碼 費時最久約為 55 ms,使用記憶體最多約為 3.4 MB,通過測試。 ```python= n, m = map(int, input().split()) # 讀取卡牌列數n、欄數m cards = [list(map(int, input().split())) for _ in range(n)] # 讀取卡牌數字 pos = [(r, c) for r in range(n) for c in range(m)] # 産生所有的位置並存成串列 score = 0 # 總分 flag = True # 是否繼續執行,如果有找到配對成功的兩張牌即為 True while flag: # 當 flag 為 True 時繼續執行 flag = False # 先重設為 False for r, c in pos: # 依序讀取位置 (r, c) if cards[r][c] == -1: continue # 如果這個位置的牌已取走已被設定為 -1,執行下一次 for 迴圈 nr, nc = r+1, c+1 # 下一列 nr,下一欄 nc """ 向下找相同的牌 """ while nr < n-1 and cards[nr][c] == -1: nr += 1 # 如果 nr 還可以加 1 而且這個位置的牌已取走,將 nr 加 1 if nr <= n-1 and cards[nr][c] == cards[r][c]: # 如果 nr 沒有出界,而且 {nr, c}、{r, c} 兩張牌相同 score += cards[r][c] # score 加上牌面數字 cards[r][c] = -1 # 將這兩個位置的牌設為 -1 cards[nr][c] = -1 flag = True # flag 設定為 True,繼續找下一輪 """ 向右找相同的牌 """ while nc < m-1 and cards[r][nc] == -1: nc += 1 # 如果 nc 還可以加 1 而且這個位置的牌已取走,將 nc 加 1 if nc <= m-1 and cards[r][nc] == cards[r][c]: # 如果 nc 沒有出界,而且 {n, nc}、{r, c} 兩張牌相同 score += cards[r][c] # score 加上牌面數字 cards[r][c] = -1 # 將這兩個位置的牌設為 -1 cards[r][nc] = -1 flag = True # flag 設定為 True,繼續找下一輪 # 結束 while 迴圈 print(score) # 印出答案 ``` <br /><br /> ## C++ 程式碼 費時最久約為 6 ms,使用記憶體最多約為 328 kB,通過測試。 ```cpp= #include <iostream> #include <vector> #include <utility> using namespace std; int main() { int n, m; cin >> n >> m; // 讀取卡牌列數n、欄數m vector<vector<int>> cards (n, vector<int> (m, 0)); // 卡牌數字 vector<pair<int, int>> pos (n*m, make_pair(0, 0)); // 所有的位置 for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { int card; cin >> card; cards[i][j] = card; pos[i*m+j] = {i, j}; } } int score = 0; // 總分 bool flag = true; // 是否繼續執行,如果有找到配對成功的兩張牌即為 True while(flag) { // 當 flag 為 True 時繼續執行 flag = false; // 先重設為 False for(auto p : pos) { // 依序讀取位置 (r, c) int r = p.first, c = p.second; if (cards[r][c] == -1) continue; // 如果這個位置的牌已取走已被設定為 -1,執行下一次 for 迴圈 int nr = r+1, nc = c+1; // 下一列 nr,下一欄 nc /* 向下找相同的牌 */ while(nr < n-1 && cards[nr][c] == -1) nr++; // 如果 nr 還可以加 1 而且這個位置的牌已取走,將 nr 加 1 if (nr <= n-1 && cards[nr][c] == cards[r][c]) { // 如果 nr 沒有出界,而且 {nr, c}、{r, c} 兩張牌相同 score += cards[r][c]; // score 加上牌面數字 cards[r][c] = -1; // 將這兩個位置的牌設為 -1 cards[nr][c] = -1; flag = true; // flag 設定為 True,繼續找下一輪 } /* 向右找相同的牌 */ while(nc < m-1 && cards[r][nc] == -1) nc++; // 如果 nc 還可以加 1 而且這個位置的牌已取走,將 nc 加 1 if (nc <= m-1 && cards[r][nc] == cards[r][c]) { // 如果 nc 沒有出界,而且 {n, nc}、{r, c} 兩張牌相同 score += cards[r][c]; // score 加上牌面數字 cards[r][c] = -1; // 將這兩個位置的牌設為 -1 cards[r][nc] = -1; flag = true; // flag 設定為 True,繼續找下一輪 } } } cout << score << "\n"; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`