Problem:


Problem E: Mirror Cave

双子の冒険者 Rin と Len は鏡の洞窟でお宝を探している．この洞窟には鏡の間という対になった 2 つの部屋があり，その部屋の扉の向こうには高価な宝が眠っているという．

便宜上，2 つの部屋はそれぞれ W &times; H のセルが格子状に並んだものとみなす．部屋の外側は壁で囲まれている．また，部屋の内側にもところどころ壁が設置されており，壁の配置されているセルには進入することができない．宝の部屋への扉を開くためには，2 人が左右対称の動きをして，同時に特定のセルに到達しなければならない．しかも，片方だけが先に到達した場合は，扉はロックされて開かなくなってしまう．

左右対称の動きとは，北と北，西と東，東と西，南と南にそれぞれ同時に動くことを意味する．ただし，片方が動こうとしている先に壁があり，もう一方の先に壁が無いといった状況下でも左右対称の動きであると認められる．この場合は壁がある方はその場にとどまり，壁が無い方は隣のセルに動くことになる．

入力として，双子の初期位置，目的地，障害物の配置が与えられる．あなたの仕事は，この双子が扉を開けることが可能であるか判定するプログラムを書くことである．

Input

入力は複数のデータセットからなる．各データセットは次の形式で与えられる．

W H

RoomL1 RoomR1

RoomL2 RoomR2

...

RoomLH RoomRH

最初の行では 2 つの正の整数 W, H (1 ≤ W, H ≤ 50) が 1 つの空白で区切られて与えられる．その後，H 行に渡って 2 つの部屋の情報が与えられる．RoomLi，RoomRi はそれぞれ左側，右側の部屋の i 番目の行に対応する．両者とも長さ W の文字列で，j 番目の文字が部屋の j 番目の列に対応する．それぞれの文字は以下のいずれかである．

. : 自由に移動できるセル

# : 壁のあるセル（進入できない）

% : 目的地

R : Rin の初期位置

L : Len の初期位置

各部屋とも 1 行目が部屋の北端，1 列目が部屋の西端に対応する．また，各部屋は必ずちょうど 1 つの目的地があり，左側の部屋には Len，右側の部屋には Rin の初期位置がちょうど 1 つ存在する．

入力の終わりは，空白で区切られた 2 つの 0 を含む行で示される．

Output

各データセットについて，双子が扉を開くことができるなら Yes，できなければ No をそれぞれ 1 行に出力せよ．

Sample Input

5 5
%#... ...#%
.#.#. .#.#.
.#.#. .#.#.
.#.#. .#.#.
...#L R#...
3 2
.L. .R#
%.. .%.
4 1
L.%. %..R
0 0

Output for the Sample Input

Yes
Yes
No



Sample input:
5 5
%#... ...#%
.#.#. .#.#.
.#.#. .#.#.
.#.#. .#.#.
...#L R#...
3 2
.L. .R#
%.. .%.
4 1
L.%. %..R
0 0


Sample output:
Yes
Yes
No

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
while True:
    w,h=map(int,input().split(" "))
    def isrange(p):
        return 0<=p[0] and p[0]<h and 0<=p[1] and p[1]<w
    if w==0: break
    rl=[[str()] for i in range(h)]
    rr=[[str()] for i in range(h)]
    for i in range(h):
        rl[i],rr[i]=input().split(" ")
    q = deque()
    dp=np.ndarray((h,w,h,w))
    for i in range(h):
        for j in range(w):
            for ii in range(h):
                for jj in range(w):
                    dp[i][j][ii][jj]=True
    for i in range(h):
        for j in range(w):
            if rl[i][j]=="L": ls=(i,j)
            if rr[i][j]=="R": rs=(i,j)
            if rl[i][j]=="%": gl=(i,j)
            if rr[i][j]=="%": gr=(i,j)
    q.append((ls,rs))
    
    dp[ls[0]][ls[1]][rs[0]][rs[1]]=True
    dw=(-1,0,1,0)
    dh=(0,1,0,-1)
    cnt=0
    while q:
        if cnt>int(1e7): break
        cnt+=1
        val=q.pop()
        lp=val[0]
        rp=val[1]
        for i in range(4):
            lnp=(lp[0]+dh[i],lp[1]+dw[i])
            rnp=(rp[0]+dh[i],rp[1]-dw[i])
            if (not isrange(lnp)) or rl[lnp[0]][lnp[1]]=="#" : lnp=lp
            if (not isrange(rnp)) or rr[rnp[0]][rnp[1]]=="#" : rnp=rp
            if dp[lnp[0]][lnp[1]][rnp[0]][rnp[1]]: continue
            dp[lnp[0]][lnp[1]][rnp[0]][rnp[1]]=True
            q.append((lnp,rnp))
    if dp[gl[0]][gl[1]][gr[0]][gr[1]] : print("Yes")
    else : print("No")

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        w,h = LI()
        if w == 0:
            break
        la = ["#" * (w+2)]
        ra = ["#" * (w+2)]
        for _ in range(h):
            l,r = LS()
            la.append("#{}#".format(l))
            ra.append("#{}#".format(r))
        la.append("#" * (w+2))
        ra.append("#" * (w+2))
        ls = None
        rs = None
        for i in range(1,h+2):
            for j in range(1,w+2):
                if la[i][j] == 'L':
                    ls = (i,j)
                if ra[i][j] == 'R':
                    rs = (i,j)

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for di, dj in dd:
                    li = u[0][0] + di
                    lj = u[0][1] + dj
                    if la[li][lj] == "#":
                        li -= di
                        lj -= dj
                    ri = u[1][0] + di
                    rj = u[1][1] - dj
                    if ra[ri][rj] == "#":
                        ri -= di
                        rj += dj
                    if la[li][lj] == '%' and ra[ri][rj] == '%':
                        return True
                    if la[li][lj] == '%':
                        continue
                    if ra[ri][rj] == '%':
                        continue
                    uv = ((li,lj), (ri,rj))

                    if v[uv]:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return False

        if search((ls,rs)):
            rr.append('Yes')
        else:
            rr.append('No')


    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        w,h = LI()
        if w == 0:
            break
        print(w,h)
        la = ["#" * (w+2)]
        ra = ["#" * (w+2)]
        for _ in range(h):
            l,r = LS()
            la.append("#{}#".format(l))
            ra.append("#{}#".format(r))
        la.append("#" * (w+2))
        ra.append("#" * (w+2))
        ls = None
        rs = None
        lp = None
        rp = None
        for i in range(1,h+2):
            for j in range(1,w+2):
                if la[i][j] == 'L':
                    ls = (i,j)
                elif la[i][j] == '%':
                    lp = (i,j)
                if ra[i][j] == 'R':
                    rs = (i,j)
                elif ra[i][j] == '%':
                    rp = (i,j)
        lla = []
        rra = []
        for i in range(h+2):
            tl = []
            tr = []
            for j in range(w+2):
                if la[i][j] == '#':
                    tl.append(None)
                else:
                    tl.append(1)
                if ra[i][j] == '#':
                    tr.append(None)
                else:
                    tr.append(1)
            lla.append(tl)
            rra.append(tr)


        def search(s):
            q = []
            q.append(s)
            v = set()
            v.add(s)
            qi = 0
            while len(q) > qi:
                u = q[qi]
                qi += 1

                for di, dj in dd:
                    li = u[0][0]
                    lj = u[0][1]
                    if not lla[li+di][lj+dj] is None:
                        li += di
                        lj += dj
                    ri = u[1][0]
                    rj = u[1][1]
                    if not rra[ri+di][rj-dj] is None:
                        ri += di
                        rj -= dj

                    uv = ((li,lj), (ri,rj))
                    if uv in v:
                        continue
                    v.add(uv)
                    if (li,lj) == lp and (ri,rj) == rp:
                        # print(len(q))
                        return True
                    if (li,lj) == lp:
                        continue
                    if (ri,rj) == rp:
                        continue

                    q.append(uv)

            # print(len(q))
            return False

        if search((ls,rs)):
            rr.append('Yes')
        else:
            rr.append('No')
        # print(rr[-1])


    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        w,h = LI()
        if w == 0:
            break
        # print(w,h)
        W = w+2
        dd = [(0,-1),(W,0),(0,1),(-W,0)]
        la = ["#" * W]
        ra = ["#" * W]
        for _ in range(h):
            l,r = LS()
            la.append("#{}#".format(l))
            ra.append("#{}#".format(r))
        la.append("#" * W)
        ra.append("#" * W)
        ls = None
        rs = None
        lp = None
        rp = None
        for i in range(1,h+2):
            for j in range(1,w+2):
                if la[i][j] == 'L':
                    ls = i*W+j
                elif la[i][j] == '%':
                    lp = i*W+j
                if ra[i][j] == 'R':
                    rs = i*W+j
                elif ra[i][j] == '%':
                    rp = i*W+j
        lla = []
        rra = []
        for i in range(h+2):
            for j in range(w+2):
                if la[i][j] == '#':
                    lla.append(None)
                else:
                    lla.append(1)
                if ra[i][j] == '#':
                    rra.append(None)
                else:
                    rra.append(1)


        def search(s):
            q = []
            q.append(s)
            v = set()
            v.add(s)
            qi = 0
            while len(q) > qi:
                u = q[qi]
                qi += 1

                for di, dj in dd:
                    lij = u[0]
                    if not lla[lij+di+dj] is None:
                        lij += di + dj
                    rij = u[1]
                    if not rra[rij+di-dj] is None:
                        rij += di - dj

                    uv = (lij,rij)
                    if uv in v:
                        continue
                    v.add(uv)
                    if lij == lp and rij == rp:
                        # print(len(q))
                        return True
                    if lij == lp:
                        continue
                    if rij == rp:
                        continue

                    q.append(uv)

            # print(len(q))
            return False

        if search((ls,rs)):
            rr.append('Yes')
        else:
            rr.append('No')
        # print(rr[-1])


    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
from collections import deque

direct_l = ((-1, 0), (1, 0), (0, 1), (0, -1))
direct_r = ((1, 0), (-1, 0), (0, 1), (0, -1))
directs = tuple(zip(direct_l, direct_r))

def search(start_l, start_r, mp_l, mp_r):
  que = deque()
  que.append((start_l, start_r))
  dic = {}
  dic[(start_l, start_r)] = True
  while que:
    pl, pr = que.popleft()
    lx, ly = pl
    rx, ry = pr
    for ld, rd in directs:
      ldx, ldy = ld
      rdx, rdy = rd
      lnx, lny = (lx + ldx, ly + ldy) if mp_l[ly + ldy][lx + ldx] != "#" else (lx, ly)
      rnx, rny = (rx + rdx, ry + rdy) if mp_r[ry + rdy][rx + rdx] != "#" else (rx, ry)
      if not ((lnx, lny), (rnx, rny)) in dic:
        dic[((lnx, lny), (rnx, rny))] = True
        if mp_l[lny][lnx] == "%" and mp_r[rny][rnx] == "%":
          print("Yes")
          return
        if mp_l[lny][lnx] != "%" and mp_r[rny][rnx] != "%":
          que.append(((lnx, lny), (rnx, rny)))
  else:
    print("No")
    return


while True:
  w, h = map(int, input().split())
  if w == 0:
    break

  mp_l = ["#" * (w + 2)]
  mp_r = ["#" * (w + 2)]
  for _ in range(h):
    l, r = input().split()
    l = "#" + l + "#"
    r = "#" + r + "#"
    mp_l.append(l)
    mp_r.append(r)
  mp_l.append("#" * (w + 2))
  mp_r.append("#" * (w + 2))
  
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp_l[y][x] == "L":
        start_l = (x, y)
      if mp_r[y][x] == "R":
        start_r = (x, y)

  search(start_l, start_r, mp_l, mp_r)

Submission status: Runtime Error

Solution code:
from collections import deque

direct_l = ((-1, 0), (1, 0), (0, 1), (0, -1))
direct_r = ((1, 0), (-1, 0), (0, 1), (0, -1))
directs = tuple(zip(direct_l, direct_r))

def search(start_l, start_r, mp_l, mp_r, dic):
  que = deque()
  que.append((start_l, start_r))
  dic[start_l[0]][start_l[1]][start_r[0]][start_r[1]] = True
  while que:
    pl, pr = que.popleft()
    lx, ly = pl
    rx, ry = pr
    for ld, rd in directs:
      ldx, ldy = ld
      rdx, rdy = rd
      lnx, lny = (lx + ldx, ly + ldy) if mp_l[ly + ldy][lx + ldx] != "#" else (lx, ly)
      rnx, rny = (rx + rdx, ry + rdy) if mp_r[ry + rdy][rx + rdx] != "#" else (rx, ry)
      if not dic[lnx][lny][rnx][rny]:
        dic[lnx][lny][rnx][rny] = True
        if mp_l[lny][lnx] == "%" and mp_r[rny][rnx] == "%":
          print("Yes")
          return
        if mp_l[lny][lnx] != "%" and mp_r[rny][rnx] != "%":
          que.append(((lnx, lny), (rnx, rny)))
  else:
    print("No")
    return


while True:
  w, h = map(int, input().split())
  if w == 0:
    break

  mp_l = ["#" * (w + 2)]
  mp_r = ["#" * (w + 2)]
  for _ in range(h):
    l, r = input().split()
    l = "#" + l + "#"
    r = "#" + r + "#"
    mp_l.append(l)
    mp_r.append(r)
  mp_l.append("#" * (w + 2))
  mp_r.append("#" * (w + 2))
  
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp_l[y][x] == "L":
        start_l = (x, y)
      if mp_r[y][x] == "R":
        start_r = (x, y)
  #dic[lx][ly][rx][ry]
  dic = [[[[False] * (h + 2) for _ in range(w + 2)] for _ in range(h + 2)] for _ in range(w + 2)]
  search(start_l, start_r, mp_l, mp_r, dic)

Submission status: Runtime Error

Solution code:
from collections import deque

directs = ((-1, 0, 1, 0), (1, 0, -1, 0), (0, 1, 0, 1), (0, -1, 0, -1))

def search(start_l, start_r, mp_l, mp_r, dic):
  que = deque()
  que.append((start_l[0], start_l[1], start_r[0], start_r[1]))
  dic[start_l[0]][start_l[1]][start_r[0]][start_r[1]] = True
  while que:
    lx, ly, rx, ry = que.popleft()
    for ldx, ldy, rdx, rdy in directs:
      lnx, lny = (lx + ldx, ly + ldy) if mp_l[ly + ldy][lx + ldx] != "#" else (lx, ly)
      rnx, rny = (rx + rdx, ry + rdy) if mp_r[ry + rdy][rx + rdx] != "#" else (rx, ry)
      if not dic[lnx][lny][rnx][rny]:
        dic[lnx][lny][rnx][rny] = True
        lsym, rsym = mp_l[lny][lnx], mp_r[rny][rnx]
        if lsym == "%" and rsym == "%":
          print("Yes")
          return
        if lsym != "%" and rsym != "%":
          que.append(((lnx, lny, rnx, rny)))
  else:
    print("No")
    return

def main():
  while True:
    w, h = map(int, input().split())
    if w == 0:
      break
  
    mp_l = ["#" * (w + 2)]
    mp_r = ["#" * (w + 2)]
    for _ in range(h):
      l, r = input().split()
      l = "#" + l + "#"
      r = "#" + r + "#"
      mp_l.append(l)
      mp_r.append(r)
    mp_l.append("#" * (w + 2))
    mp_r.append("#" * (w + 2))
    
    for y in range(1, h + 1):
      for x in range(1, w + 1):
        if mp_l[y][x] == "L":
          start_l = (x, y)
        if mp_r[y][x] == "R":
          start_r = (x, y)
    dic = [[[[False] * (h + 2) for _ in range(w + 2)] for _ in range(h + 2)] for _ in range(w + 2)]
    search(start_l, start_r, mp_l, mp_r, dic)
  
main()

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

def main():
  directs = ((-1, 0, 1, 0), (1, 0, -1, 0), (0, 1, 0, 1), (0, -1, 0, -1))
  while True:
    w, h = map(int, input().split())
    if w == 0:
      break
  
    mp_l = ["#" * (w + 2)]
    mp_r = ["#" * (w + 2)]
    for _ in range(h):
      l, r = input().split()
      l = "#" + l + "#"
      r = "#" + r + "#"
      mp_l.append(l)
      mp_r.append(r)
    mp_l.append("#" * (w + 2))
    mp_r.append("#" * (w + 2))
    
    for y in range(1, h + 1):
      for x in range(1, w + 1):
        if mp_l[y][x] == "L":
          start_l = (x, y)
        if mp_r[y][x] == "R":
          start_r = (x, y)
    
    dic = [[[[False] * (h + 2) for _ in range(w + 2)] for _ in range(h + 2)] for _ in range(w + 2)]
    def search():
      que = deque()
      app = que.append
      pop = que.popleft
      app((start_l[0], start_l[1], start_r[0], start_r[1]))
      dic[start_l[0]][start_l[1]][start_r[0]][start_r[1]] = True
      while que:
        lx, ly, rx, ry = pop()
        for ldx, ldy, rdx, rdy in directs:
          lnx, lny = (lx + ldx, ly + ldy) if mp_l[ly + ldy][lx + ldx] != "#" else (lx, ly)
          rnx, rny = (rx + rdx, ry + rdy) if mp_r[ry + rdy][rx + rdx] != "#" else (rx, ry)
          if not dic[lnx][lny][rnx][rny]:
            dic[lnx][lny][rnx][rny] = True
            lsym, rsym = mp_l[lny][lnx], mp_r[rny][rnx]
            if lsym == "%" and rsym == "%":
              print("Yes")
              return
            if lsym != "%" and rsym != "%":
              app(((lnx, lny, rnx, rny)))
      else:
        print("No")
        return
    search()
 
main()

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

def main():
  directs = ((-1, 0, 1, 0), (1, 0, -1, 0), (0, 1, 0, 1), (0, -1, 0, -1))
  while True:
    w, h = map(int, input().split())
    if w == 0:
      break
  
    mp_l = ["#" * (w + 2)]
    mp_r = ["#" * (w + 2)]
    for _ in range(h):
      l, r = input().split()
      l = "#" + l + "#"
      r = "#" + r + "#"
      mp_l.append(l)
      mp_r.append(r)
    mp_l.append("#" * (w + 2))
    mp_r.append("#" * (w + 2))
    
    for y in range(1, h + 1):
      for x in range(1, w + 1):
        if mp_l[y][x] == "L":
          start_l = (x, y)
        if mp_r[y][x] == "R":
          start_r = (x, y)
    
    dic = [[[[False] * (h + 2) for _ in range(w + 2)] for _ in range(h + 2)] for _ in range(w + 2)]
    def search():
      que = deque()
      app = que.append
      pop = que.popleft
      app((start_l[0], start_l[1], start_r[0], start_r[1]))
      dic[start_l[0]][start_l[1]][start_r[0]][start_r[1]] = True
      while que:
        lx, ly, rx, ry = pop()
        for ldx, ldy, rdx, rdy in directs:
          if mp_l[ly + ldy][lx + ldx] != "#":
            lnx, lny = lx + ldx, ly + ldy
          else:
            lnx, lny = lx, ly
          if mp_r[ry + rdy][rx + rdx] != "#":
            rnx, rny = rx + rdx, ry + rdy
          else:
            rnx, rny = rx, ry
          #lnx, lny = (lx + ldx, ly + ldy) if mp_l[ly + ldy][lx + ldx] != "#" else (lx, ly)
          #rnx, rny = (rx + rdx, ry + rdy) if mp_r[ry + rdy][rx + rdx] != "#" else (rx, ry)
          if not dic[lnx][lny][rnx][rny]:
            dic[lnx][lny][rnx][rny] = True
            lsym, rsym = mp_l[lny][lnx], mp_r[rny][rnx]
            if lsym == "%" and rsym == "%":
              print("Yes")
              return
            if lsym != "%" and rsym != "%":
              app(((lnx, lny, rnx, rny)))
      else:
        print("No")
        return
    search()
 
main()