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: 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')

Submission status: Runtime Error

Solution code:
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 = [[0 for _ in range(W)] for __ in range(H)]
    v = [[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:
            for y in range(2):
                for x in range(4):
                    m[y][x] = c
        else:
            for y in range(4):
                for x in range(2):
                    m[y][x] = c

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

Submission status: Runtime Error

Solution code:
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)

if __name__ == '__main__':
    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 = [[0 for _ in range(W)] for __ in range(H)]
        v = [[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:
                for y in range(2):
                    for x in range(4):
                        m[y][x] = c
            else:
                for y in range(4):
                    for x in range(2):
                        m[y][x] = c

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

Submission status: Runtime Error

Solution code:
BLOCK_WIDTH = 4
BLOCK_HEIGHT = 2
field = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
w = 0
h = 0
xg = 0
yg = 0

def main():
    global field, w, h, xg, yg
    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())
        field = [[0] * w for _ in range(h)]
        for i in range(n):
            c, d, x, y = map(int, input().split())
            arrangement(c, d, x, y)

        if dfs(field[xs][ys], xs, ys):
            print("OK")
        else:
            print("NG")


def arrangement(c, d, x, y):
    global field
    if d == 0:
        for i in range(BLOCK_HEIGHT):
            for j in range(BLOCK_WIDTH):
                field[y + i][x + j] = c
    else:
        for i in range(BLOCK_WIDTH):
            for j in range(BLOCK_HEIGHT):
                field[y + i][x + j] = c


def dfs(c, x, y):
    global field

    if x < 0 or x >= w or y < 0 or y >= h:
        return False
    if field[y][x] != c:
        return False
    if x == xg and y == yg:
        return True
    field[y][x] = -1
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if dfs(c, next_x, next_y):
            return True

    return False


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
BLOCK_WIDTH = 4
BLOCK_HEIGHT = 2
field = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
w = 0
h = 0
xg = 0
yg = 0

def main():
    global field, w, h, xg, yg
    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())
        field = [[0] * w for _ in range(h)]
        for i in range(n):
            c, d, x, y = map(int, input().split())
            arrangement(c, d, x, y)

        if dfs(field[ys][xs], xs, ys):
            print("OK")
        else:
            print("NG")


def arrangement(c, d, x, y):
    global field
    if d == 0:
        for i in range(BLOCK_HEIGHT):
            for j in range(BLOCK_WIDTH):
                field[y + i][x + j] = c
    else:
        for i in range(BLOCK_WIDTH):
            for j in range(BLOCK_HEIGHT):
                field[y + i][x + j] = c


def dfs(c, x, y):
    global field

    if x < 0 or x >= w or y < 0 or y >= h:
        return False
    if field[y][x] != c:
        return False
    if x == xg and y == yg:
        return True
    field[y][x] = -1
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if dfs(c, next_x, next_y):
            return True

    return False


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
BLOCK_WIDTH = 4
BLOCK_HEIGHT = 2
field = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
w = 0
h = 0
xg = 0
yg = 0

def main():
    global field, w, h, xg, yg
    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())
        field = [[0] * w for _ in range(h)]
        for i in range(n):
            c, d, x, y = map(int, input().split())
            arrangement(c, d, x, y)

        if dfs(field[ys][xs], xs, ys):
            print("OK")
        else:
            print("NG")


def arrangement(c, d, x, y):
    global field
    if d == 0:
        [[draw(x + j, y + i, c) for j in range(BLOCK_WIDTH)] for i in range(BLOCK_HEIGHT)]
    else:
        [[draw(x + j, y + i, c) for j in range(BLOCK_HEIGHT)] for i in range(BLOCK_WIDTH)]


def draw(x, y, c):
    field[y][x] = c


def dfs(c, x, y):
    global field

    if x == xg and y == yg:
        return True
    field[y][x] = -1
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
            continue
        if field[next_y][next_x] == c:
            if dfs(c, next_x, next_y):
                return True

    return False


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
		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)

Submission status: Runtime Error

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[xs][ys])
		print "OK" if B[yg][xg] == -1 else "NG"