消消乐

问题描述

消消乐游戏在一个包含有 n (n ≤ 30)行 m (m ≤ 30)列的棋盘上进行，棋盘的每个格子都有一种颜色的棋子。当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。
一个棋子可能在某一行和某一列同时被消除。

Input

输入第一行包含两个整数 n,m，表示行数和列数
接下来 n 行 m 列，每行中数字用空格隔开，每个数字代表这个位置的棋子的颜色。数字都大于 0。

Output

输出 n 行 m 列，每行中数字用空格隔开，输出消除之后的棋盘。（如果一个方格中的棋子被消除，则对应的方格输出 0，否则输出棋子的颜色编号。）

Sample

Input: 
4 5
2 2 3 1 2
3 4 5 1 4
2 3 2 1 3
2 2 2 4 4
Output: 
2 2 3 0 2
3 4 5 0 4
2 3 2 0 3
0 0 0 4 4


Input: 
4 5
2 2 3 1 2
3 1 1 1 1
2 3 2 1 3
2 2 3 3 3
Output: 
2 2 3 0 2
3 0 0 0 0
2 3 2 0 3
2 2 0 0 0

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

咋一看好像是广搜，但其实暴力搜2次就行，而且广搜不好确定起点。

暴力做法是每行，搜出连着的数，置负。然后每列，搜出连着的数，置负。

输出的时候若是负数，则输出0，否则原样输出。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 50;
int arr[maxN][maxN];
int arr2[maxN][maxN];

void solve(int n, int m) {
	for (int i = 0; i < n; i++) {
		vector<int> ve;
		for (int j = 0; j < m; j++) {
			if (!ve.empty()) {
				int x = ve.back();
				if (arr[i][x] != arr[i][j]) {
					if (ve.size() > 2) {
						for (int k = ve.front(); k <= ve.back(); k++)
							arr2[i][k] = (-1) * abs(arr2[i][k]);
					}
					ve.clear();
				}
			}
			ve.push_back(j);
			if (j == m - 1 && ve.size() > 2) {
				for (int k = ve.front(); k <= ve.back(); k++)
					arr2[i][k] = (-1) * abs(arr2[i][k]);
				ve.clear();
			}
		}
	}

	for (int j = 0; j < m; j++) {
		vector<int> ve;
		for (int i = 0; i < n; i++) {
			if (!ve.empty()) {
				int x = ve.back();
				if (arr[x][j] != arr[i][j]) {
					if (ve.size() > 2) {
						for (int k = ve.front(); k <= ve.back(); k++)
							arr2[k][j] = (-1) * abs(arr2[k][j]);
					}
					ve.clear();
				}
			}
			ve.push_back(i);
			if (i == n - 1 && ve.size() > 2) {
				for (int k = ve.front(); k <= ve.back(); k++)
					arr2[k][j] = (-1) * abs(arr2[k][j]);
				ve.clear();
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr2[i][j] < 0)
				cout << 0 << " ";
			else
				cout << arr2[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {
	int n, m;
	while (!(cin >> n >> m).eof()) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				cin >> arr[i][j];
				arr2[i][j] = arr[i][j];
			}
		solve(n, m);
	}

	return 0;
}