Problem:


ブロック

 A さんの家に親戚の B 君がやってきました。彼は 3 歳でブロックが大好きです。彼が持っているブロックは図 1 のような形をしています。

図1

 B 君はボードの上にブロックを敷き詰めています。彼に「何を作っているの?」と聞くと、彼は「迷路!!」と元気よく答えました。彼の言う迷路とは、スタートからゴールまで側面が接している、同じ色のブロックだけでたどることができるブロックの配置のことだそうです。図 2 は黄色のブロックにより、左上(スタート)から右下(ゴール)へ迷路ができていることを表しています。

図2

 無邪気に遊んでいる B 君を横目に、プログラマーであるあなたは、ブロックの並びが迷路となっているかを確かめてみることにしました。

 ブロックの情報とスタート、ゴールの座標を入力とし、ブロックが迷路となっていれば OK 、なっていなければ NG を出力するプログラムを作成してください。 ボードは横方向に w 、縦方向に h の大きさをもち、 左上の座標は(1 , 1)、右下の座標は(w, h)とします。ブロックは 2 &times; 4 の長方形ですべて同じ大きさです。ブロックの色 c は 1 (白)、2 (黄)、3 (緑)、4 (青)、5 (赤) のいずれかです。ブロックのボード上での向き d は 横方向に長い場合 0 、 縦方向に長い場合 1 とします。 ブロックの位置はブロックの左上の座標 (x, y) によって表されます。なお、ブロックの位置は他のブロックと重なることは無く、ボードからはみ出すこともありません。

Input

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

w h
xs ys
xg yg
n
c1 d1 x1 y1
c2 d2 x2 y2
:
cn dn xn yn

1 行目にボードの大きさw, h (4 ≤ w, h ≤ 100) が与えられます。2 行目にスタートの座標 xs, ys、3 行目にゴールの座標 xg, yg が与えられます。

4 行目にブロックの個数 n が与えられます。続く n 行に i 番目のブロックの色 ci、向き di、位置 xi, yi が与えられます。

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

Output

入力データセットごとに、判別結果を１行に出力します。

Sample Input

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

Output for the Sample Input

OK
NG



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


Sample output:
OK
NG

Submission status: Accepted

Solution code:
while True:
    w,h=map(int, input().split())
    if w==h==0:
        break
    xs,ys=map(int, input().split())
    xg,yg=map(int, input().split())
    xs-=1
    ys-=1
    xg-=1
    yg-=1
    n=int(input())
    dataset=[]
    for _ in range(n):
        dataset.append(list(map(int,input().split())))

    maze=[ [0 for i in range(w) ] for j in range(h)]

    for data in dataset:
        color=data[0]
        drc=data[1]
        x=data[2]-1
        y=data[3]-1
        x_list=[x,x+1] if drc==1 else [x,x+1,x+2,x+3]   
        y_list=[y,y+1,y+2,y+3] if drc==1 else [y,y+1]

        for dy in y_list:
            for dx in x_list:
                maze[dy][dx]=color

    history=[[-1 for i in range(w)] for j in range(h)]
    ws=[]
    dx_list=[0,0,1,-1]
    dy_list=[1,-1,0,0]

    flag=False

    if maze[ys][xs]!=0:
        ws.append([xs,ys])

    while len(ws)!=0:
        current=ws.pop(0)
        current_color=maze[current[1]][current[0]]
        if current[0]==xg and current[1]==yg:
            flag=True 
            break
        for dx,dy in zip(dx_list,dy_list):
            next_x=current[0]+dx
            next_y=current[1]+dy
            if next_x>=0 and next_x<w and next_y>=0 and next_y<h and maze[next_y][next_x]==current_color and history[next_y][next_x]==-1:
                history[next_y][next_x]=0
                ws.append([next_x,next_y])

    if flag:
        print('OK')
    else:
        print('NG')

Submission status: Accepted

Solution code:
from collections import deque

def search(xs, ys, xg, yg, board):  
  direct = ((-1, 0), (1, 0), (0, -1), (0, 1))
  visited = [[False] * (w + 2) for _ in range(h + 2)]
  visited[ys][xs] = True
  que = deque()
  que.append((xs, ys))
  while que:
    x, y = que.popleft()
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if (nx, ny) == (xg, yg):
        print("OK")
        return
      if not visited[ny][nx]:
        visited[ny][nx] = True
        if board[ny][nx] == color:
          que.append((nx, ny))
  else:
    print("NG")


while True:
  w, h = map(int, input().split())
  if w == 0:
    break

  xs, ys = map(int, input().split())
  xg, yg = map(int, input().split())

  board = [[0] * (w + 2) for _ in range(h + 2)]
  n = int(input())
  for _ in range(n):
    c, d, x, y = map(int, input().split())
    if d == 0:
      for xi in range(x, x + 4):
        for yi in range(y, y + 2):
          board[yi][xi] = c
    else:
      for xi in range(x, x + 2):
        for yi in range(y, y + 4):
          board[yi][xi] = c
  
  color = board[ys][xs]
  if color == 0 or board[yg][xg] != color:
    print("NG")
    continue
  
  search(xs, ys, xg, yg, board)

Submission status: Accepted

Solution code:
mv=((0,1),(0,-1),(1,0),(-1,0))
def dfs(y,x):
    if color==0:
        return False
    if y==yg-1 and x==xg-1:
        return True
    L[y][x]=0
    for i,j in mv:
        mx=x+i
        my=y+j
        if 0<=mx<w and 0<=my<h and L[my][mx]==color:
            if dfs(my,mx):
                return True
    return False

while True:
    w,h=map(int,raw_input().split())
    if w==h==0:break
    xs,ys=map(int,raw_input().split())
    xg,yg=map(int,raw_input().split())
    L=[[0]*w for i in range(h)]
    n=input()
    for i in range(n):
        c,d,x,y=map(int,raw_input().split())
        if d==0:
            for j in range(2):
                for k in range(4):
                    L[y+j-1][x+k-1]=c
        elif d==1:
            for j in range(4):
                for k in range(2):
                    L[y+j-1][x+k-1]=c
    color=L[ys-1][xs-1]
    if dfs(ys-1,xs-1):
        print "OK"
    else:
        print "NG"

Submission status: Accepted

Solution code:
lx,ly = [4,2],[2,4]
dx = [-1,0,1,0]
dy = [0,-1,0,1]
while 1:
    w,h = map(int, raw_input().split())
    if w==0 and h==0: break
    xs,ys = map(int, raw_input().split())
    xg,yg = map(int, raw_input().split())
    f = [[0 for i in range(102)] for j in range(102)]
    s = []
    n = input()
    for i in range(n):
        c,d,x,y = map(int, raw_input().split())
        for p in range(lx[d]):
            for q in range(ly[d]):
                f[y+q][x+p] = c
    ans = 0
    if f[ys][xs]>0 and f[ys][xs]==f[yg][xg]:
        c = f[ys][xs]
        s.append([xs,ys])
        while len(s)>0:
            x,y = s.pop()
            if x==xg and y==yg:
                ans = 1; break;
            for k in range(4):
                if f[y+dy[k]][x+dx[k]]==c:
                    s.append([x+dx[k],y+dy[k]])
                    f[y+dy[k]][x+dx[k]] = 0
    print ("OK" if ans==1 else "NG")

Submission status: Accepted

Solution code:
global B
def check(B,x,y,c):
	if 0 < x < w+2 and 0 < y < h+2 and B[y][x] == c:
		B[y][x] = -1
		check(B,x-1,y,c);check(B,x,y-1,c);check(B,x+1,y,c);check(B,x,y+1,c)

while 1:
	w,h = map(int,raw_input().split())
	if w == 0: break
	B = [[0]*(w+2) for i in range(h+2)]
	xs,ys = map(int,raw_input().split())
	xg,yg = map(int,raw_input().split())
	for i in range(input()):
		c,d,x,y = map(int,raw_input().split())
		if d == 0:
			B[y][x:x+4] = [c]*4
			B[y+1][x:x+4] = [c]*4
		else:
			for j in range(4):
				B[y+j][x:x+2] = [c]*2
	if B[ys][xs] != B[yg][xg]:
		print "NG"
	else:
		check(B,xs,ys,B[ys][xs])
		print "OK" if B[yg][xg] == -1 else "NG"

Submission status: Accepted

Solution code:
import sys
from collections import deque

while True:
    W, H = map(int, input().split())
    if W == 0:
        break
    (xs, ys), (xg, yg) = map(int, input().split()), map(int, input().split())
    square = [[0]*(W+2) for _ in [0]*(H+2)]
    visited = [[0]*(W+2) for _ in [0]*(H+2)]
    visited[ys][xs] = 1
    N = int(input())
    for c, d, from_x, from_y in (map(int, sys.stdin.readline().split()) for _ in [0]*N):
        to_x, to_y = (from_x+4, from_y+2) if d == 0 else (from_x+2, from_y+4)
        for y in range(from_y, to_y):
            square[y][from_x:to_x] = [c]*(to_x-from_x)

    color = square[ys][xs] or -1
    dq = deque([(ys, xs)])
    popleft, append = dq.popleft, dq.append
    while dq:
        y, x = popleft()
        if y == yg and x == xg:
            print("OK")
            break
        for ny, nx in ((y+1, x), (y-1, x), (y, x+1), (y, x-1)):
            if not visited[ny][nx] and square[ny][nx] == color:
                visited[ny][nx] = 1
                append((ny, nx))
    else:
        print("NG")

Submission status: Accepted

Solution code:
# ref: https://qiita.com/masashi127/items/0c794e28f4b295ad82c6
import heapq
import itertools


def astar(init_pos, goal,dg):
    passed_list = [init_pos]
    init_score = distance(passed_list) + heuristic(init_pos,goal)
    checked = {init_pos: init_score}
    searching_heap = []
    heapq.heappush(searching_heap, (init_score, passed_list))
    while len(searching_heap) > 0:
        score, passed_list = heapq.heappop(searching_heap)
        last_passed_pos = passed_list[-1]
        if last_passed_pos == goal:
            return passed_list
        for pos in nexts(dg,last_passed_pos):
            new_passed_list = passed_list + [pos]
            pos_score = distance(new_passed_list) + heuristic(pos,goal)
            if pos in checked and checked[pos] <= pos_score:
                continue
            checked[pos] = pos_score
            heapq.heappush(searching_heap, (pos_score, new_passed_list))
    return []

def solve_dungeon(dungeon):
    init = find_ch(dungeon,"S")
    goal = find_ch(dungeon,"G")
    path = astar(init, goal,dungeon)

    if len(path) > 0:
        return True
    else:
        return False

def find_ch(dg,ch):
    for i, l in enumerate(dg):
        for j, c in enumerate(l):
            if c == ch:
                return (i, j)

def nexts(dg,pos):
    wall = "x"
    for a, b in [[' + 1',''], [' - 1',''], ['',' + 1'], ['',' - 1']]:
        if a or b:
            if dg[eval('pos[0]' + a)][eval('pos[1]' + b)] != wall:
                yield (eval('pos[0]' + a), eval('pos[1]' + b))

def heuristic(pos,goal):
    return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5

def distance(path):
    return len(path)

def render_path(dg,path):
    buf = [[ch for ch in l] for l in dg]

    for pos in path[1:-1]:
        buf[pos[0]][pos[1]] = "*"

    buf[path[0][0]][path[0][1]] = "s"
    buf[path[-1][0]][path[-1][1]] = "g"
    return ["".join(l) for l in buf]

if __name__ == "__main__":
    while(True):
        w,h = map(int,input().split())
        if w == 0 and h == 0:
            break
        xs,ys = map(int,input().split())
        xg,yg = map(int,input().split())
        n = int(input())
        d = [ list(map(int,input().split())) for _ in range(n)]
        m = [[0]*w for _ in range(h)]
        for e in d:
            for r in m[e[3]-1:e[3]+2*(e[1]+1)-1]:
                r[e[2]-1:e[2]+2*(2-e[1])-1] = [e[0]]*2*(2-e[1])
        ans = False
        for col in range(1,6):
            txt = [''.join(str(' ' if e==col else 'x') for e in f)  for f in m]
            if txt[ys-1][xs-1] == "x" or txt[yg-1][xg-1] == "x":
                continue
            txt[ys-1] = txt[ys-1][:xs-1] + 'S' + txt[ys-1][xs:]
            txt[yg-1] = txt[yg-1][:xg-1] + 'G' + txt[yg-1][xg:]
            for i in range(len(txt)):
                txt[i] = 'x' + txt[i] + 'x'
            txt.insert(0,'x'*(w+2))
            txt.append('x'*(w+2))
            ans |= solve_dungeon(txt)
            if ans:
                print("OK")
                break
        if not ans: print("NG")

Submission status: Runtime Error

Solution code:
def tansaku(cl,nc,ok,goal): #currentlocation,nonchecked,ok,goal
    [clx,cly]=cl
    for i in range(clx-1,clx+2):
        for j in range(cly-1,cly+2):
            if [i,j] in nc:
                nc.remove([i,j])
                ok.append([i,j])
                tansaku([i,j],nc,ok,goal)


while(1):
    [boardw,boardh]=[int(x) for x in raw_input().split()]
    if boardw==0 and boardh==0:
        break
    else:
        [startx,starty]=[int(x) for x in raw_input().split()]
        [goalx,goaly]=[int(x) for x in raw_input().split()]
        blockn=int(raw_input())
        blist={1:[],2:[],3:[],4:[],5:[]}
        startc=-1
        goalc=-1
        #mark location of block
        for i in range(blockn):
            [c,d,x,y]=[int(x) for x in raw_input().split()]
            if d: #d=1,tatenaga
                for xx in range(x,x+2):
                    for yy in range(y,y+4):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
            else:
                for xx in range(x,x+4):
                    for yy in range(y,y+2):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
        if startc==-1 or goalc==-1:
            print "NG"
        elif startc != goalc:
            print "NG"
        else:
            #check if connected
            cl=[startx,starty]
            nc=blist[c]
            nc.remove(cl)
            ok=[cl]
            goal=[goalx,goaly]
            tansaku(cl,nc,ok,goal)
            if goal in ok:
                print "OK"
            else:
                print "NG"

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10000) 

def tansaku(cl,nc,ok,goal): #currentlocation,nonchecked,ok,goal
    [clx,cly]=cl
    for i in range(clx-1,clx+2):
        for j in range(cly-1,cly+2):
            if [i,j] in nc:
                nc.remove([i,j])
                ok.append([i,j])
                tansaku([i,j],nc,ok,goal)


while(1):
    [boardw,boardh]=[int(x) for x in raw_input().split()]
    if boardw==0 and boardh==0:
        break
    else:
        [startx,starty]=[int(x) for x in raw_input().split()]
        [goalx,goaly]=[int(x) for x in raw_input().split()]
        blockn=int(raw_input())
        blist={1:[],2:[],3:[],4:[],5:[]}
        startc=-1
        goalc=-1
        #mark location of block
        for i in range(blockn):
            [c,d,x,y]=[int(x) for x in raw_input().split()]
            if d: #d=1,tatenaga
                for xx in range(x,x+2):
                    for yy in range(y,y+4):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
            else:
                for xx in range(x,x+4):
                    for yy in range(y,y+2):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
        if startc==-1 or goalc==-1:
            print "NG"
        elif startc != goalc:
            print "NG"
        else:
            #check if connected
            cl=[startx,starty]
            nc=blist[c]
            nc.remove(cl)
            ok=[cl]
            goal=[goalx,goaly]
            tansaku(cl,nc,ok,goal)
            if goal in ok:
                print "OK"
            else:
                print "NG"

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000) 

def tansaku(cl,nc,ok,goal): #currentlocation,nonchecked,ok,goal
    directions=[[-1,0],[1,0],[0,-1],[0,1]]
    [clx,cly]=cl
    for dd in directions:
        [i,j]=[clx+dd[0],cly+dd[1]]
        if [i,j] in nc:
            nc.remove([i,j])
            ok.append([i,j])
            tansaku([i,j],nc,ok,goal)
 
 
while(1):
    [boardw,boardh]=[int(x) for x in raw_input().split()]
    if boardw==0 and boardh==0:
        break
    else:
        [startx,starty]=[int(x) for x in raw_input().split()]
        [goalx,goaly]=[int(x) for x in raw_input().split()]
        blockn=int(raw_input())
        blist={1:[],2:[],3:[],4:[],5:[]}
        startc=-1
        goalc=-1
        #mark location of block
        for i in range(blockn):
            [c,d,x,y]=[int(x) for x in raw_input().split()]
            if d: #d=1,tatenaga
                for xx in range(x,x+2):
                    for yy in range(y,y+4):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
            else:
                for xx in range(x,x+4):
                    for yy in range(y,y+2):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
        if startc==-1 or goalc==-1:
            print "NG"
        elif startc != goalc:
            print "NG"
        else:
            #check if connected
            cl=[startx,starty]
            nc=blist[c]
            nc.remove(cl)
            ok=[cl]
            goal=[goalx,goaly]
            tansaku(cl,nc,ok,goal)
            if goal in ok:
                print "OK"
            else:
                print "NG"

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000) 

def tansaku(cl,nc,ok,goal): #currentlocation,nonchecked,ok,goal
    directions=[[-1,0],[1,0],[0,-1],[0,1]]
    [clx,cly]=cl
    for dd in directions:
        [i,j]=[clx+dd[0],cly+dd[1]]
        if [i,j] in nc:
            nc.remove([i,j])
            ok.append([i,j])
            tansaku([i,j],nc,ok,goal)
 
 
while(1):
    [boardw,boardh]=[int(x) for x in raw_input().split()]
    if boardw==0 and boardh==0:
        break
    else:
        [startx,starty]=[int(x) for x in raw_input().split()]
        [goalx,goaly]=[int(x) for x in raw_input().split()]
        blockn=int(raw_input())
        blist={1:[],2:[],3:[],4:[],5:[]}
        startc=-1
        goalc=-1
        #mark location of block
        for i in range(blockn):
            [c,d,x,y]=[int(x) for x in raw_input().split()]
            if d: #d=1,tatenaga
                for xx in range(x,x+2):
                    for yy in range(y,y+4):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
            else:
                for xx in range(x,x+4):
                    for yy in range(y,y+2):
                        blist[c].append([xx,yy])
                        if [xx,yy]==[startx,starty]:
                            startc=c
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
        if startc==-1 or goalc==-1:
            print "NG"
        elif startc != goalc:
            print "NG"
        else:
            #check if connected
            cl=[startx,starty]
            nc=blist[c]
            nc.remove(cl)
            ok=[cl]
            goal=[goalx,goaly]
            tansaku(cl,nc,ok,goal)
            if goal in ok:
                print "OK"
            else:
                print "NG"

Submission status: Runtime Error

Solution code:
import Queue
blockpos = [[[0,0], [0,1], [1,0], [1,1], [2,0], [2,1], [3,0], [3,1]], [[0,0], [0,1], [0,2], [0,3], [1,0], [1,1], [1,2], [1,3]]]
dxy = [[0,1], [1,0], [0,-1], [-1,0]]
q = Queue.Queue()
W, H = 0, 0

def checker(xs, ys, xg, yg, field, color):
  if color == 0:
    return False
  global W, H
  x = xs
  y = ys
  while True:
    if x == xg and y == yg:
      return True
    for dx, dy in dxy:
      if x+dx < 1 or y+dy < 1 or x+dx > H or y+dx > W:
        continue
      if field[x+dx][y+dy] == color:
        field[x+dx][y+dy] = 0
        q.put([x+dx, y+dy])
    if q.empty():
      return False
    x, y = q.get()


while True:
  # input
  W, H = map(int, raw_input().split())
  if W==0 and H==0:
    break
  field = [[0 for i in range(W+1)] for j in range(H+1)]
  xs, ys = map(int, raw_input().split())
  xg, yg = map(int, raw_input().split())
  n = int(raw_input())
  for i in range(n):
    c, d, x, y = map(int, raw_input().split())
    for dx, dy in blockpos[d]:
      field[x+dx][y+dy] = c
  result = checker(xs, ys, xg, yg, field, field[xs][ys])
  if result:
    print "OK"
  else:
    print "NG"

Submission status: Runtime Error

Solution code:
def block(board, y, x, direction, color):
    # ???
    if direction == 0:
        for i in range(2):
            for j in range(4):
                board[x + i][y + j] = color
    # ??±
    elif direction == 1:
        for i in range(2):
            for j in range(4):
                board[x + j][y + i] = color


def print_board(board):
    for i in range(len(board)):
        print(board[i])


def go_maze(board, s_x, s_y, g_x, g_y):
    place = board[s_x][s_y]
    if place == 0:
        return 'NG'
    x, y = s_x, s_y
    stack = []

    while True:
        # print(x, y)
        board[x][y] = place + 1
        if board[x + 1][y] == place:
            x += 1
            stack.append((x, y))
        elif board[x][y + 1] == place:
            y += 1
            stack.append((x, y))
        elif board[x - 1][y] == place:
            x -= 1
            stack.append((x, y))
        elif board[x][y - 1] == place:
            y -= 1
            stack.append((x, y))
        else:
            if len(stack) == 0 and board[x + 1][y] != place and board[x][y + 1] != place and board[x - 1][y] != place and board[x][y - 1] != place:
                return 'NG'
            (x, y) = stack.pop()

        if x == g_x and y == g_y:
            return 'OK'


def main():
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        board = [[0 for _ in range(w)] for _ in range(h)]
        s_x, s_y = map(int, input().split())
        g_x, g_y = map(int, input().split())
        for _ in range(int(input())):
            color, direction, x, y = map(int, input().split())
            block(board, x, y, direction, color)

        # print_board(board)
        print(go_maze(board, s_y, s_x, g_y, g_x))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def block(board, y, x, direction, color):
    # ???
    if direction == 0:
        for i in range(2):
            for j in range(4):
                board[x + i][y + j] = color
    # ??±
    elif direction == 1:
        for i in range(2):
            for j in range(4):
                board[x + j][y + i] = color


def print_board(board):
    for i in range(len(board)):
        print(board[i])


def go_maze(board, s_x, s_y, g_x, g_y):
    place = board[s_x][s_y]
    if place == 0:
        return 'NG'
    x, y = s_x, s_y
    stack = []

    while True:
        # print(x, y)
        board[x][y] = place + 1
        if x + 1 < len(board) and board[x + 1][y] == place:
            x += 1
            stack.append((x, y))
        elif y + 1 < len(board[x]) and board[x][y + 1] == place:
            y += 1
            stack.append((x, y))
        elif x - 1 > 0 and board[x - 1][y] == place:
            x -= 1
            stack.append((x, y))
        elif y - 1 > 0 and board[x][y - 1] == place:
            y -= 1
            stack.append((x, y))
        else:
            if len(stack) == 0 and board[x + 1][y] != place and board[x][y + 1] != place and board[x - 1][y] != place and board[x][y - 1] != place:
                return 'NG'
            (x, y) = stack.pop()

        if x == g_x and y == g_y:
            return 'OK'


def main():
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        board = [[0 for _ in range(w)] for _ in range(h)]
        s_x, s_y = map(int, input().split())
        g_x, g_y = map(int, input().split())
        for _ in range(int(input())):
            color, direction, x, y = map(int, input().split())
            block(board, x, y, direction, color)

        # print_board(board)
        print(go_maze(board, s_y, s_x, g_y, g_x))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def block(board, y, x, direction, color):
    # ???
    if direction == 0:
        for i in range(2):
            for j in range(4):
                board[x + i][y + j] = color
    # ??±
    elif direction == 1:
        for i in range(2):
            for j in range(4):
                board[x + j][y + i] = color


def print_board(board):
    for i in range(len(board)):
        print(board[i])


def go_maze(board, s_x, s_y, g_x, g_y):
    place = board[s_x][s_y]
    if place == 0:
        return 'NG'
    x, y = s_x, s_y
    stack = []

    while True:
        # print(x, y)
        board[x][y] = place + 1
        if x + 1 < len(board) and board[x + 1][y] == place:
            x += 1
            stack.append((x, y))
        elif y + 1 < len(board[x]) and board[x][y + 1] == place:
            y += 1
            stack.append((x, y))
        elif x - 1 > 0 and board[x - 1][y] == place:
            x -= 1
            stack.append((x, y))
        elif y - 1 > 0 and board[x][y - 1] == place:
            y -= 1
            stack.append((x, y))
        else:
            if len(stack) == 0 and board[x + 1][y] != place and board[x][y + 1] != place and board[x - 1][y] != place and board[x][y - 1] != place:
                return 'NG'
            (x, y) = stack.pop()

        if x == g_x and y == g_y:
            return 'OK'


def main():
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        board = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
        s_x, s_y = map(int, input().split())
        g_x, g_y = map(int, input().split())
        for _ in range(int(input())):
            color, direction, x, y = map(int, input().split())
            block(board, x, y, direction, color)

        # print_board(board)
        print(go_maze(board, s_y, s_x, g_y, g_x))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
""" Created by Jieyi on 9/20/16. """


def block(board, w, h, direction, color):
    # horizontal.
    if direction == 0:
        for i in range(2):
            for j in range(4):
                board[h + i][w + j] = color
    # vertical.
    elif direction == 1:
        for i in range(2):
            for j in range(4):
                board[h + j][w + i] = color


def print_board(board):
    for i in range(len(board)):
        print(board[i])


def go_maze(board, s_w, s_h, g_w, g_h):
    place = board[s_h][s_w]
    if place == 0:
        return 'NG'
    w, h = s_w, s_h
    stack = []

    while True:
        board[h][w] = place + 1
        if board[h + 1][w] == place:
            h += 1
            stack.append((w, h))
        elif board[h][w + 1] == place:
            w += 1
            stack.append((w, h))
        elif board[h - 1][w] == place:
            h -= 1
            stack.append((w, h))
        elif board[h][w - 1] == place:
            w -= 1
            stack.append((w, h))
        else:
            if len(stack) == 0 and board[h + 1][w] != place and board[h][w + 1] != place and board[h - 1][w] != place and board[h][w - 1] != place:
                return 'NG'
            (w, h) = stack.pop()

        if w == g_w and h == g_h:
            return 'OK'


def main():
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        board = [[0 for _ in range(w)] for _ in range(h)]
        s_w, s_h = map(int, input().split())
        g_w, g_h = map(int, input().split())
        for _ in range(int(input())):
            color, direction, w, h = map(int, input().split())
            block(board, w, h, direction, color)

        # print_board(board)
        print(go_maze(board, s_w, s_h, g_w, g_h))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
""" Created by Jieyi on 9/20/16. """


def block(board, w, h, direction, color):
    # horizontal.
    if direction == 0:
        for i in range(2):
            for j in range(4):
                board[h + i][w + j] = color
    # vertical.
    elif direction == 1:
        for i in range(2):
            for j in range(4):
                board[h + j][w + i] = color


def print_board(board):
    for i in range(len(board)):
        print(board[i])


def go_maze(board, s_w, s_h, g_w, g_h):
    place = board[s_h][s_w]
    if place == 0:
        return 'NG'
    w, h = s_w, s_h
    stack = []

    while True:
        board[h][w] = place + 1
        if h + 1 < len(board) and board[h + 1][w] == place:
            h += 1
            stack.append((w, h))
        elif w + 1 < len(board[h]) and board[h][w + 1] == place:
            w += 1
            stack.append((w, h))
        elif h - 1 > 0 and board[h - 1][w] == place:
            h -= 1
            stack.append((w, h))
        elif w - 1 > 0 and board[h][w - 1] == place:
            w -= 1
            stack.append((w, h))
        else:
            if len(stack) == 0 and board[h + 1][w] != place and board[h][w + 1] != place and board[h - 1][w] != place and board[h][w - 1] != place:
                return 'NG'
            (w, h) = stack.pop()

        if w == g_w and h == g_h:
            return 'OK'


def main():
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        board = [[0 for _ in range(w)] for _ in range(h)]
        s_w, s_h = map(int, input().split())
        g_w, g_h = map(int, input().split())
        for _ in range(int(input())):
            color, direction, w, h = map(int, input().split())
            block(board, w, h, direction, color)

        # print_board(board)
        print(go_maze(board, s_w, s_h, g_w, g_h))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def dfs(x, y, m, v, W, H, xg, yg):
    '''
    '''
    v[y, x] = True
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx = x + dx
        ny = y + dy
        if nx in range(W) and ny in range(H) and m[ny, nx] == m[y, x] and v[ny, nx] == False:
            dfs(nx, ny, m, v, W, H, xg, yg)

while True:
    H, W = list(map(int, input().split()))
    xs, ys = list(map(lambda x: int(x)-1, input().split()))
    xg, yg = list(map(lambda x: int(x)-1, input().split()))
    n = int(input())
    m = np.array([[0 for _ in range(W)] for __ in range(H)])
    v = np.array([[False for _ in range(W)] for __ in range(H)])

    for _ in range(n):
        c, d, x, y = list(map(int, input().split()))
        x -= 1
        y -= 1
        if d == 0:
            m[y:y+2, x:x+4] = c
        else:
            m[y:y+4, x:x+2] = c


    dfs(xs, ys, m, v, W, H, xg, yg)
    if v[yg, xg]:
        print('OK')
    else:
        print('NG')

    # print(m)
    # print(v)

Submission status: Runtime Error

Solution code:
import numpy as np

def dfs(x, y, m, v, W, H, xg, yg):
    '''
    '''
    v[y, x] = True
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx = x + dx
        ny = y + dy
        if nx in range(W) and ny in range(H) and m[ny, nx] == m[y, x] and v[ny, nx] == False:
            dfs(nx, ny, m, v, W, H, xg, yg)

while True:
    H, W = list(map(int, input().split()))
    if H == 0 and W == 0:
        break
    xs, ys = list(map(lambda x: int(x)-1, input().split()))
    xg, yg = list(map(lambda x: int(x)-1, input().split()))
    n = int(input())
    m = np.array([[0 for _ in range(W)] for __ in range(H)])
    v = np.array([[False for _ in range(W)] for __ in range(H)])

    for _ in range(n):
        c, d, x, y = list(map(int, input().split()))
        x -= 1
        y -= 1
        if d == 0:
            m[y:y+2, x:x+4] = c
        else:
            m[y:y+4, x:x+2] = c


    dfs(xs, ys, m, v, W, H, xg, yg)
    if v[yg, xg]:
        print('OK')
    else:
        print('NG')