Submission #70803624

---

Source Code Expand

import sys
from collections import deque

input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    inf = 10**18
    dist = [[[inf] * 4 for _ in range(W)] for _ in range(H)]
    
    q = deque()    
    dr = [0, 1, 0, -1]#0:右, 1:下, 2:左, 3:上
    dc = [1, 0, -1, 0]
    mirror_map = {'A': 0, 'B': 1, 'C': 2}


    transform = [
        [0, 1, 2, 3], 
        [1, 0, 3, 2],  
        [3, 2, 1, 0]  
    ]
    
    dir_enter = 0 
    i, j = 0, 0
    
    S_act = mirror_map[S[i][j]]
    for type_int in range(3):
        cost = 0 if type_int == S_act else 1
        dir_next = transform[type_int][dir_enter]
        
        if cost < dist[i][j][dir_next]:
            dist[i][j][dir_next] = cost
            if cost == 0:
                q.appendleft((i, j, dir_next))
            else:
                q.append((i, j, dir_next))

    while q:
        i, j, dir_next = q.popleft()
        cost = dist[i][j][dir_next]
        
        next_i = i + dr[dir_next]
        next_j = j + dc[dir_next]
        dir_enter = dir_next

        if not (0 <= next_i < H and 0 <= next_j < W):
            continue
            
        S_act = mirror_map[S[next_i][next_j]]
        for type_int in range(3):
            op_cost = 0 if type_int == S_act else 1
            new_total_cost = cost + op_cost
            
            dir_next_new = transform[type_int][dir_enter]
            
            if new_total_cost < dist[next_i][next_j][dir_next_new]:
                dist[next_i][next_j][dir_next_new] = new_total_cost
                if op_cost == 0:
                    q.appendleft((next_i, next_j, dir_next_new))
                else:
                    q.append((next_i, next_j, dir_next_new))


    ans = dist[H-1][W-1][0] 
    return ans if ans != inf else -1

T = int(input())
ans = []
for _ in range(T):
    ans.append(solve())

for _ in range(T):
    print(ans[_])

Submission Info

Judge Result