문제:
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다
www.acmicpc.net
코드:
#include <iostream>
#include <string.h>
#include <algorithm>
#define f(i, n) for(int i = 0 ; i < (n); ++i)
#define IN(r, c) (0 <= (r) && (r) < N && 0 <= (c) && (c) < N)
using namespace std;
int N;
pair<int, int> src[5];
int map[20][20];
bool vst1[20][20], vst2[20][20];
int pop;
// dfs
int ctr[5];
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void dfs(int r, int c, int d) {
vst2[r][c] = 1;
//++ctr[d];
ctr[d] += map[r][c];
f(dd, 4) {
int nr = r + dr[dd], nc = c + dc[dd];
if (!IN(nr, nc) || vst2[nr][nc]) continue;
dfs(nr, nc, d);
}
}
// cmpt
pair<int, int> vtx[4];
void cmpt(int d) {
int r = vtx[d].first, c = vtx[d].second;
int rd, cd;
switch (d) {
case 0: cd = 1; break;
case 1: rd = 1; break;
case 2: cd = -1; break;
case 3: rd = -1; break;
}
switch (d) {
case 0: case 2:
for (c += cd; 0 <= c && c < N; c += cd) {
vst2[r][c] = 1;
//++ctr[d];
ctr[d] += map[r][c];
}
break;
case 1: case 3:
for (r += rd; 0 <= r && r < N; r += rd) {
vst2[r][c] = 1;
//++ctr[d];
ctr[d] += map[r][c];
}
break;
}
}
// plg
int rot[4];
int dif, ans = 40000;
int pr[] = { 1, 1, -1, -1 };
int pc[] = { 1, -1, -1, 1 };
void plg(int r, int c, int d) {
if (d == 2) {
memcpy(vst2, vst1, sizeof(bool) * 20 * 20);
for (; d < 4; ++d) {
for (; rot[d] < rot[d - 2]; ++rot[d]) {
r += pr[d], c += pc[d];
if (!IN(r, c)) goto init;
vst2[r][c] = 1;
}
vtx[d] = make_pair(r, c);
}
memset(ctr, 0, sizeof(int) * 5);
for (d = 0; d < 4; ++d)
cmpt(d);
for (d = 0; d < 4; ++d)
dfs(src[d].first, src[d].second, d);
ctr[4] = pop - ctr[3] - ctr[2] - ctr[1] - ctr[0];
dif = *max_element(ctr, ctr + 5) - *min_element(ctr, ctr + 5);
if (dif < ans)
ans = dif;
init:
rot[2] = 1, rot[3] = 0;
return;
}
int nr = r + pr[d], nc = c + pc[d];
if (IN(nr, nc)) {
vst1[nr][nc] = 1;
++rot[d];
plg(nr, nc, d);
--rot[d];
vst1[nr][nc] = 0;
}
if (rot[d]) {
int nd = d + 1;
int nr = r + pr[nd], nc = c + pc[nd];
if (IN(nr, nc)) {
vtx[d] = make_pair(r, c);
vst1[nr][nc] = 1;
++rot[nd];
plg(nr, nc, nd);
--rot[nd];
vst1[nr][nc] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
src[0] = { 0, N - 1 }; src[1] = { N - 1, N - 1 }; src[2] = { N - 1, 0 }; src[3] = { 0, 0 };
f(r, N) f(c, N) {
cin >> map[r][c];
pop += map[r][c];
}
f(r, N) f(c, N) plg(r, c, 0);
cout << ans;
return 0;
}