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

Solution code:
R1=range(-2,3)
R2=range(-1,2)
A1=[(x,y) for x in R1 for y in R1 if x**2+y**2<6]
A2=[(x,y) for x in R2 for y in R2]
def fi(): return map(int,raw_input().split(" "))
def f(x,y,i):
  A=[A1,A2][i>0]
  return set([(x+dx,y+dy) for dx,dy in A if 0<=x+dx<10 and 0<=y+dy<10])

while 1:
  xf,yf=fi()
  if yf==xf==0: break
  ns=input()
  tmp=fi()
  PA=zip(tmp[0::2],tmp[1::2])
  FA=set([(xf,yf)])
  for xs,ys in PA:
    SA=f(xs,ys,1)
    tmp=set([])
    for xf,yf in FA: tmp=tmp|(SA&f(xf,yf,0))
    FA=tmp
    a=len(FA)
    if a==0: break
  print ["NA","OK"][a>0]

Submission status: Wrong Answer

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 n == N:
                _n = 1
            else:
                _n = n+1
            if phyonkichi(v, str(_n)): return True
            del res[-1]
        else:
            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, 2*N, 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: Wrong Answer

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
            
    for v in c_lis:
        if not v in res:
            res.append(v)
            _n = None
            if n == N:
                _n = 1
            else:
                _n = n+1
            if phyonkichi(v, _n): return True
            del res[-1]
        else:
            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, 2*N, 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: Wrong Answer

Solution code:
def phyonkichi(p, n):
    global count
    count += 1
    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
            
    for v in c_lis:
        if not v in res:
            res.append(v)
            _n = None
            if n == N:
                _n = 1
            else:
                _n = n+1
            if phyonkichi(v, _n): return True
            del res[-1]
            count -= 1
        else:
            if count >= 10:
                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, 2*N, 2)]
    dic = {}
    res = []
    count = 0
    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: Wrong Answer

Solution code:
def phyonkichi(p, n):
    global count
    count += 1
    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
            
    for v in c_lis:
        if not v in res:
            res.append(v)
            _n = None
            if n == N:
                _n = 1
            else:
                _n = n+1
            if phyonkichi(v, _n): return True
            del res[-1]
            count -= 1
        else:
            if count >= N:
                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, 2*N, 2)]
    dic = {}
    res = []
    count = 0
    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: Wrong Answer

Solution code:
def phyonkichi(p, n):
    global count
    count += 1
    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
            
    for v in c_lis:
        if not v in res:
            res.append(v)
            _n = None
            if n == N:
                _n = 1
            else:
                _n = n+1
            if phyonkichi(v, _n): return True
            del res[-1]
            count -= 1
        else:
            if count > N:
                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, 2*N, 2)]
    dic = {}
    res = []
    count = 0
    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: Wrong Answer

Solution code:
def phyonkichi(p, n):
    global count
    count += 1
    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
            
    for v in c_lis:
        if not v in res:
            res.append(v)
            _n = None
            if n == N:
                _n = 1
            else:
                _n = n+1
            if phyonkichi(v, _n): return True
            del res[-1]
            count -= 1
        else:
            if count > N:
                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(' ')
    lis = [lis[i:i+2] for i in range(0, 2*N, 2)]
    dic = {}
    res = []
    count = 0
    for i, c in enumerate(lis):
        dic[i+1] = (int(c[0]), int(c[1]))
    else:
        if not phyonkichi((w, h), 1):
            print 'NA'

Submission status: Wrong Answer

Solution code:
import copy

Submission status: Wrong Answer

Solution code:
from collections import deque

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

Submission status: Wrong Answer

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:
    try:
        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")
    except:
        break

Submission status: Wrong Answer

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!=[] and que[0][2]<10:
        X,Y,p=que[0][0],que[0][1],que[0][2]
        del que[0]
        S=set()
        for k in range(-1,2):
            for l in range(-1,2):
                S.add((pos[i][0]+k,pos[i][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))
    if que!=[]:
        print "OK"
    else:
        print "NG"

Submission status: Accepted

Solution code:
R1=range(-2,3)
R2=range(-1,2)
A1=[(x,y) for x in R1 for y in R1 if 3<x**2+y**2<6]
A2=[(x,y) for x in R2 for y in R2]
def fi(): return map(int,raw_input().split(" "))
def f(x,y,i):
  A=[A1,A2][i>0]
  return set([(x+dx,y+dy) for dx,dy in A if 0<=x+dx<10 and 0<=y+dy<10])

while 1:
  xf,yf=fi()
  if yf==xf==0: break
  ns=input()
  tmp=fi()
  PA=zip(tmp[0::2],tmp[1::2])
  FA=set([(xf,yf)])
  for xs,ys in PA:
    SA=f(xs,ys,1)
    tmp=set([])
    for xf,yf in FA: tmp=tmp|(SA&f(xf,yf,0))
    FA=tmp
  print ["NA","OK"][len(FA)>0]

Submission status: Accepted

Solution code:
R1=range(-2,3)
R2=range(-1,2)
A1=[(x,y) for x in R1 for y in R1 if 3<x**2+y**2<6]
A2=[(x,y) for x in R2 for y in R2]
def fi(): return map(int,raw_input().split(" "))
def f(p,i):
  x,y=p
  A=[A1,A2][i>0]
  return set([(x+dx,y+dy) for dx,dy in A if 0<=x+dx<10 and 0<=y+dy<10])

while 1:
  xf,yf=fi()
  if yf==xf==0: break
  input()
  tmp=fi()
  PA=zip(tmp[0::2],tmp[1::2])
  FA=set([(xf,yf)])
  for ps in PA:
    SA=f(ps,1)
    tmp=set([])
    for pf in FA: tmp=tmp|(SA&f(pf,0))
    FA=tmp
  print ["NA","OK"][len(FA)>0]

Submission status: Accepted

Solution code:
R1=range(-2,3)
R2=range(-1,2)
A1=[(x,y) for x in R1 for y in R1 if 3<x**2+y**2<6]
A2=[(x,y) for x in R2 for y in R2]
def fi(): return map(int,raw_input().split(" "))
def f(p,i):
  x,y=p
  A=[A1,A2][i>0]
  return set([(x+dx,y+dy) for dx,dy in A if 0<=x+dx<10 and 0<=y+dy<10])

while 1:
  xf,yf=fi()
  if yf==xf==0: break
  raw_input()
  tmp=fi()
  PA=zip(tmp[0::2],tmp[1::2])
  FA=set([(xf,yf)])
  for ps in PA:
    SA=f(ps,1)
    tmp=set([])
    for pf in FA: tmp=tmp|(SA&f(pf,0))
    FA=tmp
  print ["NA","OK"][len(FA)>0]

Submission status: Accepted

Solution code:
R1=range(-2,3)
R2=range(-1,2)
A1=[(x,y) for x in R1 for y in R1 if 3<x**2+y**2<6]
A2=[(x,y) for x in R2 for y in R2]
def fi(): return map(int,raw_input().split(" "))
def f(x,y,i):
  A=[A1,A2][i>0]
  return set([(x+dx,y+dy) for dx,dy in A if 0<=x+dx<10 and 0<=y+dy<10])

while 1:
  xf,yf=fi()
  if yf==xf==0: break
  raw_input()
  tmp=fi()
  PA=zip(tmp[0::2],tmp[1::2])
  FA=set([(xf,yf)])
  for xs,ys in PA:
    SA=f(xs,ys,1)
    tmp=set([])
    for xf,yf in FA: tmp=tmp|(SA&f(xf,yf,0))
    FA=tmp
  print ["NA","OK"][len(FA)>0]

Submission status: Accepted

Solution code:
R1=range(-2,3)
R2=range(-1,2)
A1=[(x,y) for x in R1 for y in R1 if 3<x**2+y**2<6]
A2=[(x,y) for x in R2 for y in R2]
def fi(): return map(int,raw_input().split(" "))
def f(x,y,i):
  A=[A1,A2][i>0]
  return set([(x+dx,y+dy) for dx,dy in A if 0<=x+dx<10 and 0<=y+dy<10])

while 1:
  xf,yf=fi()
  if yf==xf==0: break
  n=input()
  PA=fi()
  FA=set([(xf,yf)])
  for i in range(n*2)[::2]:
    SA=f(PA[i],PA[i+1],1)
    tmp=set([])
    for xf,yf in FA: tmp=tmp|(SA&f(xf,yf,0))
    FA=tmp
  print ["NA","OK"][len(FA)>0]

Submission status: Accepted

Solution code:
import sys

def generate_frog_positions(x, y):
    positions = []
    positions.append((x - 1, y - 2))
    positions.append((x, y - 2))
    positions.append((x + 1, y - 2))
    positions.append((x + 2, y - 1))
    positions.append((x + 2, y))
    positions.append((x + 2, y + 1))
    positions.append((x - 1, y + 2))
    positions.append((x, y + 2))
    positions.append((x + 1, y + 2))
    positions.append((x - 2, y - 1))
    positions.append((x - 2, y))
    positions.append((x - 2, y + 1))
    return [(a, b) for (a, b) in positions if 0 <= a <= 9 and 0 <= b <= 9]

def is_near_sprinkler(frog, sprinkler):
    dx = frog[0] - sprinkler[0]
    dy = frog[1] - sprinkler[1]
    return -1 <= dx <= 1 and -1 <= dy <= 1

while True:
    frog_pos = tuple([int(i) for i in sys.stdin.readline().split()])
    if frog_pos == (0, 0):
        break
    num_sprinklers = int(sys.stdin.readline())
    tmp = [int(i) for i in sys.stdin.readline().split()]
    sprinklers = zip(tmp[::2], tmp[1::2])

    positions = [frog_pos]
    for sprinkler in sprinklers:
        next_positions = []
        for pos in positions:
            next_positions += generate_frog_positions(pos[0], pos[1])
            next_positions = [pos for pos in next_positions if is_near_sprinkler(pos, sprinkler)]
        positions = next_positions
    if positions:
        print("OK")
    else:
        print("NA")

Submission status: Accepted

Solution code:
import sys

def generate_frog_positions(x, y):
    positions = [(x - 1, y - 2), (x, y - 2), (x + 1, y - 2),
                 (x + 2, y - 1), (x + 2, y), (x + 2, y + 1),
                 (x - 1, y + 2), (x, y + 2), (x + 1, y + 2),
                 (x - 2, y - 1), (x - 2, y), (x - 2, y + 1)]
    return [(a, b) for (a, b) in positions if 0 <= a <= 9 and 0 <= b <= 9]

def is_near_sprinkler(frog, sprinkler):
    dx = frog[0] - sprinkler[0]
    dy = frog[1] - sprinkler[1]
    return -1 <= dx <= 1 and -1 <= dy <= 1

while True:
    frog_pos = tuple([int(i) for i in sys.stdin.readline().split()])
    if frog_pos == (0, 0):
        break
    num_sprinklers = int(sys.stdin.readline())
    tmp = [int(i) for i in sys.stdin.readline().split()]
    sprinklers = zip(tmp[::2], tmp[1::2])

    positions = [frog_pos]
    for sprinkler in sprinklers:
        next_positions = []
        for pos in positions:
            next_positions += generate_frog_positions(pos[0], pos[1])
            next_positions = [pos for pos in next_positions if is_near_sprinkler(pos, sprinkler)]
        positions = next_positions
    if positions:
        print("OK")
    else:
        print("NA")

Submission status: Accepted

Solution code:
from copy import deepcopy
def inboard(x, y):
    return 0 <= x < 10 and 0 <= y < 10
while True:
    sr, sc = map(int, raw_input().split())
    if (sr, sc) == (0, 0): break
    N = input()
    pointList = map(int, raw_input().split())
    points = []
    for i in range(0, 2*N, 2):
        points.append((pointList[i], pointList[i+1]))
    canReach = set()
    canReach.add((sr, sc))
    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)]
    for spr, spc in points:
        newset = set()
        for r, c in canReach:
            for dr, dc in jump:
                nr, nc = r + dr, c + dc
                if inboard(nr, nc) and spr-1 <= nr <= spr+1 and spc-1 <= nc <= spc+1:
                    newset.add((nr, nc))
        canReach = deepcopy(newset)
    print("OK" if len(canReach) > 0 else "NA")

Submission status: Accepted

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 == n:
		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: Accepted

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 c_lis:
        if n == N:
            print 'OK'
            return True
        else:
            for v in c_lis:
                if phyonkichi(v, n+1): return True
    else:
        return
        
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(' ')
    lis = [lis[i:i+2] for i in range(0, 2*N, 2)]
    dic = {}
    for i, c in enumerate(lis):
        dic[i+1] = (int(c[0]), int(c[1]))
    else:
        if not phyonkichi((w, h), 1):
            print '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:
# -*- coding: utf-8 -*-

import sys
import os
import math

def jump_candidate(pos):
    x = pos[0]
    y = pos[1]

    candidate_list = []

    A = []
    A.append((-2, 0))
    A.append((-2, -1))
    A.append((-2, +1))
    A.append((+2, 0))
    A.append((+2, -1))
    A.append((+2, +1))
    A.append((0, -2))
    A.append((-1, -2))
    A.append((+1, -2))
    A.append((0, +2))
    A.append((-1, +2))
    A.append((+1, +2))

    for a in A:
        next_x = x + a[0]
        next_y = y + a[1]
        if 0 <= next_x <= 9 and 0 <= next_y <= 9:
            candidate_list.append((next_x, next_y))

    return candidate_list

def in_sprinkler_range(frog_pos, sprinkler_pos):
    fx = frog_pos[0]
    fy = frog_pos[1]
    sx = sprinkler_pos[0]
    sy = sprinkler_pos[1]

    if sx - 1 <= fx <= sx + 1 and sy - 1 <= fy <= sy + 1:
        return True
    else:
        return False


for s in sys.stdin:
    px, py = map(int, s.split())

    if px == py == 0:
        break

    n = int(input())

    lst = list(map(int, input().split()))

    # solve
    survivers = [(px, py)]
    for i in range(n):
        sprinkler = (lst[2 * i], lst[2 * i + 1])

        next_survivers = []

        for surviver in survivers:
            pos_candidates = jump_candidate(surviver)

            for jump_pos in pos_candidates:
                if in_sprinkler_range(sprinkler, jump_pos):
                    next_survivers.append(jump_pos)

        survivers = next_survivers

    if len(survivers) == 0:
        print('NA')
    else:
        print('OK')

Submission status: Accepted

Solution code:
move = [[-1, 2], [0, 2], [1, 2],
        [-1, -2], [0, -2], [1, -2],
        [2, 1], [2, 0], [2, -1],
        [-2, 1], [-2, 0], [-2, -1]]

spraing_range = [[-1, 1], [0, 1], [1, 1],
                 [-1, 0], [0, 0], [1, 0],
                 [-1, -1], [0, -1], [1, -1]]


def main():
    while True:
        px, py = map(int, input().split())
        if px is 0 and py is 0:
            break

        n = int(input())
        tmp = list(map(int, input().split()))
        sprinklers_x = tmp[::2]
        sprinklers_y = tmp[1::2]

        fields = make_fields(sprinklers_x, sprinklers_y)
        if bfs(fields, px, py, n):
            print("OK")
        else:
            print("NA")


def make_fields(sprinklers_x, sprinklers_y):
    fields = []
    for x, y in zip(sprinklers_x, sprinklers_y):
        field = [[0] * 10 for _ in range(10)]
        for dx, dy in spraing_range:
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx > 9 or ny > 9:
                continue
            field[ny][nx] = 1

        fields.append(field)

    return fields


def bfs(fields, init_px, init_py, n):
    q = [[init_px, init_py, 0]]  # [px, py, count]
    while len(q) is not 0:
        px, py, count = q.pop(0)

        if count is n:
            return True

        for dx, dy in move:
            nx = px + dx
            ny = py + dy
            if nx < 0 or ny < 0 or nx > 9 or ny > 9 or \
                    fields[count][ny][nx] is 0:
                continue

            q.append([nx, ny, count + 1])

    return False


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

"""
import sys
from sys import stdin
from collections import namedtuple, deque
input = stdin.readline


def bfs(pyon, sprinklers):
    # ??´?????????????§????????????´????????§?¨??????????
    dy = [-2, -2, -2, -1,  0,  1, -1, 0, 1,  2, 2, 2]
    dx = [-1,  0,  1, -2, -2, -2,  2, 2, 2, -1, 0, 1]

    # ??????????????°???(S)??¨??´????????°???(G)?????????
    sx = pyon.x                   #  ??????????????°????????§?¨?
    sy = pyon.y
    num_sprinkler = len(sprinklers)
    jump = 0                    #  ?????£?????????????????°

    Q = deque()
    Q.append((sx, sy, jump))
    while Q:
        cx, cy, jump = Q.popleft()        #  ?????¨??°?????§?¨?
        if jump >= num_sprinkler:
            return 'OK'
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]
            #  ?§????????????§???????????? ?????? ??¢?????¢?´¢?????§???????????°??????????????§?????¢?´¢????¶???????
            if is_safe(sprinklers, jump, nx, ny):
                Q.append((nx, ny, jump + 1))
    return 'NA'


def is_safe(sprinklers, jump, nx, ny):
    if not 0 <= nx <= 9:
        return False
    if not 0 <= ny <= 9:
        return False
    sp_x = sprinklers[jump].x
    sp_y = sprinklers[jump].y
    if not sp_x - 1 <= nx <= sp_x + 1:
        return False
    if not sp_y - 1 <= ny <= sp_y + 1:
        return False
    return True


def can_survive(pyon, sprinklers):
    return bfs(pyon, sprinklers)


pos = namedtuple('pos', ['x', 'y'])
def main(args):
    while True:
        px, py = map(int, input().split())
        if px == 0 and py == 0:
            break
        pyon = pos(px, py)
        n = int(input())
        temp = [int(x) for x in input().split(' ')]
        sprinklers = []
        for i in range(n):
            sprinklers.append(pos(temp[i*2], temp[i*2+1]))

        result = can_survive(pyon, sprinklers)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

"""
import sys
from sys import stdin
from collections import namedtuple, deque
input = stdin.readline


def bfs(pyon, sprinklers):
    # ??´?????????????§????????????´????????§?¨??????????
    # ??? ?§?????????????(0, 0)??¨??????????????¢?????\???????????????
    dy = [-2, -2, -2, -1,  0,  1, -1, 0, 1,  2, 2, 2]
    dx = [-1,  0,  1, -2, -2, -2,  2, 2, 2, -1, 0, 1]

    # ??????????????°???(S)
    sx = pyon.x                 #  ??????????????°????????§?¨?
    sy = pyon.y
    num_sprinkler = len(sprinklers)
    jump = 0                    #  ?????£?????????????????°

    Q = deque()
    Q.append((sx, sy, jump))    #  ????????????????????????????????????????????°?????????????????§????????¨????????????????????????????????£?????????????¨???¶????????????
    while Q:
        cx, cy, jump = Q.popleft()        #  ?????¨??°?????§?¨?
        if jump >= num_sprinkler:         #  ???????????????????????????????????????????????????????????§?????????????????¨?????§?????????????????¶?????????????????????????????????????????????????????????OK???????
            return 'OK'
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]
            #  ?§?????????§?????????????????¨?????§????????°?????????????????¢?´¢????¶??????????????????\????????\????????????
            if is_safe(sprinklers, jump, nx, ny):
                Q.append((nx, ny, jump + 1))
    return 'NA'


def is_safe(sprinklers, jump, nx, ny):
    # ?????£????????????????????¬???????????°?????§?????????????????????????°´????±??????????????¢??????????
    if not 0 <= nx <= 9:
        return False
    if not 0 <= ny <= 9:
        return False
    sp_x = sprinklers[jump].x
    sp_y = sprinklers[jump].y
    if not sp_x - 1 <= nx <= sp_x + 1:
        return False
    if not sp_y - 1 <= ny <= sp_y + 1:
        return False
    return True


def can_survive(pyon, sprinklers):
    return bfs(pyon, sprinklers)


pos = namedtuple('pos', ['x', 'y'])
def main(args):
    while True:
        px, py = map(int, input().split()) #  ??´????????????????????????
        if px == 0 and py == 0:
            break
        pyon = pos(px, py)
        n = int(input())        #  ??????????????????????????°
        temp = [int(x) for x in input().split(' ')]
        sprinklers = []         #  ??????????????????????????§?¨?
        for i in range(n):
            sprinklers.append(pos(temp[i*2], temp[i*2+1]))

        result = can_survive(pyon, sprinklers)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])