게리멘더링 2

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int map[21][21];
int sum;
int answer = 2147000000;

int solve(int x, int y, int d1, int d2) {
	int temp[21][21] = { 0, };
	//5번 선거구
	for (int i = 0; i <= d1; i++) temp[x + i][y - i] = 5;
	for (int i = 0; i <= d1; i++) temp[x + d2 + i][y + d2 - i]=5;
	for (int i = 0; i <= d2; i++) temp[x + i][y + i]=5;
	for (int i = 0; i <= d2; i++) temp[x + d1 + i][y - d1 + i]=5;

	//1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
	int a1 = 0;
	for (int r = 1; r < x + d1; r++) {
		for (int c = 1; c <= y; c++) {
			if (temp[r][c] == 5) break;
			a1 += map[r][c];
		}
	}
	//2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
	int a2 = 0;
	for (int r = 1; r <= x + d2; r++) {
		for (int c = n; c > y; c--) {
			if (temp[r][c] == 5) break;
			a2 += map[r][c];
		}
	}
	//3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
	int a3 = 0;
	for (int r = x + d1; r <= n; r++) {
		for (int c = 1; c < y - d1 + d2; c++) {
			if (temp[r][c] == 5) break;
			a3 += map[r][c];
		}
	}
	//4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
	int a4 = 0;
	for (int r = x + d2 + 1; r <= n; r++) {
		for (int c = n; c >= y - d1 + d2; c--) {
			if (temp[r][c] == 5) break;
			a4 += map[r][c];
		}
	}
	int a5 = sum - (a1 + a2 + a3 + a4);
	int max_val = max(a1, max(a2, max(a3, max(a4, a5))));
	int min_val = min(a1, min(a2, min(a3, min(a4, a5))));
	return max_val - min_val;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= n; y++) {
			cin >> map[x][y];
			sum += map[x][y];
		}
	}

	//d1,d2>=1, 1<=x<x+d1+d2<=n, 1<=y-d1<y<y+d2<=n
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= n; y++) {
			for (int d1 = 1; d1 <= n; d1++) {
				for (int d2 = 1; d2 <= n; d2++) {
					if (x + d1 + d2 > n) continue;
					if (y - d1 < 1) continue;
					if (y + d2 > n) continue;
					answer = min(answer, solve(x, y, d1, d2));
				}
			}
		}
	}
	cout << answer << "\n";
	return 0;
}