게리멘더링 2 C++

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

17779번: 게리맨더링 2

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

using namespace std;
const int MAX = 25;
int map[MAX][MAX];
int n;
int answer = 987654321;
int divide[MAX][MAX];

void CheckMap(int x,int y, int d1, int d2) {
	vector<int> num(5,0);
	memset(divide, -1, sizeof(divide));

	//경계선
	// 2. 5번 선거구 경계선
	for (int i = 0; i <= d1; ++i)
	{
		divide[x + i][y - i] = 0;
		divide[x + d2 + i][y + d2 - i] = 0;
		num[0] += map[x + i][y - i] + map[x + d2 + i][y + d2 - i];
	}
	for (int i = 1; i < d2; ++i)
	{
		divide[x + i][y + i] = 0;
		divide[x + d1 + i][y - d1 + i] = 0;
		num[0] += map[x + i][y + i] + map[x + d1 + i][y - d1 + i];
	}

	// 3. 5번 선거구 내부 탐색
	for (int i = 0; i < d1; ++i)
	{
		int j = 0;
		while (divide[x + i + j + 1][y - i] != 0)
		{
			divide[x + i + j + 1][y - i] = 0;
			num[0] += map[x + i + j + 1][y - i];
			++j;
		}
	}
	for (int i = 1; i < d2; ++i)
	{
		int j = 0;
		while (divide[x + i + j + 1][y + i] != 0)
		{
			divide[x + i + j + 1][y + i] = true;
			num[0] += map[x + i + j + 1][y + i];
			++j;
		}
	}


	//1번 선거구
	for (int i = 1; i < x + d1; i++) {
		for (int j = 1; j <= y; j++) {
			if (divide[i][j] == -1)
				num[1] += map[i][j];
		}
	}

	//2번 선거구
	for (int i = 1; i <= x + d2; i++) {
		for (int j = y+1; j <= n; j++) {
			if (divide[i][j] == -1)
				num[2] += map[i][j];
		}
	}

	//3번 선거구
	for (int i = x+d1; i <= n; i++) {
		for (int j = 1; j < y-d1 + d2; j++) {
			if (divide[i][j] == -1)
				num[3] += map[i][j];
		}
	}

	//4번 선거구
	for (int i = x+d2+1; i <= n; i++) {
		for (int j = y-d1+d2; j <= n; j++) {
			if (divide[i][j] == -1)
				num[4] += map[i][j];
		}
	}

	sort(num.begin(), num.end());
	if (num[0] == 0)	return;
	int tmp = num[4] - num[0];
	if (tmp == 16)
		cout << 1 << endl;
	answer = min(answer, num[4] - num[0]);
}

int main(void) {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 1; i <= n-2; i++) {
		for (int j = 2; j <= n-1; j++) {
			for (int ii = 1; ii <= j - 1; ii++) {
				for (int jj = 1; jj <= n - j; jj++) {
					if (ii + jj <= n-i) {
						CheckMap(i, j, ii, jj);
					}
				}
			}
		}
	}

	cout << answer << endl;
}