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: Wrong Answer

Solution code:
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()
    s=set()
    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))
    dw=(-1,0,1,0)
    dh=(0,1,0,-1)
    while q:
        val=q.pop()
        if val in s: continue
        s.add(val)
        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 (lnp,rnp) in s: continue
            s.add((lnp,rnp))
            q.append((lnp,rnp))
    if (gl,gr) in s : print("Yes")
    else : print("No")

Submission status: Wrong Answer

Solution code:
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()
    s=set()
    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))
    dw=(-1,0,1,0)
    dh=(0,1,0,-1)
    while q:
        val=q.pop()
        s.add(val)
        lp=val[0]

Submission status: Memory Limit Exceeded

Solution code:
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()
    s=set()
    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))
    dw=(-1,0,1,0)
    dh=(0,1,0,-1)
    while q:
        val=q.pop()
        if val in s: continue
        s.add(val)
        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
            q.append((lnp,rnp))
    if (gl,gr) in s : print("Yes")
    else : print("No")

Submission status: Memory Limit Exceeded

Solution code:
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()
    s=set()
    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))
    dw=(-1,0,1,0)
    dh=(0,1,0,-1)
    while q:
        val=q.pop()
        s.add(val)
        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 (lnp,rnp) in s: continue
            s.add((lnp,rnp))
            q.append((lnp,rnp))
    if (gl,gr) in s : print("Yes")
    else : print("No")

Submission status: Memory Limit Exceeded

Solution code:
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()
    s=set()
    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))
    s.add((ls,rs))
    dw=(-1,0,1,0)
    dh=(0,1,0,-1)
    while q:
        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 (lnp,rnp) in s: continue
            s.add((lnp,rnp))
            q.append((lnp,rnp))
    if (gl,gr) in s : print("Yes")
    else : print("No")

Submission status: Accepted

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 = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-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 = []

    def f(w, h):
        w2 = w+2
        la = ['#' * w2]
        ra = ['#' * w2]
        ls = rs = None
        for i in range(1,h+1):
            lt, rt = LS()
            if 'L' in lt:
                ls = (i, lt.index('L') + 1)
            if 'R' in rt:
                rs = (i, rt.index('R') + 1)
            la.append('#' + lt + '#')
            ra.append('#' + rt + '#')
        la.append('#' * w2)
        ra.append('#' * w2)

        q = collections.deque([(ls[0], ls[1], rs[0], rs[1])])
        v = collections.defaultdict(bool)
        v[(ls[0], ls[1], rs[0], rs[1])] = 1
        while q:
            ly,lx,ry,rx = q.pop()
            for dy, dx in dd:
                lty = ly + dy
                ltx = lx + dx
                rty = ry + dy
                rtx = rx - dx
                if la[lty][ltx] == '#':
                    lty = ly
                    ltx = lx
                if ra[rty][rtx] == '#':
                    rty = ry
                    rtx = rx
                if v[(lty,ltx,rty,rtx)]:
                    continue
                v[(lty,ltx,rty,rtx)] = 1
                if la[lty][ltx] == '%' and ra[rty][rtx] == '%':
                    return 'Yes'
                if la[lty][ltx] != '%' and ra[rty][rtx] != '%':
                    q.append((lty,ltx,rty,rtx))

        return 'No'

    while True:
        w,h = LI()
        if w == 0 and h == 0:
            break
        rr.append(f(w,h))

    return '\n'.join(rr)



print(main())

Submission status: Accepted

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 = [[[[None] * (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:
          ltx, lty, rtx, rty = lx + ldx, ly + ldy, rx + rdx, ry + rdy
          if mp_l[lty][ltx] != "#":
            lnx, lny = ltx, lty
          else:
            lnx, lny = lx, ly
          if mp_r[rty][rtx] != "#":
            rnx, rny = rtx, rty
          else:
            rnx, rny = rx, ry
          tmp = dic[lnx][lny][rnx]
          if not tmp[rny]:
            tmp[rny] = True
            lsym, rsym = mp_l[lny][lnx], mp_r[rny][rnx]
            if lsym == "%":
              if rsym == "%":
                print("Yes")
                return
            elif rsym != "%":
              app(((lnx, lny, rnx, rny)))
      print("No")
      return
    search()
 
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while 1:
        w, h = LI()
        if w == h == 0:
            break
        check = defaultdict(lambda: True)
        field = SR(h)
        for i in range(h):
            for k in range(2 * w + 1):
                if field[i][k] == "L":
                    L = [k, i]
                if field[i][k] == "R":
                    R = [k, i]
        state = deque()
        state.append([L, R])
        flg = True
        while state and flg:
            l, r = state.pop()
            lx, ly = l
            rx, ry = r
            for mx, my in move:
                xl = lx + mx
                yl = ly + my
                xr = rx - mx
                yr = ry + my
                if not 0 <= xl < w:
                    xl -= mx
                if not w + 1 <= xr < 2 * w + 1:
                    xr += mx
                if not 0 <= yl < h:
                    yl -= my
                if not 0 <= yr < h:
                    yr -= my
                if field[yl][xl] == "%" and field[yr][xr] == "%":
                    flg = False
                    break
                if field[yl][xl] == "#":
                    yl -= my
                    xl -= mx
                if field[yr][xr] == "#":
                    yr -= my
                    xr += mx
                if check[(xl, xr, yl, yr)] and field[yl][xl] != "%" and field[yr][xr] != "%":
                    check[(xl, xr, yl, yr)] = False
                    state.append([[xl, yl], [xr, yr]])
        if not flg:
            print("Yes")
        else:
            print("No")
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
from collections import deque,defaultdict

d = [(1,0),(-1,0),(0,1),(0,-1)]

def bfs(sly,slx,sry,srx):
    bfs_map = defaultdict(lambda : 1)
    bfs_map[(sly,slx,sry,srx)] = 0
    q = deque()
    q.append((sly,slx,sry,srx))
    while q:
        ly,lx,ry,rx = q.popleft()
        for dy,dx in d:
            ly_ = ly+dy
            lx_ = lx+dx
            ry_ = ry+dy
            rx_ = rx-dx
            if ly_ < 0 or h <= ly_ or lx_ < 0 or w <= lx_:
                ly_,lx_ = ly,lx
            elif l[ly_][lx_] == "#":
                ly_,lx_ = ly,lx
            if ry_ < 0 or h <= ry_ or rx_ < 0 or w <= rx_:
                ry_,rx_ = ry,rx
            elif r[ry_][rx_] == "#":
                ry_,rx_ = ry,rx
            if ly_ == gly and lx_ == glx and ry_ == gry and rx_ == grx:
                return "Yes"
            if bfs_map[(ly_,lx_,ry_,rx_)]:
                if l[ly_][lx_] != "%" and r[ry_][rx_] != "%":
                    q.append((ly_,lx_,ry_,rx_))
                    bfs_map[(ly_,lx_,ry_,rx_)] = 0

    return "No"

while 1:
    w,h = map(int, input().split())
    if w == h == 0:
        break
    s = [input().split() for i in range(h)]
    l = [s[i][0] for i in range(h)]
    r = [s[i][1] for i in range(h)]
    for y in range(h):
        for x in range(w):
            if l[y][x] == "L":
                sly,slx = y,x
            elif l[y][x] == "%":
                gly,glx = y,x
    for y in range(h):
        for x in range(w):
            if r[y][x] == "R":
                sry,srx = y,x
            elif r[y][x] == "%":
                gry,grx = y,x
    print(bfs(sly,slx,sry,srx))

Submission status: Accepted

Solution code:
from collections import deque

def bfs(W, H):
    G = '%'
    edges = '#' * (W + 2)
    dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    mapL, mapR = [edges], [edges]
    for i in range(H):
        l, r = input().split()
        mapL.append('#' + l + '#')
        mapR.append('#' + r + '#')
        if 'L' in l:
            lx, ly = i+1, l.index('L')+1
        if 'R' in r:
            rx, ry = i+1, r.index('R')+1
    mapL.append(edges)
    mapR.append(edges)
    que = deque()
    enq, deq = que.append, que.popleft
    visited = [[[[0]*(W+2)for _ in[0]*(H+2)]for _ in[0]*(W+2)]for _ in[0]*(H+2)]
    enq((lx, ly, rx, ry))
    visited[lx][ly][rx][ry] = 1
    while que:
        lx, ly, rx, ry = deq()
        for dx, dy in dxy:
            llx, lly, rrx, rry = lx + dx, ly + dy, rx + dx, ry - dy
            if mapL[llx][lly] == '#':
                llx, lly = lx, ly
            if mapR[rrx][rry] == '#':
                rrx, rry = rx, ry
            if not visited[llx][lly][rrx][rry]:
                nextL, nextR = mapL[llx][lly], mapR[rrx][rry]
                if nextL == G and nextR == G:
                    return 'Yes'
                if nextL != G and nextR != G:
                    enq((llx, lly, rrx, rry))
                    visited[llx][lly][rrx][rry] = 1
    return 'No'

def main():
    for e in iter(input, '0 0'):
        W, H = map(int, e.split())
        print(bfs(W, H))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
dwh = zip([1,0,-1,0,],[0,1,0,-1])
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    A,B = [],[]
    for loop in xrange(H):
        a,b = raw_input().split()
        A.append(list(a))
        B.append(list(b))

    for h in xrange(H):
        for w in xrange(W):
            if A[h][w] == "L": wl ,hl  = w,h
            if B[h][w] == "R": wr ,hr  = w,h
            if A[h][w] == "%": wlg,hlg = w,h
            if B[h][w] == "%": wrg,hrg = w,h

    visited = [[[[False]*W for i in xrange(H)] for j in xrange(W)] for k in xrange(H)]    
    visited[hl][wl][hr][wr] = True
    que = [[wl,hl,wr,hr]]
    while que:
        wl,hl,wr,hr = que.pop(0)
        if (wl,hl) == (wlg,hlg) and (wr,hr) == (wrg,hrg):
            print "Yes"
            break
        for dw,dh in dwh:
            nwl,nhl = min(W-1,max(0,wl+dw)), min(H-1,max(0,hl+dh))
            if A[nhl][nwl] == "#": nwl,nhl = wl,hl
            nwr,nhr = min(W-1,max(0,wr-dw)), min(H-1,max(0,hr+dh))
            if B[nhr][nwr] == "#": nwr,nhr = wr,hr
            if not visited[nhl][nwl][nhr][nwr]:
                if ((nwl,nhl) == (wlg,hlg)) + ((nwr,nhr) == (wrg,hrg)) == 1: continue
                visited[nhl][nwl][nhr][nwr] = True
                que.append([nwl,nhl,nwr,nhr])
    else:
        print "No"

Submission status: Runtime Error

Solution code:
from collections import deque
dwh = zip([1,0,-1,0,],[0,1,0,-1])
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    A,B = [],[]
    for loop in xrange(H):
        a,b = raw_input().split()
        A.append(list(a))
        B.append(list(b))

    for h in xrange(H):
        for w in xrange(W):
            if A[h][w] == "L": wl ,hl  = w,h
            if B[h][w] == "R": wr ,hr  = w,h
            if A[h][w] == "%": wlg,hlg = w,h
            if B[h][w] == "%": wrg,hrg = w,h

    visited = [[[[False]*W for i in xrange(H)] for j in xrange(W)] for k in xrange(H)]    
    visited[hl][wl][hr][wr] = True
    que = deque([[wl,hl,wr,hr]])
    while que:
        wl,hl,wr,hr = que.popleft()
        if (wl,hl) == (wlg,hlg) and (wr,hr) == (wrg,hrg):
            print "Yes"
            break
        for dw,dh in dwh:
            nwl,nhl = min(W-1,max(0,wl+dw)), min(H-1,max(0,hl+dh))
            if A[nhl][nwl] == "#": nwl,nhl = wl,hl
            nwr,nhr = min(W-1,max(0,wr-dw)), min(H-1,max(0,hr+dh))
            if B[nhr][nwr] == "#": nwr,nhr = wr,hr
            if not visited[nhl][nwl][nhr][nwr]:
                if ((nwl,nhl) == (wlg,hlg)) + ((nwr,nhr) == (wrg,hrg)) == 1: continue
                visited[nhl][nwl][nhr][nwr] = True
                que.append([nwl,nhl,nwr,nhr])
    else:
        print "No"

Submission status: Runtime Error

Solution code:
from Queue import Queue

def isValid(W,H,x,y):
  return 0<=x and x<H and 0<=y and y<W

def walking(L,R,start):
  vec=[(1,0,1,0),(-1,0,-1,0),(0,1,0,-1),(0,-1,0,1)]
  q=Queue()
  searched={}
  q.put(startPos)
  searched[startPos]=True
  while q.qsize()>0:
    lx,ly,rx,ry=q.get()
    for dlx,dly,drx,dry in vec:
      if not isValid(W,H,lx+dlx,ly+dly): dlx,dly=(0,0)
      if not isValid(W,H,rx+drx,ry+dry): drx,dry=(0,0)
      if L[lx+dlx][ly+dly]=="#": dlx,dly=(0,0)
      if R[rx+drx][ry+dry]=="#": drx,dry=(0,0)
      newPos = (lx+dlx, ly+dly, rx+drx, ry+dry)
      if newPos in searched: continue
      if L[newPos[0]][newPos[1]]=="%" and R[newPos[2]][newPos[3]]=="%":
        print "Yes"
        return
      elif not L[newPos[0]][newPos[1]]=="%" and not R[newPos[2]][newPos[3]]=="%":
        q.put(newPos)
        searched[newPos]=True
  print "No"

while True:
  W,H=map(int,raw_input().split())
  if W==0: break
  L=[]
  R=[]
  lx=-1
  ly=-1
  rx=-1
  ry=-1
  for _ in xrange(H):
    l,r=raw_input().split()
    L.append(l)
    R.append(r)
  for i in xrange(H):
    for j in xrange(W):
      if L[i][j] == "L":
        lx=i
        ly=j
      if R[i][j] == "R":
        rx=i
        ry=j
  startPos=(lx,ly,rx,ry)
  walking(L,R,startPos)

Submission status: Runtime Error

Solution code:
from collections import deque
dd = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while 1:
    w, h = map(int, raw_input().split())
    if w==0:
        break
    M = [raw_input() for i in xrange(h)]
    ML = [e[:w] for e in M]
    MR = [e[w+1:] for e in M]
    for i in xrange(h):
        for j in xrange(w):
            if MR[i][j] == 'R':
                rx = j; ry = i
            elif ML[i][j] == 'L':
                lx = j; ly = i
    dist = {(rx, ry, lx, ly)}
    deq = deque()
    deq.append((rx, ry, lx, ly))
    ok = 0
    while deq and not ok:
        rx, ry, lx, ly = deq.popleft()
        for dx, dy in dd:
            n_rx = rx + dx
            if not 0 <= n_rx < w: n_rx = rx
            n_ry = ry + dy
            if not 0 <= n_ry < h: n_ry = ry
            rm = MR[n_ry][n_rx]
            if rm == '#':
                n_rx = rx; n_ry = ry
                rm = '.'
            n_lx = lx - dx
            if not 0 <= n_lx < w: n_lx = lx
            n_ly = ly + dy
            if not 0 <= n_ly < h: n_ly = ly
            lm = ML[n_ly][n_lx]
            if lm == '#':
                n_lx = lx; n_ly = ly
                lm = '.'
            if rm == '%' or lm == '%':
                if rm == '%' and lm == '%':
                    ok = 1
                continue
            n_key = (n_rx, n_ry, n_lx, n_ly)
            if n_key not in dist:
                dist.add(n_key)
                deq.append(n_key)
    print "Yes"*ok or "No"

Submission status: Runtime Error

Solution code:
from collections import deque
dd = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while 1:
    w, h = map(int, raw_input().split())
    if w==0:
        break
    M = [raw_input() for i in xrange(h)]
    ML = [e[:w] for e in M]
    MR = [e[w+1:] for e in M]
    rx = ry = lx = ly = None
    for i in xrange(h):
        for j in xrange(w):
            if MR[i][j] == 'R':
                rx = j; ry = i
            if ML[i][j] == 'L':
                lx = j; ly = i
    dist = {(rx, ry, lx, ly)}
    deq = deque()
    deq.append((rx, ry, lx, ly))
    ok = 0
    while deq and not ok:
        rx, ry, lx, ly = deq.popleft()
        for dx, dy in dd:
            n_rx = rx + dx
            if not 0 <= n_rx < w: n_rx = rx
            n_ry = ry + dy
            if not 0 <= n_ry < h: n_ry = ry
            rm = MR[n_ry][n_rx]
            if rm == '#':
                n_rx = rx; n_ry = ry
                rm = '.'
            n_lx = lx - dx
            if not 0 <= n_lx < w: n_lx = lx
            n_ly = ly + dy
            if not 0 <= n_ly < h: n_ly = ly
            lm = ML[n_ly][n_lx]
            if lm == '#':
                n_lx = lx; n_ly = ly
                lm = '.'
            if rm == '%' or lm == '%':
                if rm == '%' and lm == '%':
                    ok = 1
                continue
            n_key = (n_rx, n_ry, n_lx, n_ly)
            if n_key not in dist:
                dist.add(n_key)
                deq.append(n_key)
    print "Yes"*ok or "No"

Submission status: Runtime Error

Solution code:
from collections import deque
dd = [(-1, 0), (0, -1), (1, 0), (0, 1)]
deq = deque()
push = deq.append
pop = deq.popleft
clear = deq.clear
while 1:
    w, h = map(int, raw_input().split())
    if w==0:
        break
    M = [raw_input() for i in xrange(h)]
    rx = ry = lx = ly = None
    for i in xrange(h):
        e = M[i]
        for j in xrange(w):
            if e[j+w+1] == 'R':
                rx = j; ry = i
            if e[j] == 'L':
                lx = j; ly = i
    dist = {(rx, ry, lx, ly)}
    push((rx, ry, lx, ly))
    ok = 0
    while deq and not ok:
        rx, ry, lx, ly = pop()
        for dx, dy in dd:
            n_rx = rx + dx
            if not 0 <= n_rx < w: n_rx = rx
            n_ry = ry + dy
            if not 0 <= n_ry < h: n_ry = ry
            rm = M[n_ry][n_rx+w+1]
            if rm == '#':
                n_rx = rx; n_ry = ry
                rm = '.'
            n_lx = lx - dx
            if not 0 <= n_lx < w: n_lx = lx
            n_ly = ly + dy
            if not 0 <= n_ly < h: n_ly = ly
            lm = M[n_ly][n_lx]
            if lm == '#':
                n_lx = lx; n_ly = ly
                lm = '.'
            if rm == '%' or lm == '%':
                if rm == '%' and lm == '%':
                    ok = 1
                continue
            n_key = (n_rx, n_ry, n_lx, n_ly)
            if n_key not in dist:
                dist.add(n_key)
                push(n_key)
    clear()
    print "Yes"*ok or "No"

Submission status: Runtime Error

Solution code:
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=[[[[False for i in range(w)] for ii in range(h)] for iii in range(w)] for iiii in range(h)]
    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)
    while q:
        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:
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=[[[[False for i in range(w)] for ii in range(h)] for iii in range(w)] for iiii in range(h)]
    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)
    while q:
        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")
    dp.clear()
    q.clear()
    rl.clear()
    rr.clear()

Submission status: Runtime Error

Solution code:
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=[[[[False for i in range(w)] for ii in range(h)] for iii in range(w)] for iiii in range(h)]
    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")
    dp.clear()
    q.clear()
    rl.clear()
    rr.clear()

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.array((h,w,h,w))
    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")
    dp.clear()
    q.clear()
    rl.clear()
    rr.clear()

Submission status: Runtime Error

Solution code:
import numpy

Submission status: Runtime Error

Solution code:
import numpy as np
print(" ")