상어 초등학교 C++

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

21608번: 상어 초등학교

 

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

using namespace std;
const int MAX = 25;
int n;
vector<vector<int>> fav(625);
int answer = 0;
vector<int> turn;
struct MOVE { int x, y; };
MOVE mv[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int map[MAX][MAX];

void FindSeat(int turn) {
	pair<int, int> select= make_pair(-1,-1);
	int emp = 0;
	int near = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (map[i][j] == 0) {
				int tmp_emp = 0;
				int tmp_near = 0;

				for (int k = 0; k < 4; k++) {
					int movei = i + mv[k].x;
					int movej = j + mv[k].y;

					if (movei > 0 && movei <= n && movej > 0 && movej <= n) {
						if (map[movei][movej] == 0)
							tmp_emp += 1;
						else if (find(fav[turn].begin(), fav[turn].end(), map[movei][movej]) != fav[turn].end())
							tmp_near += 1;
					}
				}
				if (select == make_pair(-1, -1)) {
					select = make_pair(i, j);
					emp = tmp_emp;
					near = tmp_near;
				}
				if (tmp_near > near) {
					select = make_pair(i, j);
					emp = tmp_emp;
					near = tmp_near;
				}
				else if (tmp_near == near) {
					if (tmp_emp > emp) {
						select = make_pair(i, j);
						emp = tmp_emp;
						near = tmp_near;
					}
					else if (tmp_emp == emp) {
						if (select.first > i) {
							select = make_pair(i, j);
							emp = tmp_emp;
							near = tmp_near;
						}
						else if (select.first == i) {
							if (select.second > j) {
								select = make_pair(i, j);
								emp = tmp_emp;
								near = tmp_near;
							}
						}
					}
				}
			}
		}
	}
	map[select.first][select.second] = turn;
}

int main(void) {
	cin >> n;

	memset(map, 0, sizeof(0));
	for (int i = 0; i < n*n; i++) {
		int student,i1, i2, i3, i4;
		cin >> student >> i1 >> i2 >> i3 >> i4;
		turn.push_back(student);
		fav[student].push_back(i1);
		fav[student].push_back(i2);
		fav[student].push_back(i3);
		fav[student].push_back(i4);
	}

	for (int i = 0; i < turn.size(); i++) {
		FindSeat(turn[i]);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int count = 0;
			for (int k = 0; k < 4; k++) {
				int movei = i + mv[k].x;
				int movej = j + mv[k].y;

				if (movei > 0 && movei <= n && movej > 0 && movej <= n) {
					if (find(fav[map[i][j]].begin(), fav[map[i][j]].end(), map[movei][movej]) != fav[map[i][j]].end())
						count+=1;
				}
			}
			if (count == 1)
				answer += 1;
			else if (count == 2)
				answer += 10;
			else if (count == 3)
				answer += 100;
			else if (count == 4)
				answer += 1000;
		}
	}

	cout << answer << endl;
}