coding_test_study/210319_BOJ_11559.cpp at main · flylofty/coding_test_study · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int deletePuyo;
const int Row = 12;
const int Col = 6;
char map[Row][Col];
bool visit[Row][Col];
queue<pair<int, int>> q;
vector<pair<int, int>> crush;
vector<bool> changed(Col);
int dir[4][2]{ {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

bool isPuyo(char p) {
	if (p == 'R' || p == 'G' || p == 'B' || p == 'P' || p == 'Y')
		return true;
	else
		return false;
}

void changeMap() {

	for (int j = 0; j < Col; ++j) {

		if (changed[j] == false)
			continue;

		for (int i = Row - 1; i >= 0; --i) {

			if (isPuyo(map[i][j])) {
				int k = i + 1;
				while (map[k][j] == '.' && k < Row)
					k++;

				if (k <= 12 && map[k - 1][j] == '.') {
					map[k - 1][j] = map[i][j];
					map[i][j] = '.';
				}
			}
		}
	}
}

void bfs(int x, int y, char puyo) {

	crush.push_back({ x, y });
	q.push({ x, y });
	visit[x][y] = true;

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i) {
			int n_x = x + dir[i][0];
			int n_y = y + dir[i][1];

			if (n_x < 0 || n_x >= Row || n_y < 0 || n_y >= Col)
				continue;

			if (map[n_x][n_y] != puyo || visit[n_x][n_y])
				continue;

			crush.push_back({ n_x, n_y });
			q.push({ n_x, n_y });
			visit[n_x][n_y] = true;
		}
	}

	if (crush.size() >= 4) {
		for (int i = 0; i < crush.size(); ++i) {
			map[crush[i].first][crush[i].second] = '.';
			changed[crush[i].second] = true;
			deletePuyo--;
		}
	}
	crush.clear();
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < Row; ++i) {
		for (int j = 0; j < Col; ++j) {
			cin >> map[i][j];
		}
	}

	int res = 0;

	while (1) {

		for (int i = 0; i < Col; ++i)
			changed[i] = false;

		for (int i = 0; i < Row; ++i) {
			for (int j = 0; j < Col; ++j) {
				visit[i][j] = false;
			}
		}

		deletePuyo = 0;
		for (int i = 0; i < Row; ++i) {
			for (int j = 0; j < Col; ++j) {

				if (isPuyo(map[i][j]) && !visit[i][j])
					bfs(i, j, map[i][j]);
			}
		}

		if (deletePuyo == 0)
			break;

		changeMap();
		res++;
	}

	cout << res << "\n";
	return 0;
}