격자 0 만들기

시간 제한7초메모리 제한256 MB

요약

가로 또는 세로로 인접한 두 칸을 함께 1씩 감소시켜 격자의 모든 수를 0으로 만드는 최소 횟수를 구합니다.

난이도: 어려움10점 중 8점
유형: 그래프
정답자: 아직 제출이 없습니다

문제

음수가 아닌 정수로 채워진 격자가 주어진다. 이 격자에 다음 연산을 원하는 횟수만큼 행할 수 있다.

격자에서 가로 또는 세로로 인접한 칸 2개를 고른다.
고른 칸 각각에 대해, 그 값이 양수이면 1 감소시킨다.

값이 이미 0인 칸을 골라도 되며, 그 칸은 0으로 남는다.

다음 그림은 2×2 격자에 연산을 네 번 이어서 행해 모든 수를 0으로 만든 과정이다. 노란색으로 칠한 두 칸이 그 단계에서 고른 칸이다.

이 예에서는 네 번의 연산으로 모든 수를 0으로 만들었고, 이보다 적은 횟수로는 만들 수 없다.

격자가 주어졌을 때 모든 수를 0으로 만드는 데 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스의 첫째 줄에는 격자의 행 개수 $n$ 과 열 개수 $m$ 이 주어진다 ( $2 \le n, m \le 50$ ). 이어지는 $n$ 개의 줄에는 격자의 해당 행에 있는 정수 $m$ 개가 열 순서대로 주어진다. 각 정수는 $0$ 이상 $1{,}000$ 이하이다.

출력

각 테스트 케이스마다 필요한 연산의 최소 횟수를 한 줄에 출력한다.

예제7

예제 1
입력
```
2
2 2
1 3
1 2
2 4
2 3 2 3
1 2 1 1
```
예상 출력
```
4
8
```
예제 2
입력
```
1
2 2
0 0
0 0
```
예상 출력
```
0
```
예제 3
입력
```
1
2 2
5 0
0 0
```
예상 출력
```
5
```
예제 4
입력
```
1
2 2
7 7
0 0
```
예상 출력
```
7
```
예제 5
입력
```
1
2 2
4 0
0 4
```
예상 출력
```
8
```
예제 6
입력
```
1
2 2
1000 1000
1000 1000
```
예상 출력
```
2000
```
예제 7
입력
```
1
3 3
1 2 3
4 5 6
7 8 9
```
예상 출력
```
25
```