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 没有任何限制
我用暴力尝试过了，写了好几百行，有点崩溃了，求各位帮给蒟蒻讲讲思路，给给代码。
下面的代码由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;
}