17779번 게리맨더링2

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

using namespace std;
int map[21][21];
int dist[6];
int ch[21][21];
int d1, d2, r, c, n;
int ans = -1;
void go(int x,int y, int r, int c) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ch[i][j] = 5;

		}
	}
	//이제 1번
	int sub = 0;
	for (int i = 1; i < x+r; i++) {
		if (i >= x) sub++;
		for (int j = 1; j <= y-sub; j++) {
			ch[i][j] = 1;
		}
	}
	int plus = 0;
	for (int i = 1; i <= x + c; i++) {
		if (i > x) plus++;
		for (int j = y + 1+plus; j <= n; j++) {
			ch[i][j] = 2;
		}
	}
	sub = 0;
	for (int i = n; i >= x+r; i--) {
		if (i < x+r+c) sub++;
		for (int j = 1; j < y-r+c-sub;j++) {
			ch[i][j] = 3;
		}
	}
	plus = 0;
	for (int i = n; i > x+c; i--) {
		if (i <= x+r+c) plus++;
		for (int j = y-r+c+plus; j <= n; j++) {
			ch[i][j] = 4;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[ch[i][j]] += map[i][j];
		}
	}
	int sum = -1;
	int maxi = -1;
	int mini = 214700000;
	for (int i = 1; i <= 5; i++) {
		if (maxi < dist[i]) maxi = dist[i];
		if (mini > dist[i]) mini = dist[i];
	}
	sum = maxi - mini;
	if (ans==-1|| ans > sum) ans = sum;
}
int main() {
//	freopen("in1.txt", "rt", stdin);
	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; i++) {
		for (int j = 1; j <= n; j++) {
			for (int r = 1; r <= n; r++) {
				for (int c = 1; c <= n; c++) {
					if (i+r+c>n||r+1>j||j+c>n) continue;
					for (int k = 1; k <= n; k++) {
						for (int k2 = 1; k2 <= n; k2++) {
							dist[k] = 0;
							ch[k][k2] = 0;
						}
					}
					go(i, j, r, c);
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}