转珠游戏 难题解答 rookiepig

Question

Djhnj. 转珠游戏
时间限制：200ms   内存限制：64.0MB   代码提交间隔：1分钟(现在可以提交)  
试题来源：rookiepig
问题描述
转珠游戏是这样一种消除类的游戏，给定一个大小为  行  列的棋盘格，每个棋盘格中都放了一个珠子，珠子有颜色，游戏的方法是通过交换相邻两个珠子使得颜色相同的珠子连在一起，当颜色相同的珠子满足特定条件时就可以消除，消除的珠子越多得分越高。注意每个珠子都受重力影响，即如果消除后某个珠子下方没有珠子，该珠子会掉落，直到有珠子在其下方。

玩家进入游戏就会看到不同颜色的珠子放在格子中，举例如下：

115000
221000
332000
443000
554000
Data
其中数字 0 比较特殊，表示没有珠子，数字 1-6 表示 6 种不同颜色珠子。

玩家要选择一个珠子开始，这里选择位于第  行  列颜色为 的珠子开始，然后玩家连续进行  次向下交换的转珠，整个过程相当于在第三列上从上到下进行了  次相邻的交换（可以想象成第一行  这个珠子向下走到了最后一行，通过交换的方式走下去），那么棋盘会变成：

111000
222000
333000
444000
555000

玩家结束转珠后，开始进行消除。消除的规则是：从任何一个珠子开始沿着上、下、左、右四个方向之一有至少3个相同颜色的珠子连续即可全部消除该方向上的连续同色珠子。

所以上述玩家操作后，每行  个相连的珠子均可消除，消除后棋盘变为：

000000
000000
000000
000000
000000

现在给你一个开始的棋盘格状态，玩家开始转珠的起手位置，以及玩家中间一系列的移动操作，请你输出玩家结束操作并进行 1次 消除后棋盘的状态。

输入格式
首先输入棋盘的初始状态，共  行，每行为一个长度为  的字符串，保证字符串中只有数字字符 0-6;
接下来一行两个整数  ，中间用空格分开表示玩家从  行  列开始转珠。
最后有一行字符串，每个字符只能是 U, D, L, R（依次代表上、下、左、右）的一种，表示玩家一次转珠的方向，所以字符串的长度就是玩家转珠操作的步数。
输出格式
输出也是  行每行一个长度为 的字符串，表示经过玩家的转珠操作和 1次 消除后棋盘的状态。

样例输入1
115000
221000
332000
443000
554000
1 3
DDDD

样例输出1
000000
000000
000000
000000
000000

样例解释：见题目描述

样例输入2
000000
000000
000000
001100
323310
5 2
L

样例输出2
000000
000000
000000
000000
201110

样例解释：注意因为只允许发生一次消除，交换后最后一行的 333 消除后珠子掉落下来形成的 111 不会再次消除。

样例输入3
000000
000000
124542
653446
123456
4 3
URR

样例输出3
000000
000000
120002
655036
123056

样例解释：经过移动后版面为：

000000
000000
125432
654446
123456

4形成了十字形状，从中心的 4 看上下和左右都满足3个以上相连，所以整个十字消除。

样例输入4
100000
100000
210000
130000
114100
3 1
RDRDR

样例输出4
000000
000000
000000
000000
034200

样例解释：经过移动后版面为：

100000
100000
130000
104000
111200

左下角的 1 形成了L字形状，从左下角的 1 看上方和右方都满足3个以上相连，所以整个L字消除。

评测用例规模与约定
所有数据，保证起手位置和操作序列均合法，操作序列长度小于 ；不同测试点满足不同的性质：

测试点    性质
1    不会发生消除
2    只有 3 个相连的消除，消除后不会掉落
3    只有 3 个相连的消除
4    只有单独横向或者单独纵向的消除
5    只有十字消除
6    只有L字消除
7-10    没有任何限制

我用暴力尝试过了，写了好几百行，有点崩溃了，求各位帮给蒟蒻讲讲思路，给给代码。

Answer 1

下面的代码由AI生成，无法确定正确性，仅供参考:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 交换两个珠子的位置
void swap_beads(vector<vector<char>>& beads, int x1, int y1, int x2, int y2) {
    swap(beads[x1][y1], beads[x2][y2]);
}

// 在当前位置上下左右四个方向查找相同颜色的珠子
void dfs(vector<vector<char>>& beads, vector<vector<bool>>& visited, int x, int y) {
    if (x < 0 || x >= beads.size() || y < 0 || y >= beads[0].size() || visited[x][y]) {
        return;
    }
    visited[x][y] = true;
    char color = beads[x][y];
    int count = 1;
    // 向上查找
    int i = x - 1;
    while (i >= 0 && beads[i][y] == color) {
        visited[i][y] = true;
        count++;
        i--;
    }
    // 向下查找
    i = x + 1;
    while (i < beads.size() && beads[i][y] == color) {
        visited[i][y] = true;
        count++;
        i++;
    }
    // 向左查找
    int j = y - 1;
    while (j >= 0 && beads[x][j] == color) {
        visited[x][j] = true;
        count++;
        j--;
    }
    // 向右查找
    j = y + 1;
    while (j < beads[0].size() && beads[x][j] == color) {
        visited[x][j] = true;
        count++;
        j++;
    }
    // 如果有三个或以上相连的珠子，则将它们标记为空格
    if (count >= 3) {
        beads[x][y] = '0';
    }
    // 递归标记上下左右四个方向的珠子
    if (x - 1 >= 0 && beads[x - 1][y] == color) {
        dfs(beads, visited, x - 1, y);
    }
    if (x + 1 < beads.size() && beads[x + 1][y] == color) {
        dfs(beads, visited, x + 1, y);
    }
    if (y - 1 >= 0 && beads[x][y - 1] == color) {
        dfs(beads, visited, x, y - 1);
    }
    if (y + 1 < beads[0].size() && beads[x][y + 1] == color) {
        dfs(beads, visited, x, y + 1);
    }
}

// 消除珠子
void remove_beads(vector<vector<char>>& beads) {
    vector<vector<bool>> visited(beads.size(), vector<bool>(beads[0].size(), false));
    // 遍历所有珠子并进行消除
    for (int i = 0; i < beads.size(); i++) {
        for (int j = 0; j < beads[0].size(); j++) {
            if (!visited[i][j] && beads[i][j] != '0') {
                dfs(beads, visited, i, j);
            }
        }
    }
    // 重新排列珠子，使得消除的空位填充
    for (int j = 0; j < beads[0].size(); j++) {
        int idx = beads.size() - 1;
        for (int i = beads.size() - 1; i >= 0; i--) {
            if (beads[i][j] != '0') {
                beads[idx][j] = beads[i][j];
                if (idx != i) {
                    beads[i][j] = '0';
                }
                idx--;
            }
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<char>> beads(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> beads[i][j];
        }
    }
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        swap_beads(beads, x1, y1, x2, y2);
    }
    remove_beads(beads);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << beads[i][j];
        }
        cout << endl;
    }
    return 0;
}