Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = [start]
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in setmada:
			stock.append((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.append(k)
						settansaku.add(k)
	
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.append(k)
					settansaku.add(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = [start]
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			stock.append((i, j))
			setmada.append((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.append(k)
						settansaku.add((i, j))
	
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.append(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.append((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.add(k)
						
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.add(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if not k in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if not k in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
yukaset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if not k in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if not k in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
yukaset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if not k in setmada:
						if not k in settansaku:
							setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if not k in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
									if k == goal:
										mode = 0
							
	if mode == 0:
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											kouho += 1
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
									kouho += 1
									if k == goal:
										mode = 0
							
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											kouho += 1
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	newkouho = len(stock)
	while newkouho > 0:
		for i, j in list(stock):
			stock.remove((i, j))
			newkouho -= 1
			for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									if not k in settansaku:
										setmada.add(k)
										kouho += 1
										if k == goal:
											mode = 0
								
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if 0 <= k[0] < h and 0 <= k[1] < w:
					if not k in kabeset:
						if not k in setmada:
							if not k in settansaku:
								setmada.add(k)
								kouho += 1
								if k == goal:
									mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	newkouho = len(stock)
	while newkouho > 0:
		for i, j in list(stock):
			stock.remove((i, j))
			newkouho -= 1
			for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
				if 0 <= k[0] < h and 0 <= k[1] < w:
					if not k in kabeset:
						if not k in setmada:
							if not k in settansaku:
								setmada.add(k)
								kouho += 1
								if k == goal:
									mode = 0
								
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

Fixed submission:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)