21608번 상어 초등학교

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[21][21];
int ch[21][21];
int n,nn;
struct Loc {
	int x, y, student, room;
	Loc(int a, int b, int c, int d) {
		student = a;
		room = b;
		x = c;
		y = d;
	}
	bool operator<(const Loc& b) const {
		if (student != b.student) return student < b.student;
		if (room != b.room) return room < b.room;
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
};
int main() {
	//freopen("in1.txt", "rt", stdin);
	cin >> n;
	nn = n * n;
	vector<vector<int> > like(nn + 1, vector<int>(5));
	vector<vector<int> > dong(nn + 1, vector<int>(5));
	pair<int, int> V[401];
	for (int i = 0; i < nn; i++) {
		int L;
		cin >> L;
		like[i][0] = L;
		for (int j = 1; j < 5; j++) {
			int t;
			cin >> t;
			like[i][j] = t;
			dong[L][j] = t;
		}
		
		
	}
	
	for (int i = 0; i < nn; i++) {
		//첫 번째 학생 처음부터 시작
		int num = like[i][0];
		priority_queue<Loc> Q;
		for (int a = 1; a <= n; a++) {
			for (int b = 1; b <= n; b++) {
				if (map[a][b] != 0) continue;
				int student = 0;
				int room = 0;
				for (int k = 0; k < 4; k++) {
					int xx = a + dx[k];
					int yy = b + dy[k];
					if (xx > n || xx <= 0 || yy > n || yy <= 0) continue;
					if (map[xx][yy] == 0) {
						room++;
						//if (num == 3) cout << "room"<<room <<" xx"<<xx<<" yy"<<yy<< '\n';
					}
					if (map[xx][yy] == like[i][1] || map[xx][yy] == like[i][2] || map[xx][yy] == like[i][3] || map[xx][yy] == like[i][4]) {
						student++;
					}
				}
				Q.push(Loc(student, room, a, b));
				//if (num == 3) cout << "stu "<<student <<"room "<<room<<"a " << a << "b " << b << '\n';
			}
		}
		int x=0, y=0;
		x = Q.top().x;
		y = Q.top().y;
		map[x][y] = num;
		V[num] = make_pair(x, y);
		//cout << "x " << x << "y " << y << "num " << num << '\n';
	}
	int ans = 0;
	for (int i = 1; i <= nn; i++) {
		//첫 번째 학생 처음부터 시작
		int a, b;
		tie(a, b) = V[i];
		int L = map[a][b];
		int love = 0;
		for (int k = 0; k < 4; k++) {
			int xx = a + dx[k];
			int yy = b + dy[k];
			if (xx > n || xx <= 0 || yy > n || yy <= 0) continue;
			if (map[xx][yy] == dong[L][1] || map[xx][yy] == dong[L][2] || map[xx][yy] == dong[L][3] || map[xx][yy] == dong[L][4]) {
				love++;
			}
		}
		if (love == 1) ans += 1;
		else if (love == 2) ans += 10;
		else if (love == 3) ans += 100;
		else if (love == 4) ans += 1000;

	}
	cout << ans << '\n';
	return 0;
}