---
tags: uva
---
# Uva758 - The Same Game
## 題目大意
此遊戲由三種不同顏色的球組成，並將兩個同顏色且相鄰(上下左右)的球，定義為**cluster**，此遊戲的每一步就是玩家選擇一含有至少兩個球的**cluster**，並消除他，當消除發生後，接下來會發生兩件事
1. 若球的下方有空格的話將球往下移填滿空格
2. 若球左方有一整直行消失，則將球左移

而分數則是每步消去的球數量 $(m-2)^2$，若最後有消完所有球，額外加 1000 分
我們的工作是寫出一個程式，模擬每次都消去最大團的**cluster**的玩家，輸出他每步做的事以及最後得分。
## 重點觀念

## 分析
先 dfs 找最大 cluster，找到後刪掉，並依照題目重整
## 程式題目碼

#include <cstring>
#include <iostream>

using namespace std;

char graph[10][20];
bool used[10][20];

int dfs(int x, int y, char color) {
    int count = 1;
    if (x > 9 || x < 0 || y > 14 || y < 0) {
        return 0;
    }
    if (color != graph[x][y] || used[x][y]) {
        return 0;
    }
    used[x][y] = true;
    count += dfs(x + 1, y, color);
    count += dfs(x - 1, y, color);
    count += dfs(x, y + 1, color);
    count += dfs(x, y - 1, color);
    return count;
}
void remove(int x, int y, char color) {
    if (x > 9 || x < 0 || y > 14 || y < 0) {
        return;
    }
    if (color != graph[x][y]) {
        return;
    }
    graph[x][y] = 0;
    remove(x + 1, y, color);
    remove(x - 1, y, color);
    remove(x, y + 1, color);
    remove(x, y - 1, color);
    return;
}
void refresh() {
    for (int i = 0; i < 15; i++) {
        for (int j = 9; j >= 0; j--) {
            if (graph[j][i] == 0) {
                for (int k = j + 1; k < 10; k++) {
                    graph[k - 1][i] = graph[k][i];
                    if (k == 9) {
                        graph[k][i] = 0;
                    }
                }
            }
        }
    }
    for (int i = 14; i >= 0; i--) {
        bool is_empty_col = true;
        for (int j = 0; j < 10; j++) {
            if (graph[j][i] != 0) {
                is_empty_col = false;
            }
        }
        if (is_empty_col) {
            for (int k = i + 1; k < 15; k++) {
                for (int j = 0; j < 10; j++) {
                    graph[j][k - 1] = graph[j][k];
                    if (k == 14) {
                        graph[j][k] = 0;
                    }
                }
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int step = 1, score = 0, remain = 15 * 10;
        cout << "Game " << i << ":" << endl
             << endl;

        for (int i = 9; i >= 0; i--) {
            cin >> graph[i];
        }
        while (1) {
            int max_count = 0, x, y, color;
            memset(used, false, sizeof(used));
            for (int i = 0; i < 15; i++) {
                for (int j = 0; j < 10; j++) {
                    int count = 0;
                    if (!used[j][i] && graph[j][i]) {
                        count = dfs(j, i, graph[j][i]);
                    }

                    if (count >= 2 && max_count < count) {
                        max_count = count;
                        x = j, y = i;
                        color = graph[j][i];
                    }
                }
            }

            if (!max_count) {
                break;
            }
            cout << "Move " << step << " at (" << x + 1 << "," << y + 1 << "): removed " << max_count << " balls of color " << string(1, color) << ", got " << (max_count - 2) * (max_count - 2) << " points." << endl;

            remove(x, y, graph[x][y]);

            refresh();

            score += (max_count - 2) * (max_count - 2);
            remain -= max_count;
            step++;
        }
        if (remain == 0) {
            score += 1000;
        }
        cout << "Final score: " << score << ", with " << remain << " balls remaining." << endl;
        if (i != t) {
            cout << endl;
        }
    }

    return 0;
}