18575. 풍선팡 보너스 게임

틈틈이 풍선게임을 하던 김싸피는 새로운 보너스 스테이지에 도달했다. 보너스 스테이지의 규칙은 다음과 같다.

숫자가 써진 풍선이 NxN 격자의 각 칸에 고정되어 있다.

어떤 풍선을 터트리면 같은 행과 열의 풍선이 모두 터진다.

같은 풍선 배치가 두 번 주어지며, 각각 풍선을 하나씩 터트려 얻는 점수의 차이가 보너스 스테이지의 점수가 된다.

 

예를 들어, <그림 1>과 같은 스테이지에서, <그림 2>처럼 2가 써진 풍선을 터트리면 같은 행과 열의 풍선이 모두 터지고, 이때 터진 풍선에 있던 숫자의 합은 8이다. 다시 같은 배치에서 <그림 3>처럼 1인 풍선을 골라 터트리면, 같은 행과 열의 풍선이 터졌을 때의 합은 7이 되고, 이 스테이지의 점수는 8-7=1인 1점이 된다.

                                    <그림 1>                                      <그림 2>                                            <그림 3>

 

두 풍선을 잘 골라 터트리면 최대 점수를 얻을 수 있다. 보너스 스테이지가 주어지면 얻을 수 있는 최대 점수를 출력하라.

 

[입력]

첫 줄에 스테이지의 개수 T가 주어진다. 다음 줄부터 각 스테이지 별로, 첫 줄에 격자의 크기 N, 다음 줄부터 N개씩의 숫자가 N줄에 걸쳐 주어진다.

( 4 <= N <= 20, 1 <= Ai j<= min(N, 9))

 

[출력]

각 스테이지 별로 한 줄에 #과 스테이지 번호, 빈칸과 최대 점수를 출력한다.

입력

 

3
4
1 1 1 1
1 2 1 1
1 1 1 1
1 1 1 1
5
3 3 2 2 3
2 4 5 2 3
4 2 1 2 4
1 3 5 3 3
1 4 5 2 3
5
1 3 5 2 3
2 2 5 5 5
3 4 2 1 1
1 5 2 5 4
5 2 3 4 1
 

출력

 

#1 1
#2 10
#3 13

di = [1,-1,0,0]  # 델타값 설정하기(하,상,우,좌 순으로 탐색)
dj = [0,0,1,-1]
 
T = int(input())
for tc in range(1,T+1):
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    max_score = 0
    min_score = 10000
 
    for i in range(N):  # N*N 크기의 격자
        for j in range(N):
            sum_score = arr[i][j]  # 자기자신 포함이므로 자기자신이 초기값
            for k in range(1, N):
                for h in range(4):  # 하상우좌 4방향 탐색
                    ni, nj = i+di[h]*k, j+dj[h]*k
                    if 0 <= ni < N and 0 <= nj < N:  # 유효한 인덱스 범위내에서
                        sum_score += arr[ni][nj]  # 그 값을 모두 더한다
            if max_score < sum_score:  # 최댓값 갱신
                max_score = sum_score
 
            # 위와 동일한 방식으로 최솟값 구하기
            sum_score = arr[i][j]
            for k in range(1, N):
                for h in range(4):
                    ni, nj = i+di[h]*k, j+dj[h]*k
                    if 0 <= ni < N and 0 <= nj < N:
                        sum_score += arr[ni][nj]
            if min_score > sum_score:  # 최솟값 갱신
                min_score = sum_score
 
    print(f'#{tc} {max_score-min_score}')  # 얻을 수 있는 (최댓값-최솟값)이 보너스 점수의 최댓값이므로