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

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]

                tpl = (tx,ty,kx,ky)

                if tpl in d and d[tpl] <= cnt:
                    continue

                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

                if hm == 2: continue

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

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]

                tpl = (tx,ty,kx,ky)

                if tpl in d and d[tpl] <= cnt:
                    continue

                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

#                if hm == 2: continue

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

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

#                if 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)

Submission status: Wrong Answer

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

                if 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)

Submission status: Wrong Answer

Solution code:
# Stray Twins

from collections import deque

DIR = (
    ((1, 0), (-1, 0)),
    ((-1, 0), (1, 0)),
    ((0, 1), (0, -1)),
    ((0, -1), (0, 1)),
)


class Cell:
    def __init__(self, obstacle):
        self.obstacle = obstacle
        self.taka_passed = False
        self.kazu_passed = False


class Twins:
    def __init__(self, taka, kazu, time):
        self.tx = taka[0]
        self.ty = taka[1]
        self.kx = kazu[0]
        self.ky = kazu[1]
        self.time = time


while True:
    x, y = (map(int, raw_input().split()))
    if (x, y) == (0, 0):
        break

    tx, ty = (map(int, raw_input().split()))
    kx, ky = (map(int, raw_input().split()))

    depart = []
    for i in range(y):
        depart.append(map(lambda x: Cell(bool(int(x))), raw_input().split()))

    queue = deque()
    time = 0
    queue.append(Twins([tx - 1, ty - 1], [kx - 1, ky - 1], time))
    depart[ty - 1][tx - 1].taka_passed = True
    depart[ky - 1][kx - 1].kazu_passed = True

    while True:
        try:
            tak = queue.popleft()
            if (tak.tx, tak.ty) == (tak.kx, tak.ky):
                time = tak.time
                break
            for i in range(4):
                ttx = tak.tx + DIR[i][0][0]
                tty = tak.ty + DIR[i][0][1]

                kkx = tak.kx + DIR[i][1][0]
                kky = tak.ky + DIR[i][1][1]

                if (ttx < 0 or ttx == x) \
                    or (tty < 0 or tty == y) \
                    or depart[tty][ttx].obstacle:
                    ttx = tak.tx
                    tty = tak.ty
                    #depart[tty][ttx].taka_passed = False

                if (kkx < 0 or kkx == x) \
                    or (kky < 0 or kky == y) \
                    or depart[kky][kkx].obstacle:
                    kkx = tak.kx
                    kky = tak.ky
                    #depart[kky][kkx].kazu_passed = False

                if not depart[tty][ttx].taka_passed and not depart[kky][kkx].kazu_passed:
                    queue.append(Twins([ttx, tty], [kkx, kky], tak.time + 1))
                    depart[tty][ttx].taka_passed = True
                    depart[kky][kkx].kazu_passed = True
        except IndexError:
            time = 100
            break

    print time if time < 100 else 'NA'

Submission status: Wrong Answer

Solution code:
# Stray Twins

from collections import deque

DIR = (
    ((1, 0), (-1, 0)),
    ((-1, 0), (1, 0)),
    ((0, 1), (0, -1)),
    ((0, -1), (0, 1)),
)


class Cell:
    def __init__(self, obstacle):
        self.obstacle = obstacle
        self.taka_passed = False
        self.kazu_passed = False


class Twins:
    def __init__(self, taka, kazu, time):
        self.tx = taka[0]
        self.ty = taka[1]
        self.kx = kazu[0]
        self.ky = kazu[1]
        self.time = time


while True:
    x, y = (map(int, raw_input().split()))
    if (x, y) == (0, 0):
        break

    tx, ty = (map(int, raw_input().split()))
    kx, ky = (map(int, raw_input().split()))

    depart = []
    for i in range(y):
        depart.append(map(lambda x: Cell(bool(int(x))), raw_input().split()))

    queue = deque()
    time = 0
    queue.append(Twins([tx - 1, ty - 1], [kx - 1, ky - 1], time))
    depart[ty - 1][tx - 1].taka_passed = True
    depart[ky - 1][kx - 1].kazu_passed = True

    while time < 100:
        try:
            tak = queue.popleft()
            time = tak.time

            if (tak.tx, tak.ty) == (tak.kx, tak.ky):
                break

            for i in range(4):
                ttx = tak.tx + DIR[i][0][0]
                tty = tak.ty + DIR[i][0][1]

                kkx = tak.kx + DIR[i][1][0]
                kky = tak.ky + DIR[i][1][1]

                if (ttx < 0 or ttx == x) \
                    or (tty < 0 or tty == y) \
                    or depart[tty][ttx].obstacle:
                    ttx = tak.tx
                    tty = tak.ty
                    #depart[tty][ttx].taka_passed = False

                if (kkx < 0 or kkx == x) \
                    or (kky < 0 or kky == y) \
                    or depart[kky][kkx].obstacle:
                    kkx = tak.kx
                    kky = tak.ky
                    #depart[kky][kkx].kazu_passed = False

                if not depart[tty][ttx].taka_passed and not depart[kky][kkx].kazu_passed:
                    queue.append(Twins([ttx, tty], [kkx, kky], tak.time + 1))
                    depart[tty][ttx].taka_passed = True
                    depart[kky][kkx].kazu_passed = True

        except IndexError:
            time = 100
            break

    print time if time < 100 else 'NA'

Submission status: Wrong Answer

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:
                continue
            if dkx<0 or dkx>=X or dky<0 or dky>=Y:
                continue
            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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
# Aizu Problem 0223: Stray Twins

import sys, math, os, bisect
from queue import Queue

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def stray_twins(W, H, grid, tx, ty, kx, ky):
    moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    Q = Queue()
    Q.put((tx, ty, kx, ky, 0))
    visited = set()
    while not Q.empty():
        tx, ty, kx, ky, t = Q.get()
        visited.add((tx, ty, kx, ky))
        if t >= 100:
            return "NA"
        if tx == kx and ty == ky:
            return t
        for dy, dx in moves:
            dtx = max(0, min(tx + dx, W - 1))
            dty = max(0, min(ty + dy, H - 1))
            dkx = max(0, min(kx - dx, W - 1))
            dky = max(0, min(ky - dy, H - 1))
            if grid[dty][dtx] == 1:
                dtx, dty = tx, ty
            if grid[dky][dkx] == 1:
                dkx, dky = kx, ky
            if (dtx, dty, dkx, dky) not in visited:
                Q.put((dtx, dty, dkx, dky, t + 1))
    
while True:
    W, H = map(int, input().split())
    if W == H == 0:
        break
    tx, ty = [int(_) - 1 for _ in input().split()]
    kx, ky = [int(_) - 1 for _ in input().split()]
    grid = [[int(_) for _ in input().split()] for __ in range(H)]
    print(stray_twins(W, H, grid, tx, ty, kx, ky))

Submission status: Accepted

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 = set()
        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.add((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: Accepted

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

def main():
    while(True):
        W, H = map(int, input().split())
        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]])
        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: Accepted

Solution code:
from collections import deque

while(True):
    W, H = map(int, input().split())
    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]])
    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)

Submission status: Accepted

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

def main():
    while(True):
        W, H = map(int, input().split())
        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))
        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: 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]*(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 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: 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]*(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: 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]*(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 not(tx-kx or 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: 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]*(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: 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]*(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
            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)
                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)
                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()