Submission #70458112

---

Source Code Expand

import sys
input = sys.stdin.readline
INF = 10**9

def mat_mul(A, B):
  C = [[INF]*3 for _ in range(3)]
  for i in range(3):
    ai = A[i]
    for k in range(3):
      C[i][k] = min(ai[0]+B[0][k], ai[1]+B[1][k], ai[2]+B[2][k])
  return C

# Precompute for all 6-bit patterns (3 rows × 2 cols)
pre = {}
for mask in range(1<<6):
  S = [['.']*2 for _ in range(3)]
  for r in range(3):
    for c in range(2):
      if mask >> (r*2+c) & 1:
        S[r][c] = '#'
  d = [[INF]*3 for _ in range(3)]
  for sr in range(3):
    if S[sr][0] == '#': continue
    dist = [[INF]*2 for _ in range(3)]
    dist[sr][0] = 0
    q = [(sr,0)]
    while q:
      r,c = q.pop()
      v = dist[r][c]
      for nr in (r-1,r+1):
        if 0<=nr<3 and S[nr][c]=='.' and dist[nr][c]>v+1:
          dist[nr][c]=v+1;q.append((nr,c))
      nc = c^1
      if S[r][nc]=='.' and dist[r][nc]>v+1:
        dist[r][nc]=v+1;q.append((r,nc))
    for tr in range(3):
      d[sr][tr]=dist[tr][1]
  pre[mask]=d

class SegTree:
  def __init__(self, mats):
    n=1
    while n<len(mats): n<<=1
    self.n=n
    self.dat=[[[INF]*3 for _ in range(3)] for _ in range(2*n)]
    I=[[0 if i==j else INF for j in range(3)] for i in range(3)]
    for i in range(n):
      self.dat[n+i]=mats[i] if i<len(mats) else I
    for i in range(n-1,0,-1):
      self.dat[i]=mat_mul(self.dat[i<<1],self.dat[i<<1|1])
  def update(self,i,mat):
    i+=self.n
    self.dat[i]=mat
    i>>=1
    while i:
      self.dat[i]=mat_mul(self.dat[i<<1],self.dat[i<<1|1])
      i>>=1
  def all(self): return self.dat[1]

N=int(input())
S=[list(input().strip()) for _ in range(3)]
Q=int(input())

def get_mask(j):
  m=0
  for r in range(3):
    for c in range(2):
      if S[r][j+c]=='#': m|=1<<(r*2+c)
  return m

mats=[pre[get_mask(j)] for j in range(N-1)]
seg=SegTree(mats)

def ans():
  d=seg.all()[0][2]
  return -1 if d>=INF else d

out=[]
for _ in range(Q):
  r,c=map(int,input().split())
  r-=1;c-=1
  S[r][c]='.' if S[r][c]=='#' else '#'
  for j in [c-1,c]:
    if 0<=j<N-1:
      seg.update(j,pre[get_mask(j)])
  out.append(str(ans()))
print("\n".join(out))

Submission Info

Judge Result