# 10/22 APCS思路&想法 :thinking_face: --- # 第一題 機械鼠 :rat: ---- - 題目內容: 1. 有一隻勞贖在一個一維的路上(像數線一樣) 2. 在這條路上有n個食物 :cheese_wedge: 3. 老鼠會往食物多的方向走(左or右)(一維) :left_right_arrow: - 題目要求: 輸出老鼠吃到的食物數量跟最後的位置 ---- ### How to do 勒? :confused: 簡單來解的話這題就維護4個變數就好 1. Re(老鼠最右邊的食物位置) 2. Le(老鼠最左邊的食物位置) 3. Rnum(老鼠右邊食物數量) 4. Lnum(老鼠左邊食物數量) ---- ```cpp= #include <bits/stdc++.h> using namespace std; #define int long long #define ios ios_base::sync_with_stdio(0);cin.tie(0) #define endl '\n' #define debug(x) cerr<<#x<<x<<'\n'; int Re, Le, Lnum, Rnum; int x, n, in; //題目保證n是奇數 signed main(){ cin >> x >> n; Re = x; Le = x; for(int i=0; i<n; i++) { cin >> in; if(in > x){ Rnum++; if(in > Re) Re = in; } if(in < x) { Lnum++; if(in < Le) Le = in; } } if(Rnum > Lnum) cout << Rnum << " " << Re << endl; else cout << Lnum << " " << Le << endl; } ```  --- # 第二題 卡牌遊戲 :flower_playing_cards: ---- #### 題目內容: 1. 有一個桌遊，場上有n\*m個位置可以放卡片 2. 每張卡片上都有數字 3. 在 - ***兩張牌數字相同*** - ***兩張牌在同一行or列*** - ***兩張中間沒有被別種牌隔開*** - (P.S.沒有牌的空位置不算) 的情況下，玩家可以***拿走這兩張牌***，並得到數字大小的分數 4. 重覆到無牌可拿為止 ---- ### How to do 勒? - 不妨先想想如果你真的在玩這個桌遊會怎麼做 1. 看看場上有什麼牌 :face_with_raised_eyebrow: 2. 把一樣的拿掉 :negative_squared_cross_mark: 3. 重複 :repeat: 很多時候對於測資小的實作題這樣想挺有幫助的 :+1: ---- ## 一點想法: #### 拿過要消掉好煩先不理它 :smirk: - 開一個矩陣(array)存每格的卡 - 每次都掃過n\*m格的牌 - 對於每一張牌都往它的上、又、下、左看一次 - 找到一樣的就把它標成-1，並把score加上卡的點數 這樣一來，我們已經解決了上面的一、二點了 :+1: ---- ## 一些問題: :no_mouth: 1. 第三點怎麼辦，我怎麼知道要重複幾輪? 2. 拿走一些牌之後，萬一出現了新的可以消的怎麼辦? - ex: 1123325 - (2那組是在3那組削掉後才出現的) ---- ## 1解決の方法 - 針對不知道要做幾次的問題 設一個變數控制要不要繼續找 (bool flag) ```cpp= // 示意用only, pesudo code(偽代碼) while(flag) { flag = false; if(checkCards()) { takeCards(); flag = true; } } ``` ---- ## 2解決の方法 - 針對要跨過空位置找卡的問題 在往4個方向找時，如果看到的這個是0那就在往那個方向加找一次 ```cpp= // 示意用only, pesudo code(偽代碼) const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; int c_x, c_y; // 現在的i跟j for(int i=0; i<4; i++){ int reach = 1; while(board[c_x + reach*(dx[i])][c_y + reach*(dy[i])] == -1) { reach++; } // 然後再判斷找到的牌是否點數相同 } ``` ---- 最後的小提醒: ### 寫這種會在二維陣列中查找、搜尋or更改的題要注意邊界的檢查 :exploding_head: ---- ## Answer Code #### powered by Stanley Hsu :cat: ```cpp= #include <bits/stdc++.h> #define boost ios::sync_with_stdio(0);cin.tie(0) using namespace std; int main () { boost; const int dx[4] = {1,0,-1,0}; const int dy[4] = {0,1,0,-1}; int n, m, sum = 0, times, y, x; bool changed = true; bool done = false; cin >> n >> m; int arr[n][m]; for (int i =0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> arr[i][j]; } } while(changed) { changed = false; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] == -1) continue; for (int k = 0; k < 4; k++) { done = false; times = 1; while (1) { y = i+dy[k]*times; x = j+dx[k]*times; if (y >= 0 && y < n && x >= 0 && x < m) { if (arr[y][x] == arr[i][j]) { changed = true; sum += arr[y][x]; arr[y][x] = -1; arr[i][j] = -1; done = true; break; }else if (arr[y][x] == -1){ times++; }else{ break; } }else{ break; } } if (done) break; } } } } cout << sum; } ``` --- # 第三題 搬家 :derelict_house_building: ---- #### 題目內容: 1. 在一個n\*m的地圖上，有一些水管 2. 題目會輸入地圖的情況: - F: (可以接)右和下 - H: 左和右 - 7: 左和下 - I: 上和下 - X: 上、下、左和右 - L: 右和上 - J: 左和上 - 0: 沒有水管 ----  ---- ## 題目要求: ### 找出最大連在一起的水管區塊，並輸出它的水管數目 ---- ### 好像!跟之前教的BFS、DFS好像! 他就是之前庭院裡的水池那種題目的變化型 #### 加上檢查連不連得起來 跟記一下長度就好ㄌ --- 第四題我還沒交過你們XD