우아한 다이아몬드 (Small)
시간 제한5초메모리 제한512 MB
주어진 숫자 다이아몬드를 가로와 세로로 대칭인 더 큰 다이아몬드로 확장하고 추가 숫자를 최소화합니다.
문제
왕이 우아한 다이아몬드를 만들라고 당신을 고용했다. 우아한 다이아몬드는 숫자로 이루어진 2차원 도형이고, 가로축과 세로축 모두에 대해 대칭이다. 다음 네 도형은 모두 우아한 다이아몬드다.
2
3 3
4 1 4
3 3
2
8
8 8
8
3
2 2
3
7
다음 세 도형은 다이아몬드이지만 우아하지 않다.
2
1 1
1
1
1 2
1 1 1
2 1
1
3
1 1
3 1 3
1 1
2
다음 세 도형은 아예 다이아몬드가 아니다.
1
1 1
2
222
2
8 8
0
00000
왕은 다이아몬드를 하나 준다. 이 다이아몬드는 우아하지 않을 수도 있다. 당신이 할 일은 다이아몬드를 확장해서 우아하게 만드는 것이다. 확장은 숫자를 덧붙여 더 큰 다이아몬드로 만드는 작업이다. 돈을 많이 쓰고 싶지 않으니 비용을 최소로 해야 한다.
정의
크기가 인 다이아몬드는 0부터 9까지의 숫자를 공백 한 칸으로 구분해 적은 개의 줄이며, 배치 규칙은 다음과 같다.
- 인 줄 는 공백 개를 적고, 그 뒤에 숫자 개를 공백 한 칸으로 구분해 적는다.
- 인 줄 는 공백 개를 적고, 그 뒤에 숫자 개를 공백 한 칸으로 구분해 적는다.
크기가 인 우아한 다이아몬드는 크기가 인 다이아몬드 가운데 다음 두 대칭 조건을 모두 만족하는 것이다. 줄 에 있는 숫자의 개수를 라고 하자.
- 가로 대칭: 줄 의 번째 숫자(이 첫 숫자)는 같은 줄의 번째 숫자와 같다.
- 세로 대칭: 줄 의 번째 숫자(이 첫 줄)는 줄 의 번째 숫자와 같다.
크기가 인 다이아몬드에 숫자를 덧붙이는 작업을 확장이라고 한다. 확장한 결과는 다음 성질을 만족한다.
- 결과는 크기가 이상인 다이아몬드다.
- 원래 다이아몬드가 결과 안에 그대로 들어 있다. 즉 정수 와 가 존재해서, 원래 다이아몬드의 번째 줄 번째 문자가 공백이 아니라 숫자인 모든 와 에 대해 결과의 번째 줄 번째 문자도 숫자이고 값이 같다.
확장의 비용은 결과의 숫자 개수에서 원래 다이아몬드의 숫자 개수를 뺀 값이다.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 이어서 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 가 혼자 적힌 줄 하나와 크기가 인 다이아몬드로 이루어진다.
제한
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 는 주어진 다이아몬드를 우아한 다이아몬드로 확장하는 최소 비용이다. 이미 우아한 다이아몬드라면 는 0이다.
힌트
예제에는 테스트 케이스가 네 개 있다. 앞의 두 개는 각각 크기 1, 크기 2의 우아한 다이아몬드라서 확장할 필요가 없고 비용은 0이다. 세 번째는 다음 다이아몬드로 확장할 수 있다.
3
1 1
1 2 1
1 1
3
확장 방법은 여러 가지이지만 이 방법의 비용 5가 가장 작다. 네 번째는 다음 다이아몬드로 확장할 수 있다.
9
1 1
6 3 6
9 5 5 9
6 3 6
1 1
9
이때 비용은 7이다.