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

Solution code:
from Queue import Queue
while True:

	N=101
	flag=0
	q=Queue()
	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()))
	n=int(raw_input())

	c=[]
	d=[]
	x=[]
	y=[]

	root=[[0  for i in range(N)] for j in range(N)]


	dx=[0,0,1,1,2,2,3,3]
	dy=[0,1,0,1,0,1,0,1]

	ddx=[1,0,-1,0]
	ddy=[0,1,0,-1]




	for i in range(n):
		a1,a2,a3,a4=map(int,(raw_input().split()))
		if a1==2:
			if a2==0:
				for j in range(8):
					root[a3+dx[j]][a4+dy[j]]=1
					

			else:
				for j in range(8):
					root[a3+dy[j]][a4+dx[j]]=1
					

		else:
			if a2==0:
				for j in range(8):
					root[a3+dx[j]][a4+dy[j]]=0

			else:
				for j in range(8):
					root[a3+dy[j]][a4+dx[j]]=0

	root[xg][yg]=2


	st=""
	for i in range(10):
		for j in range(10):
			if i*j==0:continue
			if root[i][j]==1:
				st+="@"

			elif root[i][j]==2:
				st+="G"
			else:
				st+="."
		st+="\n"


	#print st




	r=[xs,ys]
	q.put(r)
	
	while True:
		if q.empty():
			break

		else:
			r=q.get()
			#print r
			if r==[xg,yg]:
				flag=1
				break
			x=r[0]
			y=r[1]
			root[x][y]=0
			if 0<x and x<=xg and 0<y and y<=yg:
				for i in range(4):
					xx=x+ddx[i]
					yy=y+ddy[i]

					
					#print xx,yy,root[xx][yy]
					if root[xx][yy]>0:
						q.put([xx,yy])
						
						
	if flag==1:
		print "OK"
	else:
		print "NG"

Submission status: Wrong Answer

Solution code:

from Queue import Queue
while True:

	N=101
	flag=0
	q=Queue()
	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()))
	n=int(raw_input())

	c=[]
	d=[]
	x=[]
	y=[]

	root=[[0  for i in range(N+1)] for j in range(N+1)]


	dx=[0,0,1,1,2,2,3,3]
	dy=[0,1,0,1,0,1,0,1]

	ddx=[1,0,-1,0]
	ddy=[0,1,0,-1]




	for i in range(n):
		a1,a2,a3,a4=map(int,(raw_input().split()))
		if a1==2:
			if a2==0:
				for j in range(8):
					root[a3+dx[j]][a4+dy[j]]=1
					

			else:
				for j in range(8):
					root[a3+dy[j]][a4+dx[j]]=1
					

		else:
			if a2==0:
				for j in range(8):
					root[a3+dx[j]][a4+dy[j]]=0

			else:
				for j in range(8):
					root[a3+dy[j]][a4+dx[j]]=0

	root[xg][yg]=2


	st=""
	for i in range(10):
		for j in range(10):
			if i*j==0:continue
			if root[i][j]==1:
				st+="@"

			elif root[i][j]==2:
				st+="G"
			else:
				st+="."
		st+="\n"


	#print st




	r=[xs,ys]
	q.put(r)
	
	while True:
		if q.empty():
			break

		else:
			r=q.get()
			#print r
			if r==[xg,yg]:
				flag=1
				break
			x=r[0]
			y=r[1]
			root[x][y]=0
			if 0<x and x<=xg and 0<y and y<=yg:
				for i in range(4):
					xx=x+ddx[i]
					yy=y+ddy[i]

					
					#print xx,yy,root[xx][yy]
					if root[xx][yy]>0:
						q.put([xx,yy])
						
						
	if flag==1:
		print "OK"
	else:
		print "NG"

Submission status: Wrong Answer

Solution code:
from Queue import Queue
while True:

	N=101
	flag=0
	q=Queue()
	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()))
	n=int(raw_input())

	c=[]
	d=[]
	x=[]
	y=[]

	root=[[0  for i in range(N+10)] for j in range(N+10)]


	dx=[0,0,1,1,2,2,3,3]
	dy=[0,1,0,1,0,1,0,1]

	ddx=[1,0,-1,0]
	ddy=[0,1,0,-1]




	for i in range(n):
		a1,a2,a3,a4=map(int,(raw_input().split()))
		if a1==2:
			if a2==0:
				for j in range(8):
					root[a3+dx[j]][a4+dy[j]]=1
					

			else:
				for j in range(8):
					root[a3+dy[j]][a4+dx[j]]=1
					

		else:
			if a2==0:
				for j in range(8):
					root[a3+dx[j]][a4+dy[j]]=0

			else:
				for j in range(8):
					root[a3+dy[j]][a4+dx[j]]=0

	root[xg][yg]=2


	st=""
	for i in range(10):
		for j in range(10):
			if i*j==0:continue
			if root[i][j]==1:
				st+="@"

			elif root[i][j]==2:
				st+="G"
			else:
				st+="."
		st+="\n"


	#print st




	r=[xs,ys]
	q.put(r)
	
	while True:
		if q.empty():
			break

		else:
			r=q.get()
			#print r
			if r==[xg,yg]:
				flag=1
				break
			x=r[0]
			y=r[1]
			root[x][y]=0
			if 0<x and x<=xg and 0<y and y<=yg:
				for i in range(4):
					xx=x+ddx[i]
					yy=y+ddy[i]

					
					#print xx,yy,root[xx][yy]
					if root[xx][yy]>0:
						q.put([xx,yy])
						
						
	if flag==1:
		print "OK"
	else:
		print "NG"

Submission status: Wrong Answer

Solution code:
def searchsameid(nc,bid,biddict):
    sameidpoints=[]
    for point in nc:
        if biddict[point]==bid:
            sameidpoints.append(point)
    for point in sameidpoints:
            nc.remove(point)
    return sameidpoints

def tansakub(cbid,nc,ok,biddict): #currentblockid,noncheckedpoints,okpoints
    sameblockpoints=searchsameid(nc,cbid,biddict)
    ok.extend(sameblockpoints)
    for point in sameblockpoints:
        (px,py)=point
        for surpoint in [(px-1,py),(px+1,py),(px,py-1),(px,py+1)]:
            if surpoint in nc:
                newcbid=biddict[surpoint]
                tansakub(newcbid,nc,ok,biddict)

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:[]}
        biddict={}
        startc=-1
        goalc=-1
        #mark location of block
        for bid 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))
                        biddict[(xx,yy)]=bid
                        if [xx,yy]==[startx,starty]:
                            startc=c
                            sid=bid
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
                            gid=bid
            else:
                for xx in range(x,x+4):
                    for yy in range(y,y+2):
                        blist[c].append((xx,yy))
                        biddict[(xx,yy)]=bid
                        if [xx,yy]==[startx,starty]:
                            startc=c
                            sid=bid
                        if [xx,yy]==[goalx,goaly]:
                            goalc=c
                            gid=bid
        if startc==-1 or goalc==-1:
            print "NG"
        elif startc != goalc:
            print "NG"
        else:
            #check if connected
            cbid=sid
            nc=blist[c]
            ok=[]
            goal=(goalx,goaly)
            tansakub(cbid,nc,ok,biddict)
            if goal in ok:
                print "OK"
            else:
                print "NG"

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline


from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
Block = namedtuple('Block', ['color', 'direction', 'x', 'y'])


def occupation_point(block):
    x, y = block.x, block.y
    d = [(0, 0), (1, 0), (0, 1), (1, 1)]
    for dx, dy in d:
        yield x + dx, y + dy
    if block.direction:
        y += 2
    else:
        x += 2
    for dx, dy in d:
        yield x + dx, y + dy

def paintout(board, start, value):
    color = board[start.y][start.x]
    if color == 0:
        return
    que =[(start.x, start.y)]
    print('cv',color, value)
    while que:
        x,y = que.pop()
        if board[y][x] == color:
            board[y][x] = value
            que.extend([(x + dx, y + dy) for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]])


def is_reachable(size, start, goal, blocks):
    board = [[0] * (size.x + 2) for _ in range(size.y + 2)]
    for bi in blocks:
        for x, y in occupation_point(bi):
            board[y][x] = bi.color
    paintout(board, start, -1)
    for bi in board:
        print(bi)
    return board[goal.y][goal.x] == -1


while True:
    size = Point(*map(int, readline().split()))
    if size.x == 0:
        break
    start = Point(*map(int, readline().split()))
    goal = Point(*map(int, readline().split()))
    blocks = []
    for _ in range(int(readline())):
        blocks.append(Block(*map(int, readline().split())))
    print('OK' if is_reachable(size, start, goal, blocks) else 'NG')

Submission status: Wrong Answer

Solution code:
def solve(x, y, flag):
	if y == yf and x == xf or y == yh and x == xh:
		Map[y][x] = "tintin"
	if x < 0 or x >= w or y < 0 or y >= h or Map[y][x] != flag: return
	Map[y][x] = "tintin"
	solve(x + 1, y,flag)
	solve(x - 1, y,flag)
	solve(x, y + 1,flag)
	solve(x, y - 1,flag)
	

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

	Map = [list("0" * w) for _ in range(h)]
	
	xf, yf = map(int, raw_input().split())
	Map[yf - 1][xf - 1] = "flag"
	
	xh, yh = map(int, raw_input().split())
	Map[yh - 1][xh - 1] = "flag"
	
	n = input()
	for i in range(n):
		c,d,x,y = map(int, raw_input().split())
		if d == 0 :
			for xc in range(4):
				for yc in range(2):
					if Map[y - 1 + yc][x - 1 + xc] == "flag" or Map[y - 1 + yc][x - 1 + xc] == "flag": 
						Map[y - 1 + yc][x - 1 + xc] = "flag" + str(c)
					else : Map[y - 1 + yc][x - 1 + xc] = c
		elif d == 1:
			for xc in range(2):
				for yc in range(4):
					if Map[y - 1 + yc][x - 1 + xc] == "flag" or Map[y - 1 + yc][x - 1 + xc] == "flag": 
						Map[y - 1 + yc][x - 1 + xc] = "flag" + str(c)
					else : Map[y - 1 + yc][x - 1 + xc] = c
					
	if Map[yf - 1][xf - 1] == Map[yh - 1][xh - 1]:
		flag = int(Map[yf - 1][xf - 1][4:])
		solve(xf - 1, yf - 1, flag)
		if Map[yf - 1][xf - 1] == Map[yh - 1][xh - 1]:
			print "OK"
		else:
			print "NG"
	else:
		print "NG"

Submission status: Wrong Answer

Solution code:
def block(board, y, x, direction, color):
    # ???
    if direction == 0:
        for i in range(2):
            for j in range(4):
                print(x + i, y + j)
                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: Wrong Answer

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(110)] for _ in range(110)]
        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))
        print_board(board)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline


from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
Block = namedtuple('Block', ['color', 'direction', 'x', 'y'])


def occupation_point(block):
    x, y = block.x, block.y
    d = [(0, 0), (1, 0), (0, 1), (1, 1)]
    for dx, dy in d:
        yield x + dx, y + dy
    if block.direction:
        y += 2
    else:
        x += 2
    for dx, dy in d:
        yield x + dx, y + dy

def paintout(board, start, value):
    color = board[start.y][start.x]
    if color == 0:
        return
    que =[(start.x, start.y)]
    while que:
        x,y = que.pop()
        if board[y][x] == color:
            board[y][x] = value
            que.extend([(x + dx, y + dy) for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]])


def is_reachable(size, start, goal, blocks):
    board = [[0] * (size.x + 2) for _ in range(size.y + 2)]
    for bi in blocks:
        for x, y in occupation_point(bi):
            board[y][x] = bi.color
    paintout(board, start, -1)
    return board[goal.y][goal.x] == -1


while True:
    size = Point(*map(int, readline().split()))
    if size.x == 0:
        break
    start = Point(*map(int, readline().split()))
    goal = Point(*map(int, readline().split()))
    blocks = []
    for _ in range(int(readline())):
        blocks.append(Block(*map(int, readline().split())))
    print('OK' if is_reachable(size, start, goal, blocks) else 'NG')

Submission status: Accepted

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 > W or y+dy > H:
        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(H+1)] for j in range(W+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: Accepted

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(110)] for _ in range(110)]
        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: Accepted

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])


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


def is_goable(board, w, h, color):
    for x, y in direct:
        if board[h + x][w + y] == color:
            return True
    return False


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
        is_no_way = True
        for x, y in direct:
            if board[h + x][w + y] == place:
                w, h = w + y, h + x
                stack.append((w, h))
                is_no_way = False
                break

        if is_no_way:
            if len(stack) == 0 and not is_goable(board, w, h, 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(110)] for _ in range(110)]
        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: Accepted

Solution code:
import sys

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
start_color = 0

def main():
    global field, w, h, c, xg, yg, start_color
    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())
        xs -= 1
        ys -= 1
        xg -= 1
        yg -= 1
        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 - 1, y - 1)

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


def arrangement(c, d, x, y):
    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):
    global field
    field[y][x] = c


def dfs(x, y):
    global field

    if x == xg and y == yg:
        return True
    if start_color == 0:
        return False
    field[y][x] = 0
    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] != start_color:
            continue
        if dfs(next_x, next_y):
            return True

    return False


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Aizu Problem 0207: Block

import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def build_grid(W, H, N, blocks):
    grid = [[0 for _ in range(W)] for __ in range(H)]
    for c, d, x, y in blocks:
        x, y = x - 1, y - 1
        if d == 0:
            # horizontal long:
            dx, dy = 4, 2
        else:
            # vertical long:
            dx, dy = 2, 4
        for xi in range(x, x + dx):
            for yi in range(y, y + dy):
                grid[yi][xi] = c
    return grid


def bfs(W, H, grid, xs, ys, xg, yg):
    delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    color = grid[ys][xs]
    if color == 0:
        return "NG"
    visited = set()
    queue = [(xs, ys)]
    while len(queue) > 0:
        current = queue.pop(0)
        visited.add(current)
        col, row = current
        for drow, dcol in delta:
            row2, col2 = row + drow, col + dcol
            if 0 <= row2 < H and 0 <= col2 < W and grid[row2][col2] == color:
                # neighboring piece has same color:
                neighbor = (col2, row2)
                if neighbor == (xg, yg):
                    return "OK"
                if neighbor not in queue and neighbor not in visited:
                    queue.append(neighbor)
    return "NG"

    
while True:
    W, H = [int(_) for _ in input().split()]
    if W == H == 0:
        break
    xs, ys = [int(_) - 1 for _ in input().split()]
    xg, yg = [int(_) - 1 for _ in input().split()]
    N = int(input())
    blocks = [[int(_) for _ in input().split()] for __ in range(N)]
    grid = build_grid(W, H, N, blocks)
    print(bfs(W, H, grid, xs, ys, xg, yg))
    
    #for row in grid:
    #    print(''.join([str(r) for r in row]))
    #print(color)

Submission status: Accepted

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

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


def solve(w, h, xs, ys, xg, yg, blocks):
    # ????????????????????±????????°???????????????l
    field = [[0] * (w+1) for _ in range(h+1)]
    for c, d, x, y in blocks:
        field[y][x] = c
        field[y][x+1] = c
        field[y+1][x] = c
        field[y+1][x+1] = c

        if d == 0:              #  ?¨????
            field[y][x+2] = c
            field[y][x+3] = c
            field[y+1][x+2] = c
            field[y+1][x+3] = c
        else:                   #  ??????
            field[y+2][x] = c
            field[y+3][x] = c
            field[y+2][x+1] = c
            field[y+3][x+1] = c

    # ????????????????§????????????´????????§?¨??????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # ??????????????°???(S)??¨??´????????°???(G)?????????

    d = [[float('inf')] * (w+1) for _ in range(h+1)] #  ??????????????°?????????????????¢???INF??§?????????
    Q = deque()
    Q.append((xs, ys))
    d[ys][xs] = 0
    color = field[ys][xs]

    while Q:
        xc, yc = Q.popleft()        #  ?????¨??°?????§?¨?
        if xc == xg and yc == yg:
            return 'OK'
        for i in range(len(dx)):
            xn = xc + dx[i]
            yn = yc + dy[i]
            #  ?§????????????§???????????? ?????? ??¢?????¢?´¢?????§???????????°??????????????§?????¢?´¢????¶???????
            if 0 < xn <= w and 0 < yn <= h and d[yn][xn] == float('inf') and field[yn][xn] == color:
                Q.append((xn, yn))
                d[yn][xn] = d[yc][xc] + 1
    return 'NG'


def main(args):
    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())
        blocks = [list(map(int, input().split())) for _ in range(n)]

        result = solve(w, h, xs, ys, xg, yg, blocks)
        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=0207

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


def solve(w, h, xs, ys, xg, yg, blocks):
    # ????????????????????±????????°???????????????l
    field = [[0] * (w+1) for _ in range(h+1)]
    for c, d, x, y in blocks:
        field[y][x] = c
        field[y][x+1] = c
        field[y+1][x] = c
        field[y+1][x+1] = c

        if d == 0:              #  ?¨????
            field[y][x+2] = c
            field[y][x+3] = c
            field[y+1][x+2] = c
            field[y+1][x+3] = c
        else:                   #  ??????
            field[y+2][x] = c
            field[y+3][x] = c
            field[y+2][x+1] = c
            field[y+3][x+1] = c

    # ????????????????§????????????´????????§?¨??????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    d = [[-1] * (w+1) for _ in range(h+1)] #  ?????¢?´¢?????°??¨???????????¨??????-1???
    Q = deque()
    Q.append((xs, ys))
    d[ys][xs] = 0
    color = field[ys][xs]       #  ?????????????????¨?????§?????????????????????????????°?????¨???????????????

    while Q:
        xc, yc = Q.popleft()        #  ?????¨??°?????§?¨?
        if xc == xg and yc == yg:
            return 'OK'
        for i in range(len(dx)):
            xn = xc + dx[i]
            yn = yc + dy[i]
            #  ?§????????????§???????????? ?????? ??¢?????¢?´¢?????§???????????°??????????????§?????¢?´¢????¶???????
            if 0 < xn <= w and 0 < yn <= h and d[yn][xn] == -1 and field[yn][xn] == color:
                Q.append((xn, yn))
                d[yn][xn] = d[yc][xc] + 1
    return 'NG'


def main(args):
    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())
        blocks = [list(map(int, input().split())) for _ in range(n)]

        result = solve(w, h, xs, ys, xg, yg, blocks)
        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=0207

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


def solve(w, h, xs, ys, xg, yg, blocks):
    # ????????????????????±????????°???????????????l
    field = [[0] * (w+1) for _ in range(h+1)]
    for c, d, x, y in blocks:
        field[y][x] = c
        field[y][x+1] = c
        field[y+1][x] = c
        field[y+1][x+1] = c

        if d == 0:              #  ?¨????
            field[y][x+2] = c
            field[y][x+3] = c
            field[y+1][x+2] = c
            field[y+1][x+3] = c
        else:                   #  ??????
            field[y+2][x] = c
            field[y+3][x] = c
            field[y+2][x+1] = c
            field[y+3][x+1] = c

    # ????????????????§????????????´????????§?¨??????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    explored = set()            #  ??¢?´¢????????§?¨?(x, y)????¨????
    explored.add((xs, ys))
    Q = deque()
    Q.append((xs, ys))
    color = field[ys][xs]       #  ?????????????????¨?????§?????????????????????????????°?????¨???????????????

    while Q:
        xc, yc = Q.popleft()        #  ?????¨??°?????§?¨?
        if xc == xg and yc == yg:
            return 'OK'
        for i in range(len(dx)):
            xn = xc + dx[i]
            yn = yc + dy[i]
            #  ?§????????????§???????????? ?????? ??¢?????¢?´¢?????§???????????°??????????????§?????¢?´¢????¶???????
            if 0 < xn <= w and 0 < yn <= h and field[yn][xn] == color and (xn, yn) not in explored:
                Q.append((xn, yn))
                explored.add((xn, yn))
    return 'NG'


def main(args):
    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())
        blocks = [list(map(int, input().split())) for _ in range(n)]

        result = solve(w, h, xs, ys, xg, yg, blocks)
        print(result)


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