상어 중학교

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

21609번: 상어 중학교

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 21;
int n, m;
int map[MAX][MAX];
int visited[MAX][MAX];
struct MOVE { int x, y; };
MOVE mv[4] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
struct BL {
	vector <pair<int, int>> bl;
	pair<int, int> middle;
	int rainbow = 0;
};
BL block, temp;
void dfs(int i, int j, int color) {
	temp.bl.push_back(make_pair(i, j));
	visited[i][j] = 1;
	for (int k = 0; k < 4; k++) {
		int mi = i + mv[k].x;
		int mj = j + mv[k].y;
		if (mi >= 0 && mi < n && mj >= 0 && mj < n && visited[mi][mj] == -1) {
			if (map[mi][mj] == color || map[mi][mj] == 0) {
				if (map[mi][mj] == 0) temp.rainbow += 1;
				else {
					if (mi < temp.middle.first) temp.middle = make_pair(mi, mj);
					else if (mi == temp.middle.first && mj < temp.middle.second) temp.middle = make_pair(mi, mj);
				}
				dfs(mi, mj, color);
			}
		}
	}
}
void printmap() {
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}
int main(void) {
	int answer = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	bool flag = true;
	while (flag) {
		memset(visited, -1, sizeof(visited));
		flag = false;
		block.bl.clear();
		block.rainbow = 0;
		block.middle = make_pair(21, 21);
		//1번 과정
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j]> 0 && visited[i][j] == -1) {
					temp.bl.clear();
					temp.rainbow = 0;
					temp.middle = make_pair(i, j);
					dfs(i, j, map[i][j]);
					if (temp.bl.size() < 2) continue;
					flag = true;
					if (temp.bl.size() > block.bl.size()) block = temp;
					else if (temp.bl.size() == block.bl.size()) {
						if (temp.rainbow > block.rainbow) block = temp;
						else if (temp.rainbow == block.rainbow) {
							if (temp.middle.first > block.middle.first) block = temp;
							else if (temp.middle.first == block.middle.first) {
								if (temp.middle.second > block.middle.second)
									block = temp;
							}
						}
					}
				}
				for (int ii = 0; ii < n; ii++) {
					for (int jj = 0; jj < n; jj++) {
						if (map[ii][jj] == 0) visited[ii][jj] = -1;
					}
				}
			}
		}
		//2번과정
		answer += block.bl.size() * block.bl.size();
		for (int k = 0; k < block.bl.size(); k++) {
			map[block.bl[k].first][block.bl[k].second] = -2;
		}
		//3번 과정(중력)
		for (int jj = 0; jj < n; jj++) {
			int ii = n - 2;
			while (ii >= 0) {
				if (map[ii][jj] != -1 && map[ii + 1][jj] == -2) {
					int k = ii + 1;
					while (k < n) {
						if (map[k + 1][jj] != -2) break;
						k += 1;
					}
					map[k][jj] = map[ii][jj];
					map[ii][jj] = -2;
				}
				ii -= 1;
			}
		}
		int tp[MAX][MAX];
		for (int ii = 0; ii < n; ii++) {
			for (int jj = 0; jj < n; jj++) {
				tp[ii][jj] = map[ii][jj];
			}
		}
		//4번 과정(회전)
		for (int ii = 0; ii < n; ii++) {
			for (int jj = 0; jj < n; jj++) {
				map[n - jj - 1][ii] = tp[ii][jj];
			}
		}
		//5번 과정(중력)
		for (int jj = 0; jj < n; jj++) {
			int ii = n - 2;
			while (ii >= 0) {
				if (map[ii][jj] != -1 && map[ii + 1][jj] == -2) {
					int k = ii + 1;
					while (k < n) {
						if (map[k + 1][jj] != -2) break;
						k += 1;
					}
					map[k][jj] = map[ii][jj];
					map[ii][jj] = -2;
				}
				ii -= 1;
			}
		}
	}
	cout << answer << endl;
}