[백준 17779] 게리맨더링2

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

17779번: 게리맨더링 2

요구 사항

1. 구역 나누기

 - 문제에 주어진 범위대로 구역을 나누어 준다

2. 합 구하기

 - 범위마다 합을 구한다

3. 구역의 최소값 구하기

 - 범위의 최대-최소의 차이가 최소가 되는 값을 구한다

 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int map[101][101];
int visit[101][101];
int dr[4] = { 1,1,-1,-1 };
int dc[4] = { -1,1,1,-1 };
int ans = 9876543211;
bool check(int x, int y, int d1, int d2)
{
	if ( x + d1 + d2 > n || y - d1 < 1 || y + d2 > n)
		return true;
	return false;
}
void cal(int x, int y, int d1, int d2)
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			visit[i][j] = 0;
	
	//1 0번 방향
	int nx = x;
	int ny = y;
	visit[nx][ny] = 5;
	for (int i = 1; i <= d1; i++)
	{
		int nnx = nx + dr[0];
		int nny = ny + dc[0];
		nx = nnx;
		ny = nny;
		visit[nx][ny] = 5;
	}
	nx = x;
	ny = y;
	for (int i = 1; i <= d2; i++)
	{
		visit[nx][ny] = 5;
		int nnx = nx + dr[1];
		int nny = ny + dc[1];
		nx = nnx;
		ny = nny;
		visit[nx][ny] = 5;
	}

	nx = x + d1;
	ny = y - d1;
	for (int i = 1; i <= d2; i++)
	{
		
		int nnx = nx + dr[1];
		int nny = ny + dc[1];
		nx = nnx;
		ny = nny;
		visit[nx][ny] = 5;
	}

	nx = x + d2;
	ny = y + d2;
	for (int i = 1; i <= d1; i++)
	{
		
		int nnx = nx + dr[0];
		int nny = ny + dc[0];
		nx = nnx;
		ny = nny;
		visit[nx][ny] = 5;
	}
	
	for (int i = 1; i < x+d1; i++)
	{
		for (int j = 1; j <= y; j++)
		{
			if (visit[i][j] == 5)
				break;
			if (visit[i][j] == 0)
				visit[i][j] = 1;
			else
				continue;
		}
	}

	for (int i = 1; i <= x + d2; i++)
	{
		for (int j = n; j >= y+1; j--)
		{
			if (visit[i][j] == 5)
				break;
			visit[i][j] = 2;
		}
	}
	
	for (int i = x + d1; i <= n; i++)
	{
		for (int j = 1; j < y - d1 + d2; j++)
		{
			if (visit[i][j] == 5)
				break;
			if (visit[i][j] == 0)
				visit[i][j] = 3;
			else
				continue;
		}
	}
	//x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
	for (int i = x + d2+1; i <= n; i++)
	{
		for (int j = n; j >= y - d1 + d2; j--)
		{
			if (visit[i][j] == 5)
				break;
			visit[i][j] = 4;
		}
	}
	
	int suma[6] = { 0,0,0,0,0,0 };

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (visit[i][j] == 0)
				suma[5] += map[i][j];
			else
				suma[visit[i][j]] += map[i][j];
		}
	}
	int maxvalue = 0;
	int minvalue = 987654321;

	for (int i = 1; i <= 5; i++)
	{
		//cout << suma[i] << " ";
		maxvalue = max(maxvalue, suma[i]);
		minvalue = min(minvalue, suma[i]);
	}
	//cout << endl;

	int tans = maxvalue - minvalue;
	if (ans > tans)
	{
		ans = tans;
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
		}
	}
	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 (check(x, y, d1, d2))
						continue;
					else
						cal(x, y, d1, d2);
				}
			}
		}
	}
	cout << ans << endl;
}