C++实现灭星星游戏算法 - 消除相同颜色星星

1. 游戏规则

灭星星是一款经典的消除类游戏，其规则如下：

点击一个星星，该星星以及与之相邻且颜色相同的星星将被消除。- 相邻定义为边相邻，不包括点相邻。- 如果点击的星星周围没有颜色相同的星星，则该星星不会被消除。- 星星消除后，上方的星星会下落填补空位。- 如果一整列都被消除，则右侧的星星会向左平移一位。

2. 算法描述

2.1 输入描述

每组测试数据包含以下内容：

第一行：两个整数 n 和 m (1<=n<=200,1<=m<=500)，分别表示 n 阶矩阵和 m 次操作。- 接下来 n 行：每行包含 n 个整数 a[i,j] (1<=ai,j<=7)，表示星星的颜色，相同的数字表示相同的颜色。- 接下来 m 行：每行包含两个整数 x,y (1<=x,y<=n)，表示点击的位置。

2.2 输出描述

对于每次操作，输出一行：

如果点击位置有星星，且消除的星星个数超过 2 个，则输出消除的星星个数。- 如果点击位置有星星，但没有星星被消除，则输出 'only one!'。- 如果点击位置没有星星，则输出 'empty!'。

2.3 算法思路

数据结构： 使用二维数组 matrix 存储游戏矩阵，使用二维数组 visited 标记星星是否被访问过。2. 深度优先搜索（DFS）： 对于每次点击，使用 DFS 算法遍历与点击位置颜色相同的相邻星星，并将它们标记为已访问。3. 星星消除： 如果 DFS 遍历到的星星个数大于 2，则将这些星星从 matrix 中移除，并将 visited 数组重置。4. 星星下落和平移： 星星消除后，需要进行星星下落和平移操作，以保持游戏矩阵的完整性。

3. C++代码实现cpp#include #include

using namespace std;

// 定义矩阵的大小const int MAXN = 205;

// 定义颜色的个数const int MAX_COLOR = 7;

// 定义方向数组const int dx[] = {-1, 0, 1, 0};const int dy[] = {0, 1, 0, -1};

// 矩阵的大小int n;

// 矩阵int matrix[MAXN][MAXN];

// 标记矩阵，用于判断星星是否被访问过bool visited[MAXN][MAXN];

// 记录已消除的星星个数int countOfStars;

// dfs遍历相邻的星星，并将其标记为已访问void dfs(int x, int y, int color) { // 将当前位置标记为已访问 visited[x][y] = true; // 增加已消除的星星个数 countOfStars++;

// 遍历四个方向    for (int i = 0; i < 4; i++) {        int nx = x + dx[i];        int ny = y + dy[i];

    // 判断相邻位置是否在矩阵范围内，并且颜色相同且未被访问过        if (nx >= 0 && nx < n && ny >= 0 && ny < n && matrix[nx][ny] == color && !visited[nx][ny]) {            // 继续遍历相邻的星星            dfs(nx, ny, color);        }    }}

int main() { // 读取矩阵的大小和操作次数 int m; cin >> n >> m;

// 读取矩阵的颜色    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            cin >> matrix[i][j];        }    }

// 执行每次操作    for (int k = 0; k < m; k++) {        // 读取点击的位置        int x, y;        cin >> x >> y;

    // 初始化标记矩阵和已消除的星星个数        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                visited[i][j] = false;            }        }        countOfStars = 0;

    // 判断点击位置是否有星星        if (matrix[x - 1][y - 1] == 0) {            cout << 'empty!' << endl;        } else {            // dfs遍历相邻的星星            dfs(x - 1, y - 1, matrix[x - 1][y - 1]);

        // 判断消除的星星个数            if (countOfStars > 2) {                cout << countOfStars << endl;            } else {                cout << 'only one!' << endl;            }

        // 将消除的星星标记为0，并且让上方的星星下落            for (int j = 0; j < n; j++) {                for (int i = n - 1; i >= 0; i--) {                    if (visited[i][j]) {                        matrix[i][j] = 0;                        // 上方的星星下落                        for (int k = i - 1; k >= 0; k--) {                            if (matrix[k][j] != 0) {                                matrix[i][j] = matrix[k][j];                                matrix[k][j] = 0;                                break;                            }                        }                    }                }            }

        // 将左侧的星星向右平移            for (int j = 0; j < n - 1; j++) {                if (matrix[n - 1][j] == 0) {                    for (int i = 0; i < n; i++) {                        matrix[i][j] = matrix[i][j + 1];                        matrix[i][j + 1] = 0;                    }                }            }        }    }

return 0;}

4. 总结

本文介绍了如何使用 C++ 实现灭星星游戏的算法，并提供了详细的代码实现。该算法主要使用了深度优先搜索（DFS）算法来查找和消除相邻的星星，并通过矩阵操作实现星星的下落和平移。希望本文能够帮助读者更好地理解和掌握该算法。