표적지에 산탄총으로 사격을 하려고 한다. 표적지는 크기가 N×N인 격자이다. 각 격자칸에는 점수가 있다. 격자칸의 점수는 음수일 수 있다. 또, 산탄총의 퍼지는 정도 K를 알고 있다. 사격했을 때 점수가 계산되는 방법은 다음과 같다. 사격한 위치의 중심인 칸에서는 그 칸의 점수의 K배를 받는다. 중심 칸에서 상하좌우로 인접한 4개의 칸에서는 칸들의 점수의 K-1배를 받는다. K-1배를 받는 칸에서 중심에서 먼 쪽으로 상하좌우로 인접한 칸들에서는 점수의 K-2배를 받는다. 이와 같이 진행하다가 0배를 받는 칸이 정해지면 더 이상 점수를 받지 않는다. 점수를 받는 모든 칸이 표적지 안일 필요는 없고, 사격의 중심이 표적지 밖일 수도 있다. 이런 경우 표적지 밖의 칸은 모두 0점의 점수를 가진 것으로 계산한다.
위 그림은 N=8인 경우이고, 왼쪽에서 4번째, 위에서 4번째의 칸을 중심으로 사격한 것을 보여준다. K=3이다. 가장 짙은 색으로 표시된 중심 칸에서는 3배의 점수를 받는다. 그 상하좌우의 중간 짙은 색의 칸들에서는 2배의 점수를 받는다. 가장 옅은 색의 칸들에서는 1배의 점수를 받는다. 흰색의 칸들에서는 점수를 받지 않는다.
표적지의 점수 배치를 입력 받아 가장 많은 총 점수를 받는 방법을 찾는 프로그램을 작성하라.
그림 1
제한시간: 전체 테스트 케이스는 50개 이하이며, 전체 수행 시간은 3초 이내. (Java 5초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.<br />
C에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다. ※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
메모리 사용 제한 : heap, global, static 총계 512MB, stack 100MB
제출 제한 : 최대 10회
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로 T 개의 테스트 케이스가 주어진다. (1 ≤ T ≤ 50)
각 테스트 케이스의 첫 줄에는 표적지의 크기 N과 퍼지는 정도 K가 주어진다. (1≤K≤N≤600).
둘째 줄부터 N개의 각 줄에는 N개의 수가 주어진다. 이 수들은 각 칸에 배정된 점수들이다. 점수의 절대값은 최대 이다.
점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 300 점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (47 점) : N≤50.
ㆍ 그룹 2 (107 점) : N≤200.
ㆍ 그룹 3 (146 점) : 추가적인 제한이 없음.
모든 그룹을 해결하지 않는 소스코드를 제출하는 경우에도 모든 입력 케이스에 대해 양식을 갖춘 출력을 생성해야 합니다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.