USACO-Silver-Mooyo Mooyo

一.题目描述

With plenty of free time on their hands (or rather, hooves), the cows on Farmer John's farm often pass the time by playing video games. One of their favorites is based on a popular human video game called Puyo Puyo; the cow version is of course called Mooyo Mooyo.

The game of Mooyo Mooyo is played on a tall narrow grid NN cells tall (1≤N≤1001≤N≤100) and 10 cells wide. Here is an example with N=6N=6:

0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

Each cell is either empty (indicated by a 0), or a haybale in one of nine different colors (indicated by characters 1..9). Gravity causes haybales to fall downward, so there is never a 0 cell below a haybale.

Two cells belong to the same connected region if they are directly adjacent either horizontally or vertically, and they have the same nonzero color. Any time a connected region exists with at least KK cells, its haybales all disappear, turning into zeros. If multiple such connected regions exist at the same time, they all disappear simultaneously. Afterwards, gravity might cause haybales to fall downward to fill some of the resulting cells that became zeros. In the resulting configuration, there may again be connected regions of size at least KK cells. If so, they also disappear (simultaneously, if there are multiple such regions), then gravity pulls the remaining cells downward, and the process repeats until no connected regions of size at least KK exist.

Given the state of a Mooyo Mooyo board, please output a final picture of the board after these operations have occurred.

 

简单阐述一下：其实就是消消乐的规则， 如果一些相邻的数字相同，那么他们就形成一个连通块并同时消掉，这是他们位置上的数字都变成0，接下来会发生下落，也就是非0的数字会沉底。下面我们来看看这道题的思路

二.解题思路 

这道题可以被我们分解为三个部分

1.找到连通块

2.将连通块内的数字都变成0

3.完成下落

第一个步骤很显然用dfs完成并标记，第二个部分就直接遍历并标0，第三个部分我们引入指针，不断去查找非零数字并调换0和非0数字的位置。这样我们就完成了，下面展示代码

三.代码

//Mooyo Mooyo 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 5;
int n, k;
char a[maxn][15];
bool used[maxn][15];i
bool exist;
int sum;

int dx[4] = {0, 1, -1, 0};

int dy[4] = {1, 0, 0, -1};

void dfs(int x, int y, int z) {
	used[x][y] = 1;
	for (int i = 0; i <= 3; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (used[xx][yy] == 0 && a[xx][yy] == z) {
			sum++;
			dfs(xx, yy, z);
		}
	}
}

void clearout() {
	for (int ii = 1; ii <= n; ii++) {
		for (int jj = 1; jj <= 10; jj++) {
			if (used[ii][jj] ) {
				a[ii][jj] = '0';
			}
		}
	}
}

void gravity() {
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= 10; j++) {
			if (a[i][j] != '0') {
				int tmp = i;
				while (a[tmp + 1][j] == '0' && tmp <= n && tmp >= 1) {
					tmp++;
				}
				if (tmp != i) {
					a[tmp ][j] = a[i][j];
					a[i][j] = '0';
				}
			}
		}
	}
}

int main() {
	//freopen("mooyomooyo.in", "r", stdin);
	//freopen("mooyomooyo.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 10; j++) {
			cin >> a[i][j];
		}
	}
	exist = 1;
	while (exist) {
		exist = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 10; j++) {
				if (a[i][j] != '0') {
					sum = 1;
					memset(used, 0, sizeof(used));
					dfs(i, j, a[i][j]);
					if (sum >= k) {
						clearout();
						exist = 1;
					}
				}
			}
		}
		if (exist) {
			gravity();
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 10; j++) {
			cout << a[i][j];
		}
		cout << endl;
	}
	return 0;
}

四.总结

对于二维地图连通块类型的问题，有这几点需要注意

1.每次dfs之前要进行各种数组和变量的清零

2.要注意边界问题

3.对于同一张地图需要多次遍历的问题：我们建立一个bool变量，来记录每次遍历是否有我们需要的条件，如此题中，一次遍历之后还找不到连通块我们就跳出循环。注意每次遍历之前要现将这个旗子扳倒，整个遍历过程中如果找到符合条件就把旗子扶起来。

4.注意那些操作实在dfs的操作里进行的（对于每一个单位单独操作）哪一些是每一次dfs前就提前操作的（对于连通块整体的变量）