상어 중학교 C++

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
const int MAX = 21;
//검은색 -1, 무지개 0, 일반 1~M
int n, m;
int map[MAX][MAX];
int answer = 0;

vector<pair<int, int>> bl;
pair<int, int> middle;
int rain_num = 0;

vector<pair<int, int>> tmp;
pair<int, int> middle_tmp;
int rain_tmp = 0;

int visited[MAX][MAX];
struct MOVE { int x, y; };
MOVE mv[4] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int current_color;

void dfs(int mi, int mj) {
	visited[mi][mj] = 1;
	tmp.push_back(make_pair(mi, mj));
	if (map[mi][mj] == 0) {
		rain_tmp += 1;
	}
	else {
		if (mi < middle_tmp.first) {
			middle_tmp = make_pair(mi, mj);
		}
		else if (mi == middle_tmp.first) {
			if (mj < middle_tmp.second) {
				middle_tmp = make_pair(mi, mj);
			}
		}
	}
	for (int k = 0; k < 4; k++) {
		int movei = mi + mv[k].x;
		int movej = mj + mv[k].y;
		if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
			if ((map[movei][movej] == 0 || map[movei][movej] == current_color) && visited[movei][movej] == -1) {
				dfs(movei, movej);
			}
		}
	}
}
void clearrain() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				visited[i][j] = -1;
			}
		}
	}
}
bool FindBiggestBlock() {
	bool flag = false;
	bl.clear();
	middle = make_pair(-1, -1);
	rain_num = 0;
	memset(visited, -1, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j]> 0 && visited[i][j] == -1) {
				tmp.clear();
				rain_tmp = 0;
				middle_tmp = make_pair(i, j);
				current_color = map[i][j];
				dfs(i, j);

				if (tmp.size() >= 2 && tmp.size() - rain_tmp > 0) {
					if (tmp.size() > bl.size()) {
						bl = tmp;
						middle = middle_tmp;
						rain_num = rain_tmp;
					}
					else if (tmp.size() == bl.size()) {
						if (rain_tmp > rain_num) {
							bl = tmp;
							middle = middle_tmp;
							rain_num = rain_tmp;
						}
						else if (rain_tmp == rain_num) {
							if (middle_tmp.first > middle.first) {
								bl = tmp;
								middle = middle_tmp;
								rain_num = rain_tmp;
							}
							else if (middle_tmp.first == middle.first) {
								if (middle_tmp.second > middle.second) {
									bl = tmp;
									middle = middle_tmp;
									rain_num = rain_tmp;
								}
							}
						}
					}
				}
				clearrain();
			}
		}
	}
	answer += bl.size() * bl.size();
	for (int i = 0; i < bl.size(); i++) {
		map[bl[i].first][bl[i].second] = -2;
	}
	if (middle != make_pair(-1, -1))
		flag = true;
	return flag;
}
void Gravity() {
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] != -1 && map[i][j] != -2) {
				int movei = i + 1;
				int movej = j;
				while (movei < n && (map[movei][movej] == -2)) {
					movei += 1;
				}
				map[movei - 1][movej] = map[i][j];
				for (int k = i; k < movei - 1; k++) {
					map[k][movej] = -2;
				}
			}
		}
	}
}
void Rotate() {
	int map_tmp[MAX][MAX];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map_tmp[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map_tmp[n - j - 1][i] = map[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = map_tmp[i][j];
		}
	}
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	while (FindBiggestBlock()) {
		Gravity();
		Rotate();
		Gravity();
	}
	cout << answer << endl;
}