Problem:


ぴょん吉の夏

 会津大学には一面芝生で覆われた公園があり、日差しを遮る木や建物がありません。日差しの強い夏の日には、公園内に設置されたスプリンクラーが作動して芝生に散水しています。この公園にはカエルのぴょん吉が住み着いています。ぴょん吉は暑いのが苦手で、日差しが強い夏の日には常にスプリンクラーの水に当たっていないと干からびて死んでしまいます。公園に設置されたスプリンクラーは、節水のため一度に一つだけ散水することになっているので、ぴょん吉はスプリンクラーの作動に合わせて移動しなくてはなりません。

(a) 公園の地図

(b) ぴょん吉のジャンプ範囲 
(c) スプリンクラーの散水範囲

 公園は上図の(a)のとおりで、公園内の場所は縦横それぞれ 0~9 の座標で表し、黒い●がスプリンクラーで、その番号が作動する順番を表しています。これは一例で各スプリンクラーの場所と作動順序は日々変わります。

ぴょん吉は不器用なので、移動するにも決まった距離をジャンプすることしかできません。ぴょん吉のジャンプできる範囲は上図(b)のとおりで、それ以外の場所に移動することはできません。しかも、一回のジャンプで相当体力を消耗するため、しばらく水に当たって休まなくてはなりません。

スプリンクラーが散水できる範囲は上図(c)のとおりで、スプリンクラー自身の座標も含みます。各スプリンクラーは一定時間散水すると停止し、すぐに次のスプリンクラーが作動を開始します。ぴょん吉はこの時に一回だけジャンプするものとし、次に散水が停止するまでジャンプしないものとします。また、公園の四方は灼熱のアスファルトで囲まれているので公園の外にでてしまうような方向にはジャンプしないものとします。

 猛暑となったこの夏。果たしてぴょん吉は生き延びることができたのでしょうか? ある日のぴょん吉の初期位置、スプリンクラーの位置と作動順序を読み込み、ぴょん吉が生き延びられる移動経路が存在している場合は”OK”、どう頑張っても死んでしまう場合は”NA”を出力するプログラムを作成してください。ただし、スプリンクラーの数は最大 10 個とし、ぴょん吉は一番目のスプリンクラーの作動と同時に初期位置からジャンプすることとします。

Input

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

px py
n
x1 y1 x2 y2 ... xn yn

1 行目にぴょん吉の初期位置の横座標 px と縦座標 py が与えられます。
2 行目にスプリンクラーの数 n が与えられます。
3 行目に i 番目に動作するスプリンクラーの横座標 xi と縦座標 yi が与えられます。

入力はゼロ２つの行で終わります。データセットの数は 20 を超えません。

Output

各データセットについて、生存の場合は OK、そうでない場合は NA を１行に出力してください。

Sample Input

6 1
10
6 4 3 3 1 2 0 5 4 6 1 8 5 9 7 7 8 6 8 3
6 1
10
6 4 3 3 1 2 0 5 4 6 1 8 5 9 7 7 8 6 9 0
0 0

Output for the Sample Input

OK
NA



Sample input:
6 1
10
6 4 3 3 1 2 0 5 4 6 1 8 5 9 7 7 8 6 8 3
6 1
10
6 4 3 3 1 2 0 5 4 6 1 8 5 9 7 7 8 6 9 0
0 0


Sample output:
OK
NA

Submission status: Accepted

Solution code:
from collections import deque
 
jumps = [
    [1, -2], [0, -2], [-1, -2], [-2, -1], [-2, 0], [-2, 1], [-1, 2], [0, 2], [1, 2], [2, -1], [2, 0], [2, 1]
]
 
def bfs(ipy, ipx, ys, xs, n):
    q = deque()
    q.append([ipy, ipx, -1])
    while q:
        py, px, t = q.popleft()
        if t == n-1:
            return True
 
        for dy, dx in jumps:
            npy = py + dy
            npx = px + dx
            if npy in range(10) and npx in range(10) and abs(npy - ys[t+1]) <= 1 and abs(npx - xs[t+1]) <= 1:
                q.append([npy, npx, t+1])
 
    return False
 
if __name__ == '__main__':
    while True:
        try:
            ipx, ipy = map(int, input().split())
            if ipx == 0 and ipy == 0:
                break
            n = int(input())
            l = list(map(int, input().split()))
            xs = l[::2]
            ys = l[1::2]
             
            if bfs(ipy, ipx, ys, xs, n):
                print('OK')
            else:
                print('NA')
        except:
            break

Submission status: Accepted

Solution code:
class Vector2:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector2(self.x + other.x, self.y + other.y)

    def __hash__(self):
        return self.x * 10 + self.y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y


def create_water_range():
    l = []

    for item in [-1, 0, 1]:
        for item2 in [-1, 0, 1]:
            l.append(Vector2(item, item2))

    return l


def create_jump_range():
    l = []

    for item in [-2, 2]:
        for item2 in [-1, 0, 1]:
            l.append(Vector2(item, item2))
            l.append(Vector2(item2, item))

    return l


WATER_RANGE = create_water_range()
JUMP_RANGE = create_jump_range()


def is_live(water_count, point, LIMIT, WATER_POINT_LIST):
    if LIMIT <= water_count:
        return True

    center = WATER_POINT_LIST[water_count]

    water_point_set = set(center + water for water in WATER_RANGE)

    for jump in JUMP_RANGE:
        new_point = point + jump

        if 0 <= new_point.x <= 9 and 0 <= new_point.y <= 9:
            if new_point in water_point_set:
                result = is_live(water_count + 1, new_point, LIMIT, WATER_POINT_LIST)

                if result:
                    return result

    return False


while True:
    x, y = [int(item) for item in input().split(" ")]

    if x == 0 and y == 0:
        break

    my_point = Vector2(x, y)

    water_count = int(input())
    point_list = [int(item) for item in input().split(" ")]

    water_point_list = []

    for x, y in zip(point_list[::2], point_list[1::2]):
        water_point_list.append(Vector2(x, y))

    result = is_live(0, my_point, water_count, water_point_list)

    if result:
        print("OK")
    else:
        print("NA")

Submission status: Accepted

Solution code:
def search(table, x, y, depth, max_depth):

    if depth == max_depth:
        return True

    if x < 0 or x >= 10 or y < 0 or y >= 10:
        return False

    if depth >= 0 and table[x][y][depth] == 0:
        return False

    if search(table, x-2, y-1, depth+1, max_depth):
        return True
    if search(table, x-2, y, depth+1, max_depth):
        return True
    if search(table, x-2, y+1, depth+1, max_depth):
        return True

    if search(table, x-1, y-2, depth+1, max_depth):
        return True
    if search(table, x, y-2, depth+1, max_depth):
        return True
    if search(table, x+1, y-2, depth+1, max_depth):
        return True

    if search(table, x+2, y-1, depth+1, max_depth):
        return True
    if search(table, x+2, y, depth+1, max_depth):
        return True
    if search(table, x+2, y+1, depth+1, max_depth):
        return True

    if search(table, x-1, y+2, depth+1, max_depth):
        return True
    if search(table, x, y+2, depth+1, max_depth):
        return True
    if search(table, x+1, y+2, depth+1, max_depth):
        return True


while True:
    px,py = [int(i) for i in input().split()]
    if px == 0 and py == 0:
        break

    table = [[[0 for i in range(10)] for j in range(10)] for k in range(10)]

    n = int(input())
    N = [int(i) for i in input().split()]
    traps = []

    for i in range(0, len(N), 2):
        x = N[i]
        y = N[i+1]
        prx = max(x-1, 0)
        pry = max(y-1, 0)
        pox = min(x+1, 9)
        poy = min(y+1, 9)

        d = int(i//2)
        table[prx][pry][d] = 1
        table[prx][y][d] = 1
        table[prx][poy][d] = 1
        table[x][pry][d] = 1
        table[x][y][d] = 1
        table[x][poy][d] = 1
        table[pox][pry][d] = 1
        table[pox][y][d] = 1
        table[pox][poy][d] = 1

    if search(table, px, py, -1, n):
        print("OK")
    else:
        print("NA")

Submission status: Accepted

Solution code:
while True:
  px, py = map(int, input().split())
  if px == 0:
    break

  n = int(input())
  pairs = list(map(int, input().split()))
  s_points = []
  for i in range(n):
    s_points.append((pairs[i * 2], pairs[i * 2 + 1]))
  
  survive_range = [(x, y) for x in (-1, 0, 1) for y in (-1, 0, 1)]
  jump_to = ((-2, -1), (-2, 0), (-2, 1), (-1, -2), (-1, 2), (0, -2), (0, 2), 
               (1, -2), (1, 2), (2, -1), (2, 0), (2, 1))

  def next_points(p):
    x, y = p
    return {(x + dx, y + dy) for dx, dy in jump_to if 0 <= x + dx <= 9 and 0 <= y + dy <= 9}

  def survive_points(p):
    x, y = p
    return {(x + dx, y + dy) for dx, dy in survive_range if 0 <= x + dx <= 9 and 0 <= y + dy <= 9}
  
  def next_survive(ps):
    ret = set()
    for p in ps:
      ret = ret | next_points(p)
    return ret

  survive ={(px, py)}
  for sp in s_points:
    i_survive = survive_points(sp)
    survive = next_survive(survive) & i_survive
  
  if survive:
    print("OK")
  else:
    print("NA")

Submission status: Accepted

Solution code:
# AOJ 0122 Summer of Pyonkichi
# Python3 2018.6.21 bal4u
# 深さ優先探索

move = [[-1, -2], [0, -2], [1, -2], \
        [2, -1], [2, 0], [2, 1], \
        [1, 2], [0, 2], [-1, 2], \
        [-2, 1], [-2, 0], [-2, -1]]

while True:
	px, py = list(map(int, input().split()))
	if px == 0 and py == 0: break
	n = int(input())
	arr = [[[0 for ___ in range(10)] for __ in range(10)] for _ in range(10)]
	xy = list(map(int, input().split()))
	for i in range(n):
		x = xy.pop(0)
		y = xy.pop(0)
		for nx in range(x-1, x+2):
			for ny in range(y-1, y+2):
				if nx >= 0 and ny >= 0 and nx <= 9 and ny <= 9: arr[i][nx][ny] = 1
	Q = []
	Q.append([px, py, 0])
	f = True
	while f and len(Q):
		x, y, k = Q.pop()
		for i in range(12):
			nx, ny = x + move[i][0], y + move[i][1]
			if nx >= 0 and ny >= 0 and nx <= 9 and ny <= 9 and arr[k][nx][ny]:
				if k+1 < n: Q.append([nx, ny, k+1])
				else:
					print("OK")
					f = False
					break
	if f: print("NA")

Submission status: Accepted

Solution code:
mv=((2,0),(2,1),(2,-1),(-2,0),(-2,1),(-2,-1),
    (0,2),(1,2),(-1,2),(0,-2),(1,-2),(-1,-2))

while True:
    x,y=map(int,raw_input().split())
    if x==y==0:break
    n=input()
    pos=map(int,raw_input().split())
    pos=[(pos[2*i],pos[2*i+1]) for i in range(n)]

    que=[(x,y,0)]
    while que!=[]:
        X,Y,p=que[0][0],que[0][1],que[0][2]
        del que[0]
        S=set()
        if p>=n:
            print "OK"
            break
        for k in range(-1,2):
            for l in range(-1,2):
                S.add((pos[p][0]+k,pos[p][1]+l,p+1))
        for dx,dy in mv:
            mx=X+dx
            my=Y+dy
            if 0<=mx<10 and 0<=my<10 and (mx,my,p+1) in S:
                que.append((mx,my,p+1))
    else:
        print "NA"

Submission status: Accepted

Solution code:
D = zip([-1,0,1,2,2,2,1,0,-1,-2,-2,-2],
        [-2,-2,-2,-1,0,1,2,2,2,1,0,-1])

def check(x,y):
    return 0<=x<=9 and 0<=y<=9

def pick(survivors,x,y):
    ret = []
    for (sx,sy) in survivors:
        if x-1<=sx<=x+1 and y-1<=sy<=y+1:
            ret.append((sx,sy))
    return ret

def move(survivors):
    tmp = []
    for (sx,sy) in survivors:
        for dx,dy in D:
            if check(sx+dx,sy+dy):
                tmp.append((sx+dx,sy+dy))
    return list(set(tmp))

while True:
    survivors = [map(int,raw_input().split())]
    if survivors == [[0,0]]:
        break
    n = input()
    pos = map(int,raw_input().split())
    for x,y in zip(pos[::2],pos[1::2]):
        survivors = pick(move(survivors),x,y)
        if len(survivors) == 0:
            print "NA"
            break
    else:
        print "OK"

Submission status: Accepted

Solution code:
dx = [2,2,2,1,0,-1,-2,-2,-2,-1,0,1]
dy = [-1,0,1,2,2,2,1,0,-1,-2,-2,-2]
def solve(x,y,XY):
	xy = XY[:]
	if len(xy) == 0: return "OK"
	sx,sy = xy.pop(0),xy.pop(0)
	for i in range(12):
		try:
			if doa(x+dx[i],y+dy[i],sx,sy): 
				r = solve(x+dx[i],y+dy[i],xy)
				if r: return r
		except:
			pass

def doa(x,y,sx,sy):
	return True if abs(x-sx) < 2 and abs(y-sy) < 2 else False

while 1:
	x,y = map(int,raw_input().split())
	if x == y == 0: break
	n = input()
	xy = map(int,raw_input().split())
	ans = solve(x,y,xy)
	print ans if ans else "NA"

Submission status: Accepted

Solution code:
dX = [2,2,2,1,0,-1,-2,-2,-2,-1,0,1]
dY = [-1,0,1,2,2,2,1,0,-1,-2,-2,-2]
def solve(x,y,XY):
	xy = XY[:]
	if len(xy) == 0: return "OK"
	sx,sy = xy.pop(0),xy.pop(0)
	for dx,dy in zip(dX,dY):
		if doa(x+dx,y+dy,sx,sy): 
			r = solve(x+dx,y+dy,xy)
			if r: return r

def doa(x,y,sx,sy):
	if not (0 <= x <= 9 and 0 <= y <= 9): return False
	return True if abs(x-sx) < 2 and abs(y-sy) < 2 else False

while 1:
	x,y = map(int,raw_input().split())
	if x == y == 0: break
	n = input()
	xy = map(int,raw_input().split())
	ans = solve(x,y,xy)
	print ans if ans else "NA"

Submission status: Accepted

Solution code:
dX = [2,2,2,1,0,-1,-2,-2,-2,-1,0,1]
dY = [-1,0,1,2,2,2,1,0,-1,-2,-2,-2]
def solve(x,y,XY):
	xy = XY[:]
	if len(xy) == 0: return True
	sx,sy = xy.pop(0),xy.pop(0)
	for dx,dy in zip(dX,dY):
		if doa(x+dx,y+dy,sx,sy): 
			r = solve(x+dx,y+dy,xy)
			if r: return r

def doa(x,y,sx,sy):
	if not (0 <= x <= 9 and 0 <= y <= 9): return False
	return True if abs(x-sx) < 2 and abs(y-sy) < 2 else False

while 1:
	x,y = map(int,raw_input().split())
	if x == y == 0: break
	n = input()
	xy = map(int,raw_input().split())
	print "OK" if solve(x,y,xy) else "NA"

Submission status: Accepted

Solution code:
dX = [2,2,2,1,0,-1,-2,-2,-2,-1,0,1]
dY = [-1,0,1,2,2,2,1,0,-1,-2,-2,-2]
def solve(x,y,i):
	if i == 2*n: return True
	sx,sy = xy[i],xy[i+1]
	for dx,dy in zip(dX,dY):
		if doa(x+dx,y+dy,sx,sy): 
			r = solve(x+dx,y+dy,i+2)
			if r: return r

def doa(x,y,sx,sy):
	if not (0 <= x <= 9 and 0 <= y <= 9): return False
	return True if abs(x-sx) < 2 and abs(y-sy) < 2 else False

while 1:
	x,y = map(int,raw_input().split())
	if x == y == 0: break
	n = input()
	xy = map(int,raw_input().split())
	print "OK" if solve(x,y,0) else "NA"

Submission status: Accepted

Solution code:
def solve():
    px, py = map(int, input().split())
    if px == 0:
        return False
    N = int(input())
    *vs, = map(int, input().split())
    P = []
    for i in range(N):
        x, y = vs[2*i:2*i+2]
        P.append((x-1, y-1))
    W = H = 10
    dd = ((-2, 1), (-2, 0), (-2, -1), (-1, -2), (0, -2), (1, -2), (2, -1), (2, 0), (2, 1), (1, 2), (0, 2), (-1, 2))
    memo = {}
    def dfs(i, x, y):
        key = (i, x, y)
        if key in memo:
            return memo[key]
        if i == N:
            return 1
        x0, y0 = P[i]
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if not 0 <= nx < W or not 0 <= ny < H:
                continue
            if -1 <= x0 - nx <= 1 and -1 <= y0 - ny <= 1:
                if dfs(i+1, nx, ny):
                    return 1
        memo[key] = 0
        return 0
    print("OK" if dfs(0, px-1, py-1) else "NA")
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
def pyon(point,count,n,box,M):
    count +=1
    adress=[]
    for xx,yy in ((1,1),(1,0),(1,-1),(0,1),(0,0),(0,-1),(-1,1),(-1,0),(-1,-1)):box[M[count-1][1]+yy][M[count-1][0]+xx]=count
    for py,px in point:
        for xx,yy in ((2,1),(2,0),(2,-1),(-1,2),(0,2),(1,2),(-2,1),(-2,0),(-2,-1),(1,-2),(0,-2),(-1,-2)):
            if box[py+yy][px+xx]==count and (py+yy,px+xx) not in adress:adress.append((py+yy,px+xx))
    if count==n and len(adress)!=0:return "OK"
    elif len(adress)==0:return "NA"
    else:return pyon(adress,count,n,box,M)
    
while 1:
    px,py=map(int,input().split())
    if px==0:break
    point=[(py+2,px+2)]
    box=[[0]*14 for i in range(14)]
    n=int(input())
    N=list(map(int,input().split()))
    count=1
    M=[]
    for i in range(0, len(N), 2):M.append((N[i]+2,N[i+1]+2))
    print(pyon(point,0,n,box,M))

Submission status: Runtime Error

Solution code:
def check(here, count):
	return ((abs(here[0]-s[count][0]))**2 + (abs(here[1]-s[count][1]))**2 <= 2)
		
def dfs(here, count):
	if count == 10:
		result = True
	else:
		result = False
		for dx, dy in delta:
			next = (here[0]+dx,here[1]+dy)
			if lb[0] <= next[0] <= ub[0] and lb[1] <= next[1] <= ub[1] and check(next, count):
				result |= dfs(next, count+1)
	return result
delta = ((2, 0), (2, 1), (2, -1), (0, 2), (1, 2), (-1, 2), 
	(-2, 0), (-2, 1), (-2, -1), (0, -2), (1, -2), (-1, -2)) 

lb = (0,0)
ub = (9,9)
while 1:
	here = map(int,raw_input().split(" "))
	if here == [0,0]:
		break
	n = int(raw_input())
	s = map(int,raw_input().split(" "))
	s = [(s[i*2],s[i*2+1]) for i in range(n)]
	if dfs(here, 0):
		print "OK"
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
import sys
def check(here, count):
	return ((abs(here[0]-s[count][0]))**2 + (abs(here[1]-s[count][1]))**2 <= 2)
		
def dfs(here, count):
	if count == 10:
		result = True
	else:
		result = False
		for dx, dy in delta:
			next = (here[0]+dx,here[1]+dy)
			if lb[0] <= next[0] <= ub[0] and lb[1] <= next[1] <= ub[1] and check(next, count):
				result |= dfs(next, count+1)
	return result
delta = ((2, 0), (2, 1), (2, -1), (0, 2), (1, 2), (-1, 2), 
	(-2, 0), (-2, 1), (-2, -1), (0, -2), (1, -2), (-1, -2)) 

sys.setrecursionlimit = 1000000
lb = (0,0)
ub = (9,9)
while 1:
	here = map(int,raw_input().split(" "))
	if here == [0,0]:
		break
	n = int(raw_input())
	s = map(int,raw_input().split(" "))
	s = [(s[i*2],s[i*2+1]) for i in range(n)]
	if dfs(here, 0):
		print "OK"
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
def phyonkichi(p, n):
    yoko = 0
    tate = 1
    s = dic[n]
    p_lis = [(p[yoko]+a[yoko], p[tate]+a[tate]) for a in jump]
    s_lis = [(s[yoko]+a[yoko], s[tate]+a[tate]) for a in sprinkler]
    c_lis = []
    for v in list(set(p_lis) & set(s_lis)):
        if 0 <= v[yoko] <= 9 and 0 <= v[tate] <= 9:
            c_lis.append(v)
            
    if n == N:
        if c_lis:
            print 'OK'
            return True
        else:
            return
            
    for v in c_lis:
        if phyonkichi(v, n+1): return True
        
        
jump = [(2,-1),(2,0),(2,1),
        (-1,-2),(0,-2),(1,-2),
        (-2,1),(-2,0),(-2,-1),
        (-1,2),(0,2),(1,2)]

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

while True:
    w, h = map(int, raw_input().split(' '))
    if w == 0 and h == 0: break
    N = int(raw_input())
    lis = raw_input().split(' ')
    c_lis = [lis[i:i+2] for i in range(0, 20, 2)]
    dic = {}
    for i, c in enumerate(c_lis):
        dic[i+1] = (int(c[0]), int(c[1]))
    else:
        if not phyonkichi((w, h), 1):
            print 'NA'

Submission status: Runtime Error

Solution code:
def phyonkichi(p, n):
    yoko = 0
    tate = 1
    s = dic[n]
    p_lis = [(p[yoko]+a[yoko], p[tate]+a[tate]) for a in jump]
    s_lis = [(s[yoko]+a[yoko], s[tate]+a[tate]) for a in sprinkler]
    c_lis = []
    for v in list(set(p_lis) & set(s_lis)):
        if 0 <= v[yoko] <= 9 and 0 <= v[tate] <= 9:
            c_lis.append(v)
    else:
        if not c_lis:
            return
            
    if n == N:
        print 'YES'
        return True
            
    for v in c_lis:
        if phyonkichi(v, n+1): return True
        
        
jump = [(2,-1),(2,0),(2,1),
        (-1,-2),(0,-2),(1,-2),
        (-2,1),(-2,0),(-2,-1),
        (-1,2),(0,2),(1,2)]

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

while True:
    w, h = map(int, raw_input().split(' '))
    if w == 0 and h == 0: break
    N = int(raw_input())
    lis = raw_input().split(' ')
    c_lis = [lis[i:i+2] for i in range(0, 20, 2)]
    dic = {}
    for i, c in enumerate(c_lis):
        dic[i+1] = (int(c[0]), int(c[1]))
    else:
        if not phyonkichi((w, h), 1):
            print 'NA'

Submission status: Runtime Error

Solution code:
def phyonkichi(p, n):
    yoko = 0
    tate = 1
    if n[-1] == '0':
        n = 10
    else:
        n = int(n[-1])
    s = dic[n]
    p_lis = [(p[yoko]+a[yoko], p[tate]+a[tate]) for a in jump]
    s_lis = [(s[yoko]+a[yoko], s[tate]+a[tate]) for a in sprinkler]
    c_lis = []
    for v in list(set(p_lis) & set(s_lis)):
        if 0 <= v[yoko] <= 9 and 0 <= v[tate] <= 9:
            c_lis.append(v)
    else:
        if not c_lis:
            return
            
    for v in c_lis:
        if not v in res:
            res.append(v)
            if phyonkichi(v, str(n+1)): return True
            del res[-1]
        else:
            print v, res
            print 'OK'
            return True
        
        
jump = [(2,-1),(2,0),(2,1),
        (-1,-2),(0,-2),(1,-2),
        (-2,1),(-2,0),(-2,-1),
        (-1,2),(0,2),(1,2)]

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

while True:
    w, h = map(int, raw_input().split(' '))
    if w == 0 and h == 0: break
    N = int(raw_input())
    lis = raw_input().split(' ')
    c_lis = [lis[i:i+2] for i in range(0, 20, 2)]
    dic = {}
    res = []
    for i, c in enumerate(c_lis):
        dic[i+1] = (int(c[0]), int(c[1]))
    else:
        if not phyonkichi((w, h), '1'):
            print 'NA'

Submission status: Runtime Error

Solution code:
import queue
import copy

def makeList(splist,n):
    for i in range(n):
        springs=[]
        springs.append(splist[i*2:i*2+2])
        springs.append(i)
        yield springs

def isSafe(wfs,safe):
    while not wfs.empty():
        flog=wfs.get()
        flogArea=[]
        spn=flog[1]+1

        for i in range(-1,2):
            for j in [-2,2]:
                dx=flog[0][0]+j
                dy=flog[0][1]+i
                if dx>=0 and dx<10 and dy>=0 and dy<10:
                    flogArea.append([[dx,dy],spn])
        for j in range(-1,2):
            for i in [-2,2]:
                dx=flog[0][0]+j
                dy=flog[0][1]+i
                if dx>=0 and dx<10 and dy>=0 and dy<10:
                    flogArea.append([[dx,dy],spn])
        
        for i in range(len(safe[spn])):
            if safe[spn][i] in flogArea:
                if spn==9:
                    return True
                if spn<9:
                    wfs.put(safe[spn][i])
    return False

while True:
    fx,fy=map(int,input().split())
    if fx==0 and fy==0:
        break
    n=int(input())
    splist=list(map(int,input().split()))
    safe=[]
    k=makeList(splist,n)
    for spring in k:
        temp=[]
        for i in range(-1,2):
            for j in range(-1,2):
                dw=spring[0][0]+i
                dh=spring[0][1]+j
                if dw>=0 and dw<10 and dh>=0 and dh<10:
                    temp.append([[dw,dh],spring[1]])
        safe.append(temp)

    wfs=queue.Queue()
    first=[[fx,fy],-1]
    wfs.put(first)

    if isSafe(wfs,safe):
        print("OK")
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
import collectoins

Submission status: Runtime Error

Solution code:
from collections import deque
import copy

def makeList(splist,n):
    for i in range(n):
        springs=[]
        springs.append(splist[i*2:i*2+2])
        springs.append(i)
        yield springs

def isSafe(wfs,safe):
    while len(wfs)>0:
        flog=wfs.popleft()
        flogArea=[]
        spn=flog[1]+1

        for i in range(-1,2):
            for j in [-2,2]:
                dx=flog[0][0]+j
                dy=flog[0][1]+i
                if dx>=0 and dx<10 and dy>=0 and dy<10:
                    flogArea.append([[dx,dy],spn])
        for j in range(-1,2):
            for i in [-2,2]:
                dx=flog[0][0]+j
                dy=flog[0][1]+i
                if dx>=0 and dx<10 and dy>=0 and dy<10:
                    flogArea.append([[dx,dy],spn])
        
        for i in range(len(safe[spn])):
            if safe[spn][i] in flogArea:
                if spn==9:
                    return True
                if spn<9:
                    wfs.append(safe[spn][i])
    return False

while True:
    fx,fy=map(int,input().split())
    if fx==0 and fy==0:
        break
    n=int(input())
    splist=list(map(int,input().split()))
    safe=[]
    k=makeList(splist,n)
    for spring in k:
        temp=[]
        for i in range(-1,2):
            for j in range(-1,2):
                dw=spring[0][0]+i
                dh=spring[0][1]+j
                if dw>=0 and dw<10 and dh>=0 and dh<10:
                    temp.append([[dw,dh],spring[1]])
        safe.append(temp)

    wfs=deque()
    first=[[fx,fy],-1]
    wfs.append(first)

    if isSafe(wfs,safe):
        print("OK")
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
mv=((2,0),(2,1),(2,-1),(-2,0),(-2,1),(-2,-1),
    (0,2),(1,2),(-1,2),(0,-2),(1,-2),(-1,-2))

while True:
    x,y=map(int,raw_input().split())
    if x==y==0:break
    n=input()
    pos=map(int,raw_input().split())
    pos=[(pos[2*i],pos[2*i+1]) for i in range(n)]

    que=[(x,y,0)]
    while que!=[]:
        X,Y,p=que[0][0],que[0][1],que[0][2]
        del que[0]
        S=set()
        if p>=10:
            print "OK"
            break
        for k in range(-1,2):
            for l in range(-1,2):
                S.add((pos[p][0]+k,pos[p][1]+l,p+1))
        for dx,dy in mv:
            mx=X+dx
            my=Y+dy
            if 0<=mx<10 and 0<=my<10 and (mx,my,p+1) in S:
                que.append((mx,my,p+1))
    else:
        print "NA"