석유 회사
면접 대비시간 제한8초메모리 제한512 MB
변을 공유하는 칸에 발전소를 동시에 두지 않는다는 조건에서 채굴할 수 있는 석유량의 최댓값을 구한다.
문제
Irving & Cohen 석유 회사가 한 지역에 새 유전을 개발하기로 했다. 사전 조사를 마치고 매장량을 표시한 격자 지도를 만들었다.
회사는 이 지도를 보고 여러 격자 칸에 채굴 시설을 세울 계획인데, 화재가 났을 때 불이 번지는 것을 막기 위해 서로 인접한 두 칸에는 시설을 놓지 않기로 했다. 두 칸은 변을 공유하면 인접한 것으로 본다. 당신은 이 회사에서 일하는 프로그래머이며, 매장량 지도가 주어졌을 때 캘 수 있는 석유의 최대량을 계산하는 프로그램을 작성해야 한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 다음과 같은 형식으로 주어진다.
W H
r1,1 r2,1 . . . rW,1
...
r1,H r2,H . . . rW,H
테스트 케이스의 첫 줄에는 두 정수 W와 H (1 ≤ W, H ≤ 20)가 주어진다. 이는 영역의 크기를 나타낸다. 다음 H개 줄에는 각각 W개의 정수가 주어지며 영역의 지도를 나타낸다. 각 정수 r**x,y (0 ≤ r**x,y < 10000)는 격자 칸 (x, y)의 석유 매장량을 나타낸다.
출력
각 테스트 케이스마다 케이스 번호(1부터 시작)와 캘 수 있는 석유의 최대량을 한 줄에 출력한다. 형식은 샘플 출력 부분을 참고한다.