[코드트리] 최적의 십자 모양 폭발 Python

# n 입력
n = int(input())
# grid 입력
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# pairs_num_of(bombed_grid)
def pairs_num_of(bombed_grid):
    # pair_cnt
    pair_cnt = 0

    # 완전 탐색
    for i in range(n):
        for j in range(n):
            # 숫자가 있다면,
            if bombed_grid[i][j]:
                dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
                for dx, dy in zip(dxs, dys):
                    nx, ny = i + dx, j + dy
                    # 범위 내에 있고, 짝이 있으면
                    if in_range(nx, ny) and bombed_grid[i][j] == bombed_grid[nx][ny]:
                        # pair_cnt 올려주기
                        pair_cnt += 1
    
    # 반환 -> 한 쌍이 중복되어 카운트되므로 2로 나눈 값을 반환
    return pair_cnt // 2

# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# get_pairs_num(x, y)
def get_pairs_num(x, y):
    
    # temp_grid -> grid 복제
    temp_grid = [
        [0] * n
        for _ in range(n)
    ]
    for i in range(n):
        for j in range(n):
            temp_grid[i][j] = grid[i][j]
    
    # 터뜨려주기
    # bomb_pow
    bomb_pow = temp_grid[x][y]
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        for i in range(bomb_pow):
            nx, ny = x + dx * i, y + dy * i
            # 범위 내에 있으면
            if in_range(nx, ny):
                # 터뜨려주기
                temp_grid[nx][ny] = 0
    
    # 밀어주기
    # 모든 행에 대하여
    for c in range(n):
        # temp_col
        temp_col = []
        
        # 각 행에서
        for r in range(n-1, -1, -1):
            # 숫자가 있다면
            if temp_grid[r][c]:
                # temp_col에 추가
                temp_col.append(temp_grid[r][c])
        
        # shortage
        shortage = n - len(temp_col)
        for _ in range(shortage):
            temp_col.append(0)
        
        # 바꿔주기
        for r in range(n):
            temp_grid[r][c] = temp_col[n - r - 1]

    # 반환
    return pairs_num_of(temp_grid)
        
# 설계
# max_pairs
max_pairs = 0

# 완전 탐색
for i in range(n):
    for j in range(n):
        # max_pairs update
        max_pairs = max(max_pairs, get_pairs_num(i, j))

# 출력
print(max_pairs)