UVa758 - The Same Game(DFS)

題目大意

一個小遊戲(類似於 candy crush)，目標是拿到最大分，規則與分數如下：

• 有三種顏色的石頭，只要有三顆相同顏色的石頭在一起就可以被消除掉
• 如果石頭有被消除掉，當前的格子為空，那上面的石頭會替補上來(column)
• 如果有一整排(column)為空，那將右邊的那些石頭全部都往左移一排(column)
• 分數計算是消掉的石頭(m) \((m-2) ^ 2\)
• 如果全部的石頭都被消去就多獲得 1000 分

一個好的策略是從左下底端開始尋找，找出有最大堆顏色的石頭將它們消去，不斷重複至不能消除
必須要輸出如何消除、總共分數、剩下幾顆。

題目連結

觀念重點

• 理解題目英文
• 這題屬於複雜操作題，腦袋清晰地寫
• 需要不斷反覆除錯

分析：

麻煩的題目…，寫這題需要高度的專心力與注意力才可以把這題寫好…。

這題不難，就是依照題目的要求直接暴力解即可，不太需要想甚麼優化的問題，測資並不大。

題外話：我倒是花了一堆時間在想要怎麼把程式碼精簡，最終還是放棄QQ。

參考來源

Uva758 - The Same Game - txya900619

心得

這題真的夠了..，一年寫一次這種題目就好了，我都想稱他為麻煩大題了QQ，我寫完後硬是讓自己逃避了 3,4 hr 再來 debug 這題，很怕有大錯讓自己要重改之類的RRRR。

總之，希望自己的程式能力速度可以變快。

透過學習立委的程式碼，讓我覺得自己變聰明了些。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

程式碼很長，希望大家都能專心QQ。

hash 模式
R = 1
G = 2
B = 3
消除的石頭(0) = 0;

#include <iostream>
#include <bits/stdc++.h>
#define BX 10 // 題目 X 最大邊界
#define BY 15 // 題目 Y 最大邊界
#define extra 5 //擴增陣列，以防超出
#define LOCAL
using namespace std;
int graph[BX+extra][BY+extra], visit[BX+extra][BY+extra]; 
//graph 遊戲的圖 visit 判斷有沒有走過，用於一開始的搜尋
int n, kase = 0; //kase 輸出當前第幾測資
string s; //輸入題目陣列元素用
map<char, int> mp; // char hash 成 int
map<int, char> mp2; // int hash 成 char

int dfs_search(int x, int y, int value){ //用來搜尋同樣顏色的石頭最大面積
    if(x < 0 || y < 0 || x > BX || y > BY) return 0; //超出邊界
    if(visit[x][y] == 1 || graph[x][y] != value) return 0; //已被走訪過 或 不同顏色石頭

    visit[x][y] = 1; //走訪過
    int cnt = 1; //最大面積，還沒往其他地方探索，因此只有自己所以 1
    cnt += dfs_search(x-1, y, value); //往四個地方進行走訪，value 是一開始搜尋的石頭顏色
    cnt += dfs_search(x+1, y, value);
    cnt += dfs_search(x, y-1, value);
    cnt += dfs_search(x, y+1, value);
    return cnt; //回傳最大面積
}

void dfs_remove(int x, int y, int value){ //用來移除石頭，在找到最大面積石頭時使用
    if(x < 0 || y < 0 || x > BX || y > BY) return; //超出邊界
    if(graph[x][y] != value) return; //顏色不同石頭
    graph[x][y] = 0; //移除，因此變零
    dfs_remove(x-1, y, value); //四個方向移除
    dfs_remove(x+1, y, value);
    dfs_remove(x, y-1, value);
    dfs_remove(x, y+1, value);
}

void refresh(){ //將消除的石頭位置放上新石頭
    int k = 0; //k 用來判斷位置
    for(int i = 0; i < BX; i++){ //rule 1 題目大意的規則 2
        for(int j = 0; j < BY; j++){
            if(graph[i][j] == 0){ //表示這裡有被移除的石頭
                k = i+1; //要跟上面沒有被移除的石頭的 x index 
                while(k < BX){ //如果沒有超出邊界，就繼續
                    if(graph[k][j] != 0){ //index k 的石頭沒有被消除
                        swap(graph[i][j], graph[k][j]); //那就交換
                        break; // 消除成功，所以退出
                    }
                    k++; //沒有找到，所以 k++
                }
                //至於為甚麼要這樣找，不是直接跟上一個交換?
                //因為有可能上面三個都被移除，那移除石頭交換本身沒意義
            }
        }
    }
    //注意，這裡是將 y index 放在外迴圈
    for(int j = 0; j < BY; j++){ //rule2 題目大意的規則 3
        int sum = 0; //sum 用來判斷那行 column 是否都是空的
        for(int i = 0; i < BX; i++) sum += graph[i][j]; 
        //因為 hash 後的數值都大於 1，因此如果等於 0 一定都沒有
        if(sum == 0){
            k = j+1; //用來交換的 index 
            while(k < BY){  //如果沒有超出邊界，就繼續
                if(graph[0][k] != 0){ //index k 的石頭沒有被消除
                    for(int i = 0; i < BX; i++) swap(graph[i][j], graph[i][k]);
                    //整行交換
                    break;  // 消除成功，所以退出
                }
                k++; //沒有找到，所以 k++
            }
        }
    }

}

void visit_debug(){ //debug 用
    cout << '\n';
    for(int i = BX-1; i >= 0; i--){
        for(int j = 0; j <= BY-1; j++) cout << visit[i][j] << ' ';
        cout << '\n';
    }
}

void graph_debug(){ //debug 用
    cout << '\n';
    for(int i = BX-1; i >= 0; i--){
        for(int j = 0; j <= BY-1; j++) cout << mp2[graph[i][j]] << ' ';
        cout << '\n';
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCLA
    cin >> n;
    mp['R'] = 1; mp['G'] = 2; mp['B'] = 3; //hash 
    mp2[1] = 'R'; mp2[2] = 'G'; mp2[3] = 'B'; mp2[0] = '0'; //hash 
    while(n--){
        cout << "Game " << ++kase << ":\n\n"; //輸出當前 case 
        for(int i = BX-1; i >= 0; i--){ //輸入資料
            cin >> s;
            for(int j = 0; j < BY; j++) graph[i][j] = mp[s[j]]; 
            //注意這裡的 s[j]，不是 s[i]
        }

        int ans = 0, score, step = 1, remain = BX*BY; 
        //ans 答案 score 當前分數 step 移動第幾次 remain 還有幾個石頭沒有被消除
        while(1){ //不斷輪迴，嘗試消除石頭
            int block = 0, max_block = 0, mx, my; 
            //block 當前區塊 max_block 最大區塊 mx my 最大區塊的 x,y
            memset(visit, 0, sizeof(visit)); //重設為 0
            for(int j = 0; j < BY; j++){ //對每一個石頭進行搜尋
                for(int i = 0; i < BX; i++){
                    if(visit[i][j] == 0 && graph[i][j] != 0) block = dfs_search(i, j, graph[i][j]);
                    //如果這個石頭沒有被搜尋，就 dfs 這邊的石頭
                    if(max_block < block){ //搜尋的區塊比之前搜尋的還大
                        max_block = block;
                        mx = i; my = j;
                    }
                }
            }
            //visit_debug();
            //cout << "max_block " << max_block << '\n';

            if(max_block < 2) break; //如果搜尋到的最大區塊 < 2 表示沒有辦法在消除，就離開迴圈
            remain -= max_block; //減掉最大的區塊
            score = (max_block - 2) * (max_block - 2); //計算這次分數
            cout << "Move "<< step++ << " at (" << mx+1 << "," << my+1 << \
             "): removed " << max_block << " balls of color "<< mp2[graph[mx][my]] << ", got " << score << " points.\n";
            //輸出這次步驟，這裡輸出顏色用 mp2
            ans += score; //加上這次分數
            dfs_remove(mx, my, graph[mx][my]); //移除最大區塊的石頭
            refresh(); //將題目大意的規則 2 and 3 重整一次
            //graph_debug(); //debug
        }
        if(remain == 0) ans += 1000; //沒有剩下的石頭可以拿到 1000 分
        //輸出最後資訊
        cout << "Final score: " << ans << ", with " << remain << " balls remaining.\n";
        if(n != 0) cout << '\n'; //最後一個不斷行兩次，因為題目要求間隔斷行
    }
    return 0;
}