땅의 균형 분할

시간 제한1초메모리 제한1024 MB

요약

0, 1, 2 값이 적힌 r행 c열 격자를 연결된 두 조각으로 나눌 때, 각 조각 값의 곱 차이가 최소가 되는 값을 구합니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

늙은 왕이 자신의 땅을 두 조각으로 나누어 두 자손에게 주려고 합니다. 땅은 r행 c열의 격자이며, 각 칸에는 번영도를 나타내는 정수가 있습니다. 값은 0(황폐), 1(보통), 2(비옥) 중 하나입니다. 두 칸이 변을 공유하면 연결된 것으로 봅니다.

각 자손은 칸이 하나 이상인 연결된 땅을 한 조각씩 받습니다. 모든 칸은 두 자손 중 한 명에게 반드시 주어야 하며, 남는 칸은 없습니다. 땅의 번영도는 그 땅에 속한 모든 칸의 번영도 값을 곱한 값입니다. 왕은 두 땅의 번영도 차이의 절댓값을 가능한 한 작게 만들고 싶어 합니다. 그 최솟값을 출력하세요.

입력

첫 줄에 양의 정수 r과 c가 주어집니다. 단, $2 \le r \times c \le 64$ 입니다. 이어지는 r개의 줄에는 각각 c개의 정수가 주어지며, 땅의 번영도 값을 나타냅니다. 모든 정수는 0, 1, 2 중 하나입니다.

출력

두 자손이 받는 땅의 번영도 차이의 절댓값 중 최솟값을 출력하세요.

예제3

예제 1
입력
```
3 4
1 2 1 1
2 2 1 2
1 2 2 2
```
예상 출력
```
8
```
예제 2
입력
```
2 3
0 1 2
0 1 2
```
예상 출력
```
0
```
예제 3
입력
```
1 3
2 0 2
```
예상 출력
```
2
```