BFS, 시뮬레이션 - 마법의 숲 탐색

from collections import deque


R, C, K = map(int, input().split())



maps = [[0] * (C) for _ in range(R + 3)] # 골렘 시작위치를 처리하기 위해 3행 추가

def check_map(d, r, c):

    if d == 1: # 동쪽
        if 0 <= r - 1 and r + 1 < 3 + R and c + 2 < C and maps[r - 1][c + 1] == 0 and maps[r][c + 2] == 0 and maps[r + 1][c + 1] == 0:
            return True, r, c + 1
        return False, -1, -1
    elif d == 2: # 남쪽
        if 0 <= c - 1 and r + 2 < 3 + R and c + 1 < C and maps[r + 1][c + 1] == 0 and maps[r + 2][c] == 0 and maps[r + 1][c - 1] == 0:
            return True, r + 1, c
        return False, -1, -1
    elif d == 3: # 서쪽
        if 0 <= r - 1 and r + 1 < 3 + R and 0 <= c - 2 and maps[r - 1][c - 1] == 0 and maps[r][c - 2] == 0 and maps[r + 1][c - 1] == 0:
            return True, r, c - 1
        return False, -1, -1


def exit_clock(d):
    if d == 3:
        return 0
    return d + 1

def exit_anti_clock(d):
    if d == 0:
        return 3
    return d - 1

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def draw_golem(di, i, r, c):

    # 골렘 중앙 표시
    maps[r][c] = i

    # 출구 표시
    nr, nc = r + dx[di], c + dy[di]
    maps[nr][nc] = -i

    # 골렘 몸 표시
    for j in range(4):
        if j == di:
            continue
        nr, nc = r + dx[j], c + dy[j]
        maps[nr][nc] = i
    

def move_fairy(x, y):

    num = maps[x][y]
    
    q = deque()
    visited = set()
    visited.add((x, y))
    q.append((x, y, num))
    
    max_row = -1

    while q:
    	# num: 현재 머무르고 있는 골렘의 번호
        r, c, num = q.popleft()
        # 최대 행 갱신
        max_row = max(r, max_row)

        for i in range(4):
            nr, nc = r + dx[i], c + dy[i]

            if 3 <= nr < 3 + R and 0 <= nc < C and (nr, nc) not in visited and maps[nr][nc] != 0:

                # 현재 위치가 탈출구라면
                if maps[r][c] < 0:
                    # 다른 골렘으로 이동
                    if maps[nr][nc] != num:
                        q.append((nr, nc, abs(maps[nr][nc])))
                        visited.add((nr, nc))
                # 현재 있는 골렘 내부라면                
                if abs(maps[nr][nc]) == num:
                    q.append((nr, nc, num))
                    visited.add((nr, nc))
    
    return max_row




total_row_sum = 0

for i in range(1, K + 1):
    ci, di = map(int, input().split())

    # ci 에서 1 빼서 인덱스 시작 0으로 맞춰줘야 함 주의
    ci -= 1

    # 1) 골렘 중앙을 (1, ci)로 시작
    r, c = 1, ci

    # 골렘 이동 시작
    while True:
        # 1) 남쪽 확인
        is_okay, nr, nc = check_map(2, r, c)
        if is_okay:
            r, c = nr, nc
        else:
            # 2) 서쪽 + 남쪽 확인
            is_okay, nr, nc = check_map(3, r, c)
            is_moved = False

            if is_okay:
                # 남쪽도 확인
                is_okay, nnr, nnc = check_map(2, nr, nc)

                if is_okay:
                    r, c = nnr, nnc
                    # 출구 반시계방향으로 회전
                    di = exit_anti_clock(di)
                    is_moved = True
            
            # 2번도 실패 시
            # 3) 동쪽 + 남쪽 확인
            if not is_moved:

                is_okay, nr, nc = check_map(1, r, c)
                is_moved = False

                if is_okay:
                    # 남쪽도 확인
                    is_okay, nnr, nnc = check_map(2, nr, nc)

                    if is_okay:
                        r, c = nnr, nnc
                        # 출구 시계방향으로 회전
                        di = exit_clock(di)
                        is_moved = True

                # 더 이상 이동불가 종료
                if not is_moved:
                    break

    # 골렘 중심 위치 체크 - 골렘 일부분이 숲 바깥에 위치한다면 전체 리셋 후 다음 턴으로
    if r <= 3:
        maps = [[0] * (C) for _ in range(R + 3)] # 골렘 시작위치를 처리하기 위해 3행 추가
        continue


    # 골렘 이동 종료 시 맵에 골렘 위치 표시 (+i: 골렘, -i: 골렘 탈출구)

    draw_golem(di, i, r, c)

    # 정령 이동 BFS

    max_r = move_fairy(r, c)
    
    # 맵에 3행 추가 + 인덱스 0으로 진행했으므로 -3 + 1 = -2 더해줘야 함!
    max_r -= 2

    total_row_sum += max_r


print(total_row_sum)