게리맨더링2/ 구현

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<deque>
#include<math.h>
#include<cmath>
using namespace std;

int arr[22][22];
int check[22][22];
int n;
int finalmin = 1e9 + 1;

void print() {
	
	for (int i = 1; i <= n; i++) {
		
		for (int j = 1; j <= n; j++) {
		
			cout << check[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool cango(int x, int y)
{
	return x >= 1 && y >= 1 && x <= n && y <= n;
}

int checkOne(int x, int y, int d1, int d2) {
	int total = 0;
	for (int i = 1; i < x + d1; i++) {
		for (int j = 1; j <= y; j++) {

			if (check[i][j] == 0) {
				total += arr[i][j];
				check[i][j] = 1;
			}
		}
	}
	return total;
}

int checkTwo(int x, int y, int d1, int d2) {
	int total = 0;
	for (int i = 1; i <= x + d2; i++) {
		for (int j = y+1; j <= n; j++) {
			
			if (check[i][j] == 0) {
				total += arr[i][j];
				check[i][j] = 2;
			}
		}
	}
	return total;
}

int checkThree(int x, int y, int d1, int d2) {
	int total = 0;
	for (int i = x+d1; i <=n; i++) {
		for (int j = 1; j < y-d1+d2; j++) {
	
			if (check[i][j] == 0) {
				total += arr[i][j];
				check[i][j] = 3;
			}
		}
	}
	return total;
}

int checkFour(int x, int y, int d1, int d2) {
	int total = 0;
	for (int i = x + d2+1; i <= n; i++) {
		for (int j = y-d1+d2; j <=n; j++) {
			
			if (check[i][j] == 0) {
				total += arr[i][j];
				check[i][j] = 4;
			}
		}
	}
	return total;
}

int checkFive(int x, int y, int d1, int d2) {

	//vector<vector<int>>v(n, vector<int>(n));
	map<int, set<int>>ms;
	int total = 0;

	for (int d = 0; d <= d1; d++) {

		int nx = x + d;
		int ny = y - d;

		if (check[nx][ny] == 0) {
			total += arr[nx][ny];
			check[nx][ny] = 5;
			ms[nx].insert(ny);
		}
		
		nx = x + d2 + d;
		ny = y + d2 - d;

		if (check[nx][ny] == 0) {
			total += arr[nx][ny];
			check[nx][ny] = 5;
			ms[nx].insert(ny);
		}
	}

	for (int d = 0; d <= d2; d++) {
		
		int nx = x + d;
		int ny = y + d;

		if (check[nx][ny] == 0) {
			total += arr[nx][ny];
			check[nx][ny] = 5;
			ms[nx].insert(ny);
		}
		
		nx = x + d1 + d;
		ny = y - d1 + d;

		if (check[nx][ny] == 0) {
			total += arr[nx][ny];
			check[nx][ny] = 5;
			ms[nx].insert(ny);
		}
	}

	map<int, set<int>>::iterator it;
	set<int>::iterator sit;
	for (it = ms.begin(); it != ms.end(); it++) {
		sit = it->second.begin();
		int s = *sit;
		

		sit = it->second.end();
		--sit;
	
		int e = *sit;

	
		for (int t = s + 1; t < e; t++) {
			
			total += arr[it->first][t];
			check[it->first][t]=5;
		
		}
	}
	
	return total;

}

void checkZone(int x, int y, int d1, int d2) {

	memset(check, 0, sizeof(check));

	int minnum = 1e9 + 1;
	int maxnum = 0;
	
	int total = checkFive(x, y, d1, d2);
	if (total == 0) { return; }
	if (minnum > total) { minnum = total; }
	if (total > maxnum) { maxnum = total; }
	
	total = checkOne(x, y, d1, d2);
	if (total == 0) { return; }
	if (minnum > total) { minnum = total; }
	if (total > maxnum) { maxnum = total; }
	
	total = checkTwo(x, y, d1, d2);
	if (total == 0) { return; }
	if (minnum > total) { minnum = total; }
	if (total > maxnum) { maxnum = total; }
	
	total = checkThree(x, y, d1, d2);
	if (total == 0) { return; }
	if (minnum > total) { minnum = total; }
	if (total > maxnum) { maxnum = total; }
	
	total = checkFour(x, y, d1, d2);
	if (total == 0) { return; }
	if (minnum > total) { minnum = total; }
	if (total > maxnum) { maxnum = total; }
	
//	cout << maxnum << endl;
//	cout << minnum << endl;
//	print();

	if (finalmin > (maxnum - minnum)) {
	
		finalmin = maxnum - minnum;
	}


}

bool checkCorrectValue(int x, int y, int d1, int d2) {
	
	return d1 >= 1 && d2 >= 1 && x >= 1 && x < (x + d1 + d2) && (x + d1 + d2) <= n && 1 <= (y - d1) && (y - d1) < y && y < (y + d2) && (y + d2) <= n;

}

int main() {


	cin >> n;

	memset(arr, 0, sizeof(arr));
	memset(check, 0, sizeof(check));

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

		
		}
	}

	for (int d1 = 1; d1 < n; d1++) {
	
		for (int d2 = 1; d2 < n; d2++) {
			
			for (int x = 1; x <= n; x++) {
				
				for (int y = 1; y <= n; y++) {
				
					if (checkCorrectValue(x, y, d1, d2)) {
						checkZone(x, y, d1, d2);
					}
					else { continue; }
					

				}
			}
		}
	}

	cout << finalmin << endl;




}