Problem:


迷子の双子

たかゆき君とかずゆき君は仲良しの双子ですが、行動が真逆です。 例えば、たかゆき君が西に行けば、かずゆき君は東へ行き、かずゆき君が北へ行けば、たかゆき君は南へ行きます。 現在 2 人はデパートに来ており、別々の場所にいます。真逆に移動してしまう 2 人ができるだけ早く出会うためにはどうしたらよいでしょうか?

  デパートは横 W 個 &times; 縦 H 個のマスで構成されるグリッドで表され、2 人は単位時間に東西南北に 1 マス分移動することができます。ただし、グリッドの範囲外や障害物のあるマスに移動することはできません。

図のように、グリッドのマスの位置は座標 (x, y) で表されます。

 グリッドの情報と 2 人の初期位置を入力とし、2 人が出会うまでの最短の時間を出力するプログラムを作成してください。出会うことができない場合や、出会うのに 100 以上の時間を要する場合は、NA と出力してください。グリッドの情報は、H 行 W 列の数字、2 人の位置情報は座標によって与えられます。
 

  移動後にたかゆき君かかずゆき君のうち、どちらか一方が障害物やグリッドの範囲外に位置してしまうときには、移動ができないので、障害物やグリッドの範囲外に位置する方は元の場所に戻りますが、そうでない方は元の場所に戻ることなく動くことができます。

  なお、2 人が出会うとは、移動後に 2 人が同じマスに止まることを言います。2 人がすれ違っても、出会ったことにはなりません。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。
各データセットは以下の形式で与えられます。

W H
tx ty
kx ky
d11 d21 ... dW1
d12 d22 ... dW2
:
d1H d2H ... dWH

1 行目にデパートの大きさW, H (1 ≤ W, H ≤ 50) が与えられます。2 行目にたかゆき君の初期位置 tx, ty、3 行目にかずゆき君の初期位置 kx, ky が与えられます。

続く H 行にデパートの情報が与えられます。di,j はマス (i, j) の種類を表し、0 のとき移動可能なマス、1 のとき障害物があるマスを表します。

データセットの数は 100 を超えません。

Output

入力データセットごとに、最短の時間を１行に出力します。

Sample Input

6 6
2 4
6 2
0 0 0 0 1 0
0 1 0 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 0 0
3 3
1 1
3 3
0 0 0
0 1 0
0 0 0
0 0

Output for the Sample Input

3
NA



Sample input:
6 6
2 4
6 2
0 0 0 0 1 0
0 1 0 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 0 0
3 3
1 1
3 3
0 0 0
0 1 0
0 0 0
0 0


Sample output:
3
NA

Submission status: Accepted

Solution code:
# from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[0]+[abs(1-int(a)) for a in stdin.readline().split()]+[0] for i in range(H)]
        ma = [[0]*(W+2)] + ma + [[0]*(W+2)]
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            if c+1 > 100: continue
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy =  dx * ma[ty+dy][tx+dx],  dy * ma[ty+dy][tx+dx]
                kdx, kdy = -dx * ma[ky-dy][kx-dx], -dy * ma[ky-dy][kx-dx]
                ttx,tty,kkx,kky = tx+tdx,ty+tdy,kx+kdx,ky+kdy
                if (ttx,tty,kkx,kky) in pas: continue
                que.append([ttx,tty,kkx,kky,c+1])
                pas.add((ttx,tty,kkx,kky))
        print(ans)

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Accepted

Solution code:
# from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[False]+[bool(1-int(a)) for a in stdin.readline().split()]+[False] for i in range(H)]
        ma = [[False]*(W+2)] + ma + [[False]*(W+2)]
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            if c+1 > 100: continue
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = ( dx, dy) if ma[ty+dy][tx+dx] else (0,0)
                kdx, kdy = (-dx,-dy) if ma[ky-dy][kx-dx] else (0,0)
                if (tx+tdx,ty+tdy,kx+kdx,ky+kdy) in pas: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                pas.add((tx+tdx,ty+tdy,kx+kdx,ky+kdy))
        print(ans)

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Accepted

Solution code:
direc = ((1,0),(-1,0),(0,1),(0,-1))


#d = [[[[0 for i in range(Y+1)] for i in range(X+1)] for i in range(Y+1)] for i in range(X+1)]
#d[1][1][2][2]=3
# print(d)
while 1:
    X, Y = list(map(int,input().split()))
    if X == 0: break

    ftx, fty = list(map(lambda x: x-1, map(int, input().split())))
    fkx, fky = list(map(lambda x: x-1, map(int, input().split())))

    m = [list(map(int, input().split())) for i in range(Y)]

    d = {(ftx, fty, fkx, fky): 0}

    s = [[0, (ftx, fty, fkx, fky)]]
    res = 'NA'
    while len(s) > 0:
        spm = s.pop(0)
        cnt = spm[0] + 1
        if cnt > 100:
            break

        def search_move():
            for i in range(4):
                #print('--' + str(spm[1]))
                tx = spm[1][0]+direc[i][0]
                ty = spm[1][1]+direc[i][1]
                kx = spm[1][2]-direc[i][0]
                ky = spm[1][3]-direc[i][1]


                hm = 0
                if tx < 0 or tx >= X or ty < 0 or ty >= Y or m[ty][tx] == 1:
                    tx = spm[1][0]
                    ty = spm[1][1]
                    hm += 1
                if kx < 0 or kx >= X or ky < 0 or ky >= Y or m[ky][kx] == 1:
                    kx = spm[1][2]
                    ky = spm[1][3]
                    hm += 1

                if hm == 2: continue
                tpl = (tx,ty,kx,ky)
                if tpl in d and d[tpl] <= cnt:
                    continue

                #print(tpl)
                if tx == kx and ty == ky:
                    return True
                else:
                    s.append([cnt,tpl])
                    d[tpl] = cnt
            return False
        if search_move():
            res = str(cnt)
            break
    print(res)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(tx,ty,kx,ky,d):
    dict = {}
    
    que = deque([(tx,ty,kx,ky,0)])
    while len(que):
        tx,ty,kx,ky,t = que.popleft()
        try:
            if dict[(tx,ty,kx,ky)] <= t:
                continue
        except KeyError:
            dict[(tx,ty,kx,ky)] = t
        
        if tx == kx and ty == ky:
            return t
        t += 1
        if 100 < t:
            break
        que.append((tx if d[ty][tx + 1] else tx + 1,ty,kx if d[ky][kx - 1] else kx - 1,ky,t))
        que.append((tx,ty if d[ty + 1][tx] else ty + 1,kx,ky if d[ky - 1][kx] else ky - 1,t))
        que.append((tx if d[ty][tx - 1] else tx - 1,ty,kx if d[ky][kx + 1] else kx + 1,ky,t))
        que.append((tx,ty if d[ty - 1][tx] else ty - 1,kx,ky if d[ky + 1][kx] else ky + 1,t))
    return 'NA'

import sys
f = sys.stdin

while True:
    x, y = map(int, f.readline().split())
    if x == y == 0:
        break
    tx, ty = map(int, f.readline().split())
    kx, ky = map(int, f.readline().split())
    depart = [[1] * (x + 2)] + [[1] + list(map(int, f.readline().split())) + [1] for i in range(y)] + [[1] * (x + 2)]
    print(bfs(tx,ty,kx,ky,depart))

Submission status: Accepted

Solution code:
from Queue import Queue
mv=((-1,0),(1,0),(0,-1),(0,1))
while True:
    X,Y=map(int,raw_input().split())
    if X==Y==0:break
    tx,ty=map(int,raw_input().split())
    kx,ky=map(int,raw_input().split())
    tx,ty,kx,ky=tx-1,ty-1,kx-1,ky-1
    D=[map(int,raw_input().split()) for i in range(Y)]
    Q=Queue()
    Q.put((tx,ty,kx,ky,0))
    visited=set()
    visited.add((tx,ty,kx,ky))
    while not Q.empty():
        tx,ty,kx,ky,t=Q.get()
        if t>=100:
            print "NA"
            break
        if tx==kx and ty==ky:
            print t
            break
        for i in range(4):
            dtx,dty=tx+mv[i][0],ty+mv[i][1]
            dkx,dky=kx-mv[i][0],ky-mv[i][1]
            if dtx<0 or dtx>=X or dty<0 or dty>=Y:
                dtx,dty=tx,ty
            if dkx<0 or dkx>=X or dky<0 or dky>=Y:
                dkx,dky=kx,ky
            if D[dty][dtx]==1:
                dtx,dty=tx,ty
            if D[dky][dkx]==1:
                dkx,dky=kx,ky
            if (dtx,dty,dkx,dky) not in visited:
                visited.add((dtx,dty,dkx,dky))
                Q.put((dtx,dty,dkx,dky,t+1))
    else:
        print "NA"

Submission status: Accepted

Solution code:
from collections import deque

def search(tx, ty, kx, ky, mp):
  direct = ((-1, 0, 1, 0), (1, 0, -1, 0), (0, -1, 0, 1), (0, 1, 0, -1))
  dic = {}
  dic[(tx, ty, kx, ky)] = 0
  que = deque()
  que.append((0, (tx, ty, kx, ky)))
  while que:
    dist, p = que.popleft()
    tx, ty, kx, ky = p
    for dtx, dty, dkx, dky in direct:
      if mp[ty + dty][tx + dtx] == 0:
        ntx, nty = tx + dtx, ty + dty
      else:
        ntx, nty = tx, ty
      if mp[ky + dky][kx + dkx] == 0:
        nkx, nky = kx + dkx, ky + dky
      else:
        nkx, nky = kx, ky
      if (ntx, nty, nkx, nky) not in dic:
        if (ntx, nty) == (nkx, nky):
          print(dist + 1)
          return
        dic[(ntx, nty, nkx, nky)] = True
        que.append((dist + 1, (ntx, nty, nkx, nky)))
  else:
    print("NA")

while True:
  w, h = map(int, input().split())
  if w == 0:
    break
  tx, ty = map(int, input().split())
  kx, ky = map(int, input().split())
  mp = [[1] + list(map(int, input().split())) + [1] for _ in range(h)]
  mp.insert(0, [1] * (w + 2))
  mp.append([1] * (w + 2))

  search(tx, ty, kx, ky, mp)

Submission status: Accepted

Solution code:
from collections import deque

def search(tx, ty, kx, ky, mp):
  direct = ((-1, 0, 1, 0), (1, 0, -1, 0), (0, -1, 0, 1), (0, 1, 0, -1))
  dic = {}
  dic[(tx, ty, kx, ky)] = 0
  que = deque()
  que.append((0, (tx, ty, kx, ky)))
  while que:
    dist, p = que.popleft()
    tx, ty, kx, ky = p
    for dtx, dty, dkx, dky in direct:
      if mp[ty + dty][tx + dtx] == 0:
        ntx, nty = tx + dtx, ty + dty
      else:
        ntx, nty = tx, ty
      if mp[ky + dky][kx + dkx] == 0:
        nkx, nky = kx + dkx, ky + dky
      else:
        nkx, nky = kx, ky
      if (ntx, nty, nkx, nky) not in dic:
        if (ntx, nty) == (nkx, nky):
          if dist + 1 >= 100:
            print("NA")
          else:
            print(dist + 1)
          return
        dic[(ntx, nty, nkx, nky)] = True
        que.append((dist + 1, (ntx, nty, nkx, nky)))
  else:
    print("NA")

def main():
  while True:
    w, h = map(int, input().split())
    if w == 0:
      break
    tx, ty = map(int, input().split())
    kx, ky = map(int, input().split())
    mp = [[1] + list(map(int, input().split())) + [1] for _ in range(h)]
    mp.insert(0, [1] * (w + 2))
    mp.append([1] * (w + 2))
  
    search(tx, ty, kx, ky, mp)

main()

Submission status: Accepted

Solution code:
from collections import deque
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))

DD = [-1, 1]
while 1:
    W, H = map(int, input().split())
    if W == H == 0:
        break
    tx, ty = map(int, input().split())
    kx, ky = map(int, input().split())
    D = [list(map(int, input().split())) for i in range(H)]
    que = deque()
    push = que.append
    pop = que.popleft
    key = (tx-1, ty-1, kx-1, ky-1)
    push(key)
    dist = {key: 0, (kx-1, ky-1, tx-1, ty-1): 0}
    while que:
        x0, y0, x1, y1 = key = pop()
        d = dist[key]
        if x0 == x1 and y0 == y1:
            print(d)
            break
        if d == 99:
            continue
        for dx in DD:
            nx0 = x0 + dx
            if not 0 <= nx0 < W or D[y0][nx0]:
                nx0 = x0
            nx1 = x1 - dx
            if not 0 <= nx1 < W or D[y1][nx1]:
                nx1 = x1
            key = (nx0, y0, nx1, y1)
            if key not in dist:
                dist[key] = d + 1
                push(key)
                key = (nx1, y1, nx0, y0)
                dist[key] = d + 1
        for dy in DD:
            ny0 = y0 + dy
            if not 0 <= ny0 < H or D[ny0][x0]:
                ny0 = y0
            ny1 = y1 - dy
            if not 0 <= ny1 < H or D[ny1][x1]:
                ny1 = y1
            key = (x0, ny0, x1, ny1)
            if key not in dist:
                dist[key] = d + 1
                push(key)
                key = (x1, ny1, x0, ny0)
                dist[key] = d + 1
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
from line_profiler import LineProfiler
from collections import deque

def main():
    while(True):
        W, H = map(int, input().split())
        # print(W,H)
        if not W: break
        tx,ty = map(int, input().split())
        kx,ky = map(int, input().split())
        ma = [[False]*(W+2) for _ in range(H+2)]
        for i in range(1,H+1):
            for j,a in enumerate(input().split()):
                ma[i][j+1] = bool(1-int(a))
        from pprint import pprint
        que = deque([[tx,ty,kx,ky,0]])
        # pa = [[[[False]*(W+2) for ii in range(H+2)] for jj in range(W+2)] for kk in range(H+2)]
        pas = []
        ans = "NA"
        while(que):
            # if len(que)>10:break
            # pprint(que)
            tx,ty,kx,ky,c = que.popleft()
            # import copy
            # toprint = copy.deepcopy(ma)
            # toprint[ty][tx] = "tt"
            # toprint[ky][kx] = "kk"
            # for i in range(H+2):
            #     print("".join(( toprint[i][j] if toprint[i][j] in ["tt","kk"] else "  ") if toprint[i][j] else "**" for j in range(W+2)))
            if c > 100: break
            if tx == kx and ty == ky:
                ans = c
                break
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = [ dx, dy] if ma[ty+dy][tx+dx] else [0,0]
                kdx, kdy = [-dx,-dy] if ma[ky-dy][kx-dx] else [0,0]
                # if pa[tx+tdx][ty+tdy][kx+kdx][ky+kdy]: continue
                if [tx+tdx,ty+tdy,kx+kdx,ky+kdy] in pas: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                # pa[tx+tdx][ty+tdy][kx+kdx][ky+kdy] = True
                pas.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy])
        print(ans)
        # pprint(ma)

if __name__ == "__main__":
    prf = LineProfiler()
    prf.add_function(main)
    prf.runcall(main)
    prf.print_stats()
    # main()

Submission status: Runtime Error

Solution code:
# from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, sys.stdin().split())
        if not W: break
        tx,ty = map(int, sys.stdin().split())
        kx,ky = map(int, sys.stdin().split())
        ma = [[False]*(W+2) for _ in range(H+2)]
        for i in range(1,H+1):
            for j,a in enumerate(sys.stdin().split()):
                ma[i][j+1] = bool(1-int(a))
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if c > 100: break
            if tx == kx and ty == ky:
                ans = c
                break
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = [ dx, dy] if ma[ty+dy][tx+dx] else [0,0]
                kdx, kdy = [-dx,-dy] if ma[ky-dy][kx-dx] else [0,0]
                if (tx+tdx,ty+tdy,kx+kdx,ky+kdy) in pas: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                pas.add((tx+tdx,ty+tdy,kx+kdx,ky+kdy))
        print(ans)

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Runtime Error

Solution code:
from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[False]*(W+2) for _ in range(H+2)]
        for i in range(1,H+1):
            for j,a in enumerate(stdin.readline().split()):
                ma[i][j+1] = bool(1-int(a))
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = [ dx, dy] if ma[ty+dy][tx+dx] else [0,0]
                kdx, kdy = [-dx,-dy] if ma[ky-dy][kx-dx] else [0,0]
                if (tx+tdx,ty+tdy,kx+kdx,ky+kdy) in pas: continue
                if c+1 > 100: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                pas.add((tx+tdx,ty+tdy,kx+kdx,ky+kdy))
        print(ans)

if __name__ == "__main__":
    prf = LineProfiler()
    prf.add_function(main)
    prf.runcall(main)
    prf.print_stats()
    # main()

Submission status: Runtime Error

Solution code:
from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[False]*(W+2) for _ in range(H+2)]
        for i in range(1,H+1):
            for j,a in enumerate(stdin.readline().split()):
                ma[i][j+1] = bool(1-int(a))
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = ( dx, dy) if ma[ty+dy][tx+dx] else (0,0)
                kdx, kdy = (-dx,-dy) if ma[ky-dy][kx-dx] else (0,0)
                ttx,tty,kkx,kky = tx+tdx,ty+tdy,kx+kdx,ky+kdy
                if (ttx,tty,kkx,kky) in pas: continue
                if c+1 > 100: continue
                que.append([ttx,tty,kkx,kky,c+1])
                pas.add((ttx,tty,kkx,kky))
        print(ans)

if __name__ == "__main__":
    prf = LineProfiler()
    prf.add_function(main)
    prf.runcall(main)
    prf.print_stats()
    # main()

Submission status: Runtime Error

Solution code:
direc = ((1,0),(-1,0),(0,1),(0,-1))


#d = [[[[0 for i in range(Y+1)] for i in range(X+1)] for i in range(Y+1)] for i in range(X+1)]
#d[1][1][2][2]=3
# print(d)
while 1:
    X, Y = list(map(int,input().split()))
    if X == 0: break

    ftx, fty = list(map(lambda x: x-1, map(int, input().split())))
    fkx, fky = list(map(lambda x: x-1, map(int, input().split())))

    m = [list(map(int, input().split())) for i in range(Y)]

    d = {(ftx, fty, fkx, fky): 0}

    s = [[0, (ftx, fty, fkx, fky)]]
    res = 'NA'
    while len(s) > 0:
        spm = s.pop(0)
        cnt = spm[0] + 1
        if cnt > 100:
            break

        def search_move():
            for i in range(4):
                tx = spm[1][0]+direc[i][0]
                ty = spm[1][1]+direc[i][1]
                kx = spm[1][2]-direc[i][0]
                ky = spm[1][3]-direc[i][1]


                hm = 0
                if tx < 0 or tx >= X or ty < 0 or ty >= Y or m[ty][tx] == 1:
                    tx = ftx
                    ty = fty
                    hm += 1
                if kx < 0 or kx >= X or ky < 0 or ky >= Y or m[ky][kx] == 1:
                    kx = fkx
                    ky = fky
                    hm += 1

                hm == 2: continue
                tpl = (tx,ty,kx,ky)
                if tpl in d and d[tpl] <= cnt:
                    continue

                if tx == kx and ty == ky:
                    return True
                else:
                    s.append([cnt,tpl])
                    d[tpl] = cnt
    #            print(tpl)
            return False
        if search_move():
            res = str(cnt)
            break
    print(res)