21609 상어 중학교

import sys
input = sys.stdin.readline
from collections import deque

n , m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [1 , 0 , -1 , 0]
dy = [0 , 1 , 0 , -1]
point = 0

# 중력 작용
def gravity(board):

    for j in range(n): # x 축이 0 ~ n-1 까지 진행
        for i in range(n - 2 , -1 , -1): # 맨 아래 블럭은 있던없던 진행 안해도됨 , 위에 블럭부터 진행

            if board[i][j] >= 0 and board[i + 1][j] == -2:
                # 만약 현재 위치에 블럭이 있고, 아래쪽이 빈 경우
                dropped = 0

                for k in range(i + 1 , n):
                # 아래부터 바닥까지 탐색
                    if board[k][j] >= -1:
                        # 블럭을 만나면
                        board[k - 1][j] = board[i][j]
                        # 해당 위치에 현재 블럭을 놓고 원래 위치는 빈칸 처리
                        board[i][j] = -2
                        dropped = 1
                        break
                # 이 경우는 아래에서 블럭을 안만남, 다 비어있는 경우 
                if not dropped:
                    board[n - 1][j] = board[i][j]
                    board[i][j] = -2
                    # 맨 아래로 내린다

    return board

# 반시계 방향 회전
def rotate_reverseClockwise(board):

    rotated_board = [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            rotated_board[n - 1 - j][i] = board[i][j]
    
    return rotated_board

# 시뮬레이션 진행
def simulate(board):

    groups = []
    # 1 부터 m + 1 까지 탐색
    for num in range(1 , m + 1):

        queue = deque()
        visited = [[False] * n for _ in range(n)]

        for i in range(n):
            for j in range(n):
                
                if not visited[i][j] and board[i][j] == num:
                    # totalBlock , rainbowBlock 을 설정
                    totalBlock , rainbowBlock = 1 , 0
                    visited[i][j] = True

                    queue.append([i , j , num])
                    # bfs 로 돌면서 인접한 rainbowBlock 과 totalBlock 을 센다
                    while queue:
                        
                        [y , x , num] = queue.popleft()

                        for k in range(4):

                            ny = y + dy[k]
                            nx = x + dx[k]

                            if ny < 0 or nx < 0 or ny > n - 1 or nx > n - 1:
                                continue
                            
                            # 만약 방문하지 않은 블럭이 해당 숫자인 경우
                            if not visited[ny][nx] and board[ny][nx] == num:
                                totalBlock += 1
                                visited[ny][nx] = True
                                queue.append([ny , nx , num])
                            # 방문하지 않은 블럭이 무지개 블럭인 경우
                            elif not visited[ny][nx] and board[ny][nx] == 0:
                                totalBlock += 1
                                rainbowBlock += 1
                                visited[ny][nx] = True
                                queue.append([ny , nx , num])

                    # 총 블럭수가 2개 이상일때 append
                    if totalBlock >= 2:
                        groups.append([totalBlock , rainbowBlock , i , j , num])

    groups = sorted(groups , key = lambda x : (-x[0] , -x[1] , -x[2] , -x[3]))           
    return groups
    # 결과를 리턴한다.
while True:

    # 먼저 시뮬레이션을 한번 함
    groups = simulate(board)

    if groups: # 존재하는 그룹이 있는 경우
        
        cy , cx , num = groups[0][2] , groups[0][3] , groups[0][4]
        point += (groups[0][0] ** 2)
        # 조건에 해당하는 블럭을 선택
        delete_visited = [[False] * n for _ in range(n)]
        delete_visited[cy][cx] = True
        board[cy][cx] = -2
        # 삭제된 블럭은 -2 로 표시한다
        queue = deque()
        queue.append([cy , cx , num])
        # bfs 로 돌면서
        while queue:

            y , x , num = queue.popleft()

            for i in range(4):

                ny = y + dy[i]
                nx = x + dx[i]

                if ny < 0 or nx < 0 or ny > n - 1 or nx > n - 1:
                    continue
                # 삭제 블럭 -2 로 표시
                if not delete_visited[ny][nx] and (board[ny][nx] == num or board[ny][nx] == 0):
                    board[ny][nx] = -2
                    delete_visited[ny][nx] = True
                    queue.append([ny , nx , num])

        # 중력 , 회전 진행
        board = gravity(board)
        board = rotate_reverseClockwise(board)
        board = gravity(board)
    
    else:
        break

print(point)