Problem:


忍者のビル登り

 忍者のあつしさんは、毎日朝早くから夜遅くまで忍者ビルの屋上から町を警備しています。この忍者ビルは、隣接する 2 つの同じ階数のビルであり、あつしさんは警備のために、ビルとビルの間をジャンプしながら屋上へ向かうことを日課としています。

 この 2 つのビルは頻繁に清掃が行われるため、ビル登りの助けとなるはしごや障害となる滑りやすい部分があります。  しかも、はしごや滑りやすい部分の位置は毎日変わります。   そのためあつしさんは、屋上へ向かう方法を毎日考えなければいけません。

 あつしさんは二つ並んだ同じ階数のビルの壁を跳び移りながら、ビルの屋上を目指します。ジャンプ
はどちらか一方のビルの1階から始められます。向かい側のビルへジャンプするときには、同じ階・1つ上の階・2 つ上の階の、いずれかに飛び移ることができます。

 壁には以下の 3 種類があり、それぞれの壁にジャンプした後の移動が決まっています。

   
0. 普通の壁: 上下の移動はしない。次のジャンプはそこから行う。

   
1. はしご: はしごは 2 つ以上の階にまたがってかかっており、今いるはしごの一番上まで移動する。次のジャンプはそこから行う。

   
2. すべる壁: 普通の壁かはしごの一番上まで滑り落ちる。次のジャンプはそこから行う。

 また、壁は 1 階から屋上のすぐ下の最上階まであり、屋上へはそのビルの最上階からのみ行くことが
できます。また、ビルの最下階の壁はすべる壁にはなりません。

 2 つのビルの階数 n と 2 つのビルの壁の種類を入力とし、最少で何回目のジャンプで最上階までたどり着き、屋上まで行くことができるかを出力するプログラムを作成してください。なお、どちらのビルの屋上にたどり着いてもよいものとします。ただし、あつしさんがどちらのビルの屋上へもたどり着けない場合は“NA”と出力してください。

Input

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

n
a1 a2 ... an
b1 b2 ... bn

１行目にビルの階数 n (3 ≤ n  ≤ 100) が与えられます。２行目に１ つ目のビルの 1 階から n 階までの壁の情報 ai、３行目に２つ目のビルの 1 階から n 階までの壁の情報 bi が与えられます。ai, bi はi 階目の壁の情報を表し、0 が普通の壁、1 がはしご(i 階と i+1 階にまたがる)、2 がすべる壁を表します。

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

Output

入力データセットごとに、ジャンプの回数を１行に出力します。

Sample Input

8
0 0 0 2 2 2 0 0
1 1 1 1 0 0 0 0
4
1 1 2 2
0 0 2 2
0

Output for the Sample Input

4
NA



Sample input:
8
0 0 0 2 2 2 0 0
1 1 1 1 0 0 0 0
4
1 1 2 2
0 0 2 2
0


Sample output:
4
NA

Submission status: Wrong Answer

Solution code:
import Queue
while True:
    n = input()
    if n==0:
        break
    a = []
    nxt = [range(n) for i in xrange(2)]
    for i in xrange(2):
        a.append(map(int, raw_input().split()))
    for i in xrange(2):
        back = 0
        for j in xrange(n):
            if a[i][j]==2:
                nxt[i][j] = back
            else:
                back = j
        forw = -1
        for j in xrange(n-1,-1,-1):
            if a[i][j]==1:
                nxt[i][j] = forw
            else:
                forw = j-1
    cost = [[10**9] * n for i in xrange(2)]
    que = Queue.PriorityQueue()
    que.put((0, 0, 0))
    que.put((0, 1, 0))
    ans = -1
    while not que.empty():
        co, sd, st = que.get()
        if st==n-1:
            ans = co
            break
        if cost[sd][st] < co:
            continue
        step = nxt[sd^1][st+1]
        if co+1 < cost[sd^1][step]:
            cost[sd^1][step] = co+1
            que.put((co+1, sd^1, step))
        if st+2<n:
            step = nxt[sd^1][st+2]
            if co+1 < cost[sd^1][step]:
                cost[sd^1][step] = co+1
                que.put((co+1, sd^1, step))
    print "NA" if ans==-1 else ans

Submission status: Wrong Answer

Solution code:
import Queue
while True:
    n = input()
    if n==0:
        break
    a = []
    nxt = [range(n) for i in xrange(2)]
    for i in xrange(2):
        a.append(map(int, raw_input().split()))
    for i in xrange(2):
        back = 0
        for j in xrange(n):
            if a[i][j]==2:
                nxt[i][j] = back
            else:
                back = j
        forw = n-1
        for j in xrange(n-1,-1,-1):
            if a[i][j]==1:
                nxt[i][j] = forw
            else:
                forw = j-1
    cost = [[10**9] * n for i in xrange(2)]
    que = Queue.PriorityQueue()
    que.put((0, 0, 0))
    que.put((0, 1, 0))
    ans = -1
    while not que.empty():
        co, sd, st = que.get()
        if st==n-1:
            ans = co
            break
        if cost[sd][st] < co:
            continue
        step = nxt[sd^1][st+1]
        if co+1 < cost[sd^1][step]:
            cost[sd^1][step] = co+1
            que.put((co+1, sd^1, step))
        if st+2<n:
            step = nxt[sd^1][st+2]
            if co+1 < cost[sd^1][step]:
                cost[sd^1][step] = co+1
                que.put((co+1, sd^1, step))
    print "NA" if ans==-1 else ans

Submission status: Wrong Answer

Solution code:
import Queue
while True:
    n = input()
    if n==0:
        break
    a = []
    nxt = [range(n) for i in xrange(2)]
    for i in xrange(2):
        a.append(map(int, raw_input().split()))
    for i in xrange(2):
        back = 0
        for j in xrange(n):
            if a[i][j]==2:
                nxt[i][j] = back
            else:
                back = j
        forw = n-1
        for j in xrange(n-1,-1,-1):
            if a[i][j]==1:
                nxt[i][j] = forw
            else:
                forw = j-1
    cost = [[10**9] * n for i in xrange(2)]
    que = Queue.PriorityQueue()
    que.put((0, 0, 0))
    que.put((0, 1, 0))
    ans = -1
    while not que.empty():
        co, sd, st = que.get()
        if st==n-1:
            ans = co
            break
        if cost[sd][st] < co:
            continue
        for i in xrange(3 if st+2<n else 2):
            step = nxt[sd^1][st+i]
            if co+1 < cost[sd^1][step]:
                cost[sd^1][step] = co+1
                que.put((co+1, sd^1, step))
    print "NA" if ans==-1 else ans

Submission status: Wrong Answer

Solution code:
import Queue
while True:
    n = input()
    if n==0:
        break
    a = []
    nxt = [range(n) for i in xrange(2)]
    for i in xrange(2):
        a.append(map(int, raw_input().split()))
    for i in xrange(2):
        back = 0
        for j in xrange(n):
            if a[i][j]==2:
                nxt[i][j] = back
            else:
                back = j
        forw = n-1
        for j in xrange(n-1,-1,-1):
            if a[i][j]==1:
                nxt[i][j] = forw
            else:
                forw = j-1
    cost = [[10**9] * n for i in xrange(2)]
    que = Queue.PriorityQueue()
    que.put((0, 0, nxt[0][0]))
    que.put((0, 1, nxt[0][0]))
    ans = -1
    while not que.empty():
        co, sd, st = que.get()
        if st==n-1:
            ans = co
            break
        if cost[sd][st] < co:
            continue
        for i in xrange(3 if st+2<n else 2):
            step = nxt[sd^1][st+i]
            if co+1 < cost[sd^1][step]:
                cost[sd^1][step] = co+1
                que.put((co+1, sd^1, step))
    print "NA" if ans==-1 else ans

Submission status: Wrong Answer

Solution code:
def bfs(b):
    mem=[[False for i in range(n)]for j in range(2)]
    mem[0][0]=True
    mem[1][0]=True
    que=[[0,0,0],[1,0,0]]
    while len(que)!=0:
        d=que.pop(0)
        state=b[d[0]][d[1]]
        if state!=2 and d[1]==n-1:
            return d[2]
            
        if state==0:
            for i in range(3):
                if d[1]+i>=n:break
                if d[0]==0 and mem[1][d[1]+i]==False:
                    que.append([1,d[1]+i,d[2]+1])
                    mem[1][d[1]+i]=True
                elif d[0]==1 and mem[0][d[1]+i]==False:
                    que.append([0,d[1]+i,d[2]+1])
                    mem[0][d[1]+i]=True
        elif state==1:
            k=1
            while True:
                if d[1]+k>=n:return d[2]
                if b[d[0]][d[1]+k]!=1:
                    for i in range(3):
                        if d[1]+k+i-1>=n:break
                        if d[0]==0 and mem[1][d[1]+k+i-1]==False:
                            que.append([1,d[1]+k+i-1,d[2]+1])
                            mem[1][d[1]+k+i-1]=True
                        elif d[0]==1 and mem[0][d[1]+k+i-1]==False:
                            que.append([0,d[1]+k+i-1,d[2]+1])
                            mem[0][d[1]+k+i-1]=True
                    break
                else: k+=1

        elif state==2:
            k=1
            while True:
                if b[d[0]][d[1]-k]!=2:
                    for i in range(3):
                        if d[1]-k+i>=n:break
                        if d[0]==0 and mem[1][d[1]-k+i]==False:
                            que.append([1,d[1]-k+i,d[2]+1])
                            mem[1][d[1]-k+i]=True
                        elif d[0]==1 and mem[0][d[1]-k+i]==False:
                            que.append([0,d[1]-k+i,d[2]+1])
                            mem[0][d[1]-k+i]=True
                    break
                else:k+=1  
    return 0
while True:
#for t in range(1):
    n=int(input())
    #n=8
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    #b=[[0,0,0,2,2,2,0,0],[1,1,1,1,0,0,0,0]]
    count=bfs(b)
    print(str(count)if count!=0 else "NA")

Submission status: Wrong Answer

Solution code:
def bfs(b):
    mem=[[False for i in range(n)]for j in range(2)]
    st=[0,0]
    for i in range(2):
        while st[i]<n-1 and b[i][st[i]+1]==1:
            st[i]+=1
        if st[i]==n-1:return 0
    mem[0][st[0]]=True
    mem[1][st[1]]=True
    que=[[0,st[0],0],[1,st[1],0]]
    while len(que)!=0:
        d=que.pop(0)
        des=(d[0]+1)%2
        cst=d[2]+1
        for i in range(3):
            fl=d[1]+i
            if fl>=n:break
            state=b[des][fl]
            if state!=2 and fl==n-1:
                return cst
            if state==0:
                if mem[des][fl]==False:
                    que.append([des,fl,cst])
                    mem[des][fl]=True
            elif state==1:
                k=1
                while True:
                    if fl+k>=n:return cst
                    if b[des][fl+k]!=1:
                        if mem[des][fl+k-1]==False:
                            que.append([des,fl+k-1,cst])
                            mem[des][fl+k-1]=True
                        break
                    else: k+=1

            elif state==2:
                k=1
                while True:
                    if b[des][fl-k]!=2:
                        if mem[des][fl-k]==False:
                            que.append([des,fl-k,cst])
                            mem[des][fl-k]=True
                        break
                    else:k+=1  
    return -1
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    count=bfs(b)
    print(str(count)if count>=0 else "NA")

Submission status: Wrong Answer

Solution code:
from collections import deque

def fix(alst, blst, floar, buil, n):
  if buil == 0:
    lst = alst
  else:
    lst = blst
  
  if lst[floar] == 0:
    return floar
  if lst[floar] == 1:
    while floar + 1 < n and lst[floar + 1] == 1:
      floar += 1
    return floar
  if lst[floar] == 2:
    while lst[floar] == 2:
      floar -= 1
    return floar 

def search(alst, blst, n):
  que = deque()
  #(cost, floar, buil)
  que.append((0, 0, 0))
  que.append((0, 0, 1))
  dic = {}
  dic[(0, 0)] = 0
  dic[(0, 1)] = 0
  while que:
    total, floar, buil = que.popleft()
    next_buil = (buil + 1) % 2
    for i in range(min(3, n - floar)):
      to = fix(alst, blst, floar + i, next_buil, n)
      if to == n - 1:
        print(total + 1)
        return
      if (to, next_buil) not in dic:
        dic[(to, next_buil)] = total + 1
        que.append((total + 1, to, next_buil))
  print("NA")


while True:
  n = int(input())
  if n == 0:
    break
  alst = list(map(int, input().split()))
  blst = list(map(int, input().split()))
  search(alst, blst, n)

Submission status: Wrong Answer

Solution code:
from collections import deque

def fix(alst, blst, floar, buil, n):
  if buil == 0:
    lst = alst
  else:
    lst = blst
  
  if lst[floar] == 0:
    return floar
  if lst[floar] == 1:
    while floar + 1 < n and lst[floar + 1] == 1:
      floar += 1
    return floar
  if lst[floar] == 2:
    while lst[floar] == 2:
      floar -= 1
    return floar 

def search(alst, blst, n):
  que = deque()
  #(cost, floar, buil)
  init_floar_a = fix(alst, blst, 0, 0, n)
  init_floar_b = fix(alst, blst, 0, 1, n)
  que.append((0, init_floar_a, 0))
  que.append((0, init_floar_b, 1))
  dic = {}
  dic[(0, init_floar_a)] = 0
  dic[(0, init_floar_b)] = 0
  while que:
    total, floar, buil = que.popleft()
    next_buil = (buil + 1) % 2
    for i in range(min(3, n - floar)):
      to = fix(alst, blst, floar + i, next_buil, n)
      if to == n - 1:
        print(total + 1)
        return
      if (to, next_buil) not in dic:
        dic[(to, next_buil)] = total + 1
        que.append((total + 1, to, next_buil))
  print("NA")


while True:
  n = int(input())
  if n == 0:
    break
  alst = list(map(int, input().split()))
  blst = list(map(int, input().split()))
  search(alst, blst, n)

Submission status: Wrong Answer

Solution code:
from collections import deque

def fix(alst, blst, floar, buil, n):
  if buil == 0:
    lst = alst
  else:
    lst = blst
  
  if lst[floar] == 0:
    return floar
  if lst[floar] == 1:
    while floar + 1 < n and lst[floar + 1] == 1:
      floar += 1
    return floar
  if lst[floar] == 2:
    while lst[floar] == 2:
      floar -= 1
    return floar 

def search(alst, blst, n):
  que = deque()
  #(cost, floar, buil)
  init_floar_a = fix(alst, blst, 0, 0, n)
  init_floar_b = fix(alst, blst, 0, 1, n)
  que.append((0, init_floar_a, 0))
  que.append((0, init_floar_b, 1))
  dic = {}
  dic[(0, init_floar_a)] = 0
  dic[(0, init_floar_b)] = 0
  while que:
    total, floar, buil = que.popleft()
    next_buil = (buil + 1) % 2
    for i in range(3):
      if floar + i >= n:
        break
      to = fix(alst, blst, floar + i, next_buil, n)
      if to == n - 1:
        print(total + 1)
        return
      if (to, next_buil) not in dic:
        dic[(to, next_buil)] = total + 1
        que.append((total + 1, to, next_buil))
  print("NA")


while True:
  n = int(input())
  if n == 0:
    break
  alst = list(map(int, input().split()))
  blst = list(map(int, input().split()))
  search(alst, blst, n)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(bldg):
    dict = {}
    
    que = deque([(bldg[0][0],0,0),(bldg[1][0],1,0)])

    while len(que):
        h, b, t = que.popleft()
        try:
            if dict[(h, b)] <= t:
                continue
        except KeyError:
            dict[(h, b)] = t
        
        if h == len(bldg[0]) - 3:
            return t
        t += 1
        if 100 < t:
            break
        que.append((bldg[b^1][h + 2],b^1,t))
    return 'NA'

def building():
    bldg = f.readline().split() + ['2', '2']    
    
    scaffold = 0    
    for i in range(len(bldg)):
        if '2' == bldg[i]:
            bldg[i] = scaffold
        else:
            scaffold = i
        if '0' == bldg[i]:
            bldg[i] = i

    scaffold = None
    for i in reversed(range(len(bldg))):
        if '1' == bldg[i]:
            if scaffold is None:
                scaffold = i
            bldg[i] = scaffold
        else:
            scaffold = None
    return bldg

import sys
f = sys.stdin


while True:
    n = int(f.readline())
    if n == 0:
        break
    print(bfs([building(),building()]))

Submission status: Accepted

Solution code:
import Queue
while True:
    n = input()
    if n==0:
        break
    a = []
    nxt = [range(n) for i in xrange(2)]
    for i in xrange(2):
        a.append(map(int, raw_input().split()))
    for i in xrange(2):
        back = 0
        for j in xrange(n):
            if a[i][j]==2:
                nxt[i][j] = back
            else:
                back = j
        forw = n-1
        for j in xrange(n-1,-1,-1):
            if a[i][j]==1:
                nxt[i][j] = forw
            else:
                forw = j-1
    cost = [[10**9] * n for i in xrange(2)]
    que = Queue.PriorityQueue()
    cost[0][nxt[0][0]] = 0
    cost[1][nxt[1][0]] = 0
    que.put((0, 0, nxt[0][0]))
    que.put((0, 1, nxt[1][0]))
    ans = -1
    while not que.empty():
        co, sd, st = que.get()
        if st==n-1:
            ans = co
            break
        if cost[sd][st] < co:
            continue
        for i in xrange(3 if st+2<n else 2):
            step = nxt[sd^1][st+i]
            if co+1 < cost[sd^1][step]:
                cost[sd^1][step] = co+1
                que.put((co+1, sd^1, step))
    print "NA" if ans==-1 else ans

Submission status: Accepted

Solution code:
def bfs(b):
    mem=[[False for i in range(n)]for j in range(2)]
    st=[0,0]
    for i in range(2):
        if b[i][0]!=1:continue
        while st[i]<n-1 and b[i][st[i]+1]==1:
            st[i]+=1
        if st[i]==n-1:return 0
    mem[0][st[0]]=True
    mem[1][st[1]]=True
    que=[[0,st[0],0],[1,st[1],0]]
    while len(que)!=0:
        d=que.pop(0)
        des=(d[0]+1)%2
        cst=d[2]+1
        for i in range(3):
            fl=d[1]+i
            if fl>=n:break
            state=b[des][fl]
            if state!=2 and fl==n-1:
                return cst
            if state==0:
                if mem[des][fl]==False:
                    que.append([des,fl,cst])
                    mem[des][fl]=True
            elif state==1:
                k=1
                while True:
                    if fl+k>=n:return cst
                    if b[des][fl+k]!=1:
                        if mem[des][fl+k-1]==False:
                            que.append([des,fl+k-1,cst])
                            mem[des][fl+k-1]=True
                        break
                    else: k+=1

            elif state==2:
                k=1
                while True:
                    if b[des][fl-k]!=2:
                        if mem[des][fl-k]==False:
                            que.append([des,fl-k,cst])
                            mem[des][fl-k]=True
                        break
                    else:k+=1  
    return -1
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    count=bfs(b)
    print(str(count)if count>=0 else "NA")

Submission status: Accepted

Solution code:
from collections import deque

def fix(alst, blst, floar, buil, n):
  if buil == 0:
    lst = alst
  else:
    lst = blst
  
  if lst[floar] == 0:
    return floar
  if lst[floar] == 1:
    while floar + 1 < n and lst[floar + 1] == 1:
      floar += 1
    return floar
  if lst[floar] == 2:
    while lst[floar] == 2:
      floar -= 1
    return floar 

def search(alst, blst, n):
  que = deque()
  #(cost, floar, buil)
  init_floar_a = fix(alst, blst, 0, 0, n)
  init_floar_b = fix(alst, blst, 0, 1, n)
  if n - 1 in (init_floar_a, init_floar_b):
    print(0)
    return
  que.append((0, init_floar_a, 0))
  que.append((0, init_floar_b, 1))
  dic = {}
  dic[(0, init_floar_a)] = 0
  dic[(0, init_floar_b)] = 0
  while que:
    total, floar, buil = que.popleft()
    next_buil = (buil + 1) % 2
    for i in range(3):
      if floar + i >= n:
        break
      to = fix(alst, blst, floar + i, next_buil, n)
      if to == n - 1:
        print(total + 1)
        return
      if (to, next_buil) not in dic:
        dic[(to, next_buil)] = total + 1
        que.append((total + 1, to, next_buil))
  print("NA")


while True:
  n = int(input())
  if n == 0:
    break
  alst = list(map(int, input().split()))
  blst = list(map(int, input().split()))
  search(alst, blst, n)

Submission status: Runtime Error

Solution code:
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    mem=[[1145141919 for i in range(n)]for j in range(2)]
    mem[1][0]=True
    que=[[0,0,0],[1,0,0]]
    count=1145141919
    while len(que)!=0:
        d=que.pop(0)
        state=b[d[0]][d[1]]
        if state!=2 and d[1]==n-1 and d[2]<count:
            count=d[2]
        mem[d[0]][d[1]]=d[2]
        case=-1
        if state==0:case=0
        elif state==1:
            if b[d[0]][d[1]+1]==1:case=1
            else:case=0
        elif state==2:case=2

        if case==0:
            for i in range(3):
                if d[1]+i>=n:break
                if d[0]==0 and mem[1][d[1]+i]>d[2]+1:que.append([1,d[1]+i,d[2]+1])
                elif d[0]==1 and mem[0][d[1]+i]>d[2]+1:que.append([0,d[1]+i,d[2]+1])
        elif case==1:
            if mem[d[0]][d[1]+1]>d[2]:que.append([d[0],d[1]+1,d[2]])
        elif case==2:
            if mem[d[0]][d[1]-1]>d[2]:que.append([d[0],d[1]-1,d[2]])
    print(str(count)if count!=1145141919 else "NA")

Submission status: Runtime Error

Solution code:
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    mem=[[1145141919 for i in range(n)]for j in range(2)]
    que=[[0,0,0],[1,0,0]]
    count=1145141919
    while len(que)!=0:
        d=que.pop(0)
        state=b[d[0]][d[1]]
        if state!=2 and d[1]==n-1 and d[2]<count:
            count=d[2]
        mem[d[0]][d[1]]=d[2]
        case=-1
        if state==0:case=0
        elif state==1:
            if b[d[0]][d[1]+1]==1:case=1
            else:case=0
        elif state==2:case=2

        if case==0:
            for i in range(3):
                if d[1]+i>=n:break
                if d[0]==0 and mem[1][d[1]+i]>d[2]+1:que.append([1,d[1]+i,d[2]+1])
                elif d[0]==1 and mem[0][d[1]+i]>d[2]+1:que.append([0,d[1]+i,d[2]+1])
        elif case==1:
            if mem[d[0]][d[1]+1]>d[2]:que.append([d[0],d[1]+1,d[2]])
        elif case==2:
            if mem[d[0]][d[1]-1]>d[2]:que.append([d[0],d[1]-1,d[2]])
    print(str(count)if count!=1145141919 else "NA")

Submission status: Runtime Error

Solution code:
while True:
#for t in range(1):
    n=int(input())
    #n=8
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    #b=[[0,0,0,2,2,2,0,0],[1,1,1,1,0,0,0,0]]
    mem=[[False for i in range(n)]for j in range(2)]
    mem[0][0]=True
    mem[1][0]=True
    que=[[0,0,0],[1,0,0]]
    count=0
    while len(que)!=0:
        d=que.pop(0)
        state=b[d[0]][d[1]]
        if state!=2 and d[1]==n-1:
            count=d[2]
            break
        if state==0:
            for i in range(3):
                if d[1]+i>=n:break
                if d[0]==0 and mem[1][d[1]+i]==False:
                    que.append([1,d[1]+i,d[2]+1])
                    mem[1][d[1]+i]=True
                elif d[0]==1 and mem[0][d[1]+i]==False:
                    que.append([0,d[1]+i,d[2]+1])
                    mem[0][d[1]+i]=True
        elif state==1:
            k=1
            while True:
                if b[d[0]][d[1]+k]!=1:
                    for i in range(3):
                        if d[1]+k+i-1>=n:break
                        if d[0]==0 and mem[1][d[1]+k+i-1]==False:
                            que.append([1,d[1]+k+i-1,d[2]+1])
                            mem[1][d[1]+k+i-1]=True
                        elif d[0]==1 and mem[0][d[1]+k+i-1]==False:
                            que.append([0,d[1]+k+i-1,d[2]+1])
                            mem[0][d[1]+k+i-1]=True
                    break
                else: k+=1

        elif state==2:
            k=1
            while True:
                if b[d[0]][d[1]-k]!=2:
                    for i in range(3):
                        if d[1]-k+i>=n:break
                        if d[0]==0 and mem[1][d[1]-k+i]==False:
                            que.append([1,d[1]-k+i,d[2]+1])
                            mem[1][d[1]-k+i]=True
                        elif d[0]==1 and mem[0][d[1]-k+i]==False:
                            que.append([0,d[1]-k+i,d[2]+1])
                            mem[0][d[1]-k+i]=True
                    break
                else:k+=1
       
    print(str(count)if count!=0 else "NA")

Submission status: Runtime Error

Solution code:
def bfs(b):
    mem=[[False for i in range(n)]for j in range(2)]
    st=[0,0]
    for i in range(2):
        while b[i][st[i]+1]==1:
            st[i]+=1
    mem[0][st[0]]=True
    mem[1][st[1]]=True
    que=[[0,0,0],[1,0,0]]
    while len(que)!=0:
        d=que.pop(0)
        des=(d[0]+1)%2
        cst=d[2]+1
        for i in range(3):
            fl=d[1]+i
            if fl>n:break
            state=b[des][fl]
            if state!=2 and fl==n-1:
                return cst
            if state==0:
                if mem[des][fl]==False:
                    que.append([des,fl,cst])
                    mem[des][fl]=True
            elif state==1:
                k=1
                while True:
                    if fl+k>=n:return cst
                    if b[des][fl+k]!=1:
                        if mem[des][fl+k-1]==False:
                            que.append([des,fl+k-1,cst])
                            mem[des][fl+k-1]=True
                        break
                    else: k+=1

            elif state==2:
                k=1
                while True:
                    if b[des][fl-k]!=2:
                        if mem[des][fl-k]==False:
                            que.append([des,fl-k,cst])
                            mem[des][fl-k]=True
                        break
                    else:k+=1  
    return 0
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    count=bfs(b)
    print(str(count)if count!=0 else "NA")