Submission #53424548

---

Source Code Expand

from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from atcoder.segtree import SegTree
from atcoder.lazysegtree import LazySegTree
from atcoder.dsu import DSU
from itertools import permutations, combinations
from heapq import heappop, heappush
import math, sys
_int = lambda x: int(x)-1
MOD = 998244353
INF = 1<<62
Yes, No = "Yes", "No"

N = int(input())
C = [input() for _ in range(N)]

d = dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def calc(s, g, ok):
    q = [(0, s[0], s[1])]
    memo = [[-1]*N for _ in range(N)]
    while q:
        cost, i, j = heappop(q)
        if memo[i][j] != -1: continue
        memo[i][j] = cost
        for d in dir:
            ni, nj = i+d[0], j+d[1]
            if 0 <= ni < N and 0 <= nj < N and memo[ni][nj] == -1:
                c = cost
                if C[ni][nj] != ok: c += 1
                heappush(q, (c, ni, nj))
    return memo[g[0]][g[1]]

r = calc((0, 0), (N-1, N-1), "R")
b = calc((N-1, 0), (0, N-1), "B")
ans = r+b
print(ans)

Submission Info

Judge Result