Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))
import collections
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	count = 0
	for v in [(u[0]-1,u[1]-1), (u[0]-1,u[1]), (u[0]-1,u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	for v in [(u[0],u[1]-1), (u[0],u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	for v in [(u[0]+1,u[1]-1), (u[0]+1,u[1]), (u[0]+1,u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	if count == 0:
		return []

	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0] + i,u[1] + j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				if v != u: ret.append(v)
	return ret
def f(s,t,mat):
	if all(['#' not in l for l in mat]):
		return 0

	heap = [(0,s)]
	r = {} 
	while(heap):
		d,u = heapq.heappop(heap)
		if u in r and d > r[u]: continue
		r[u] = min(r[u] if u in r else +float('inf'), d)
		if u == t:
			return d

		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d:
					heapq.heappush(heap,(d,v))
					r[v] = d
		for v in neighbors(u,mat):
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d + 1:
					heapq.heappush(heap,(d+1,v))
					r[v] = d + 1
	return -1

def g(s,t,mat):
	q = collections.deque([s])
	vis = set()
	while(q):
		u = q.popleft()
		vis.add(u)
		if u == t:
			return True
		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < len(mat) and 0 <= v[1] < len(mat[0]) and mat[v[0]][v[1]] == '.' and v not in vis:
				vis.add(v)
				q.append(v)

	return False



if g(s,t,mat):
	print 0
else:
	print f(s,t,mat)

Submission status: Time Limit Exceeded

Solution code:
h,w = list(map(int, input().split()))
# 初期位置
ch,cw = list(map(int, input().split()))
# ゴール位置
dh,dw = list(map(int, input().split()))
b = [['#']*(w+2)]
for _ in range(h):
    b.append(['#'] + list(input()) + ['#'])
b.append(['#']*(w+2))

from collections import deque
q = deque()
nq = deque()
q.append((ch, cw))

visit = [[False]*(w+2) for _ in range(h+2)]

warp = 0
while q or nq:
    while q:
        y,x = q.popleft()
        if (y,x) == (dh,dw):
            print(warp)
            exit()
        if visit[y][x]:
            continue
        visit[y][x] = True
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            if b[y+dy][x+dx] == '.':
                if not visit[y+dy][x+dx] and (y+dy, x+dx) not in q:
                    q.append((y+dy, x+dx))
            else:
                for dx in (-2,-1,0,1,2):
                    for dy in (-2,-1,0,1,2):
                        if y+dy > h or x + dx > w:
                            continue
                        if b[y+dy][x+dx] == '.':
                            if not visit[y+dy][x+dx] and (y+dy, x+dx) not in nq:
                                nq.append((y+dy, x+dx))
    q = nq
    nq = deque()
    warp += 1
    
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
dist = [[-1]*w for i in range(h)]

dk = [(i, j, 0) for i in range(-2, 3) for j in range(-2, 3)]
d = []
for i, j, c in dk:
    if (i, j) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        c = 0
    else:
        c = 1
    d.append((c, i, j))
d.sort()

def Dijkstra(ch, cw):
    """
    Dijkstra法を用いて単一始点終点の最短コストを算出する
    0オリジンとする。
    es: 辺を表す配列。
        es[start]: [cost, en]
    n: 頂点数
    source: 始点
    return: dist　最短距離距離配列。
    """
    import heapq
    used = [[False] * w for i in range(h)] # Falseならば計算対象
    edgelist = []
    # 始点の辺を追加
    for e in d:
        c, y, x = e
        if 0<=ch+y<h and 0<=cw+x<w:
            if used[ch+y][cw+x]: continue
            if area[ch+y][cw+x]=='#': continue
            heapq.heappush(edgelist, (c, ch+y, cw+x))
    used[ch][cw] = True
    dist[ch][cw] = 0
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        cost, y, x = minedge
        if used[y][x]:
            continue
        dist[y][x] = cost
        used[y][x] = True
        if y==dh and x==dw:
            return dist
        for e in d:
            next_cost, next_y, next_x = e
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if used[y+next_y][x+next_x]: continue
                if area[y+next_y][x+next_x]=='#': continue
                heapq.heappush(edgelist, (dist[y][x]+next_cost, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣25マスから
"""


def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    while que:
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
            
            for i in range(-2,3,1):
                for j in range(-2,3,1):
                    nxh,nxw = h+i,w+j
                    if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp+1):
                        que.append((nxh,nxw,worp+1))
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque 
inf = 10**9+1
def do():
    dyx = [(-1,0),(1,0),(0,1),(0,-1)]
    dd1 = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-1),(-1,1)]
    dd2 = [(2,-2),(2,-1),(2,0),(2,1),(2,2),(1,-1),(1,1)]
    dd3 = [(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)]
    dd4 = [(-2,-2),(-1,-2),(0,-2),(1,-2),(-2,-1),(-1,-1),(1,-1),]
    h,w=INTM()
    sh,sw=INTM()
    sh-=1
    sw-=1
    gh,gw=INTM()
    gh-=1
    gw-=1
    dist=[[inf]*w for i in range(h)]
    dist[sh][sw]=0
    s=[]
    for i in range(h):
        s.append(STR())
    
    que=deque()
    que.append(sh*w+sw)
    while que:
        q=que.popleft()
        th=q//w
        tw=q%w
        for dy,dx in dyx:
            if (0 <= th+dy <h) and (0 <= tw+dx <w):
                if s[th+dy][tw+dx]=="#":
                    if (dy,dx)==(-1,0):
                        ddt=dd1
                    if (dy,dx)==(1,0):
                        ddt=dd2
                    if (dy,dx)==(0,1):
                        ddt=dd3
                    if (dy,dx)==(0,-1):
                        ddt=dd4
#                    for ddy in range(-2,3,1):
 #                       for ddx in range(-2,3,1):
                    for ddy,ddx in ddt:        
                         if (ddy,ddx) in dyx or ((ddy,ddx) == (0,0)):
                                continue
                         if (0 <= th+ddy <h) and (0 <= tw+ddx <w):
                            if  s[th+ddy][tw+ddx]==".":
                                if dist[th+ddy][tw+ddx] >dist[th][tw]+1:
                                    que.append((th+ddy)*w+(tw+ddx))
                                    dist[th+ddy][tw+ddx] =dist[th][tw]+1
                                    
                else:
                    if dist[th+dy][tw+dx] >dist[th][tw]:
                        que.append((th+dy)*w+(tw+dx))
                        dist[th+dy][tw+dx] =dist[th][tw]
        
    if dist[gh][gw]==inf:
        print(-1)
    else:
        print(dist[gh][gw])
        
    # print(dist)
                                
                                
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
cy, cx = map(lambda x:int(x)-1, input().split())
gy, gx = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(h)]
seen = [[-1]*w for _ in range(h)]
def f(sy, sx, cnt):
    que = []
    que.append((sy, sx))
    seen[sy][sx] = cnt
    while que:
        y, x = que.pop()
        for dy, dx in ((-1,0),(0,-1),(1,0),(0,1)):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if seen[ny][nx] != -1:
                    continue
                if S[ny][nx] == "#":
                    continue
                seen[ny][nx] = cnt
                que.append((ny, nx))
cnt = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == "." and seen[i][j] == -1:
      f(i, j, cnt)
      cnt += 1
G = [set() for _ in range(cnt+1)]
for i in range(h):
  for j in range(w):
    for dy in range(-2, 3):
      for dx in range(-2, 3):
        y, x = i+dy, j+dx
        if 0 <= y < h and 0 <= x < w:
          if S[i][j] == "#":
            continue
          if S[y][x] == "#":
            continue
          G[seen[i][j]].add(seen[y][x])
          G[seen[y][x]].add(seen[i][j])
s = seen[cy][cx]
g = seen[gy][gx]
dist = [-1]*(cnt+1)
dist[s] = 0
que = deque()
que.append((s, 0))
while que:
  v, d = que.popleft()
  dist[v] = d
  if g == v:
    print(dist[g])
    exit()
  for i in G[v]:
    if dist[i] != -1:
      continue
    que.append((i, d+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#
import math
import sys
import itertools
import numpy as np

h,w = map(int, input().split())

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

x = np.zeros((h,w))
y = np.zeros((h,w))

z = [list(input()) for i in range(h)]
x = z
#print(x)
x[ch-1][cw-1]='a'

def tansaku():
    nu = 0
    while 1:
        nutta=0 # 塗ったマス
        for i in range(h):
            for j in range(w):
                if x[i][j] == 'a':
                    if i>0:
                        if x[i-1][j]=='.':
                            nutta += 1
                            x[i-1][j]='a'
                    if j>0:
                        if x[i][j-1]=='.':
                            nutta += 1
                            x[i][j-1]='a'
                    if i<h-1:
                        if x[i+1][j]=='.':
                            nutta += 1
                            x[i+1][j]='a'
                    if j<w-1:
                        if x[i][j+1]=='.':
                            nutta += 1
                            x[i][j+1]='a'
        if nutta==0:
            return nu
        else:
            nu += nutta

def warp():
    y=[[0 for j in range(w)] for i in range(h)]
    nu = 0
    for i in range(h):
        for j in range(w):
            if x[i][j] == 'a':
                for p in range(max(i-2,0),min(i+3,h)):
                    for q in range(max(j-2,0),min(j+3,w)):
                        if x[p][q] == '.':
                            y[p][q]='a'
                            #print("a",p,q)
                            nu += 1
    for i in range(h):
        for j in range(w):
            if y[i][j]=='a':
                x[i][j]='a'
                #print("b")
    return nu # これは塗った数よりは多いがnuが1なら0ではない


answer = 0
while(1):
    #print(x,ch,cw,dh,dw)
    nurioe = tansaku()
    #print(x,nurioe)
    if x[dh-1][dw-1]=='a':
        print(answer)
        break
    nurioe = warp()
    answer += 1
    #print(x,nurioe)
    if nurioe == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
a = [list(input())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

dx=[1,0,-1,0,  2,1,0,-1,-2,  2,1,-1,-2,  2,-2,  2,1,-1,-2,  2,1,0,-1,-2]
dy=[0,1,0,-1,  2,2,2,2,2,  1,1,1,1,  0,0,  -1,-1,-1,-1,  -2,-2,-2,-2,-2]
m = len(dx)

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False

    while q:
        p = q.pop()
        #print((p[0],p[1]),d[p[1]][p[0]])
        if p[0] == gx and p[1] == gy:
            goal = True

        for i in range(m):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if i < 4:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]]
            else:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]] + 1

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
                continue
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        cost += 1
        for di in rx:
            x = px + di
            if x >= h or x < 0:
                continue
            sx = s[x]
            dpx = dp[x]
            for dj in ry:
                y = py + dj
                if y >= w or y < 0 or sx[y] == "#":
                    continue
                if dpx[y] > cost:
                    dpx[y] = cost
                    heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(input()) for _ in range(H)]


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = set()
        for s in S[max(0, i-2):i+3]:
            g |= set(s[max(0, j-2):j+3])
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True

can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys


def input(): return sys.stdin.readline().rstrip()


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input()) for i in range(H)]


def trans(h, w):
    return W*(h) + w


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

G = [[] for i in range(H*W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and S[dx+i][dy+j] == ".":
                    u, v = trans(i, j), trans(dx+i, dy+j)
                    G[u].append((v, 0))
                    G[v].append((u, 0))
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if S[i][j] == "." and 0 <= dx+i < H and 0 <= dy+j < W and S[dx+i][dy+j] == ".":
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 1))
                        G[v].append((u, 1))

D = [10**10 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]
q = [(0, (ch, cw))]
heapq.heapify(q)
while len(q) > 0:
    c, (i,j) = heapq.heappop(q)
    if s[i][j] != '.' and s[i][j] <= c:
        continue
    s[i][j] = c
    for v in vec:
        ii = i + v[0]
        jj = j + v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c, (ii, jj)))
    for v in vec5:
        ii = i+v[0]
        jj = j+v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c+1, (ii, jj)))
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))
import collections
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	count = 0
	for v in [(u[0]-1,u[1]-1), (u[0]-1,u[1]), (u[0]-1,u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	for v in [(u[0],u[1]-1), (u[0],u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	for v in [(u[0]+1,u[1]-1), (u[0]+1,u[1]), (u[0]+1,u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	if count == 0:
		return []

	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0] + i,u[1] + j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				if v != u: ret.append(v)
	return ret
def f(s,t,mat):
	if all(['#' not in l for l in mat]):
		return 0

	heap = [(0,s)]
	r = {} 
	while(heap):
		d,u = heapq.heappop(heap)
		if u in r and d > r[u]: continue
		r[u] = min(r[u] if u in r else +float('inf'), d)
		if u == t:
			return d

		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d:
					heapq.heappush(heap,(d,v))
					r[v] = d
		for v in neighbors(u,mat):
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d:
					heapq.heappush(heap,(d+1,v))
					r[v] = d + 1
	return -1

def g(s,t,mat):
	q = collections.deque([s])
	vis = set()
	while(q):
		u = q.popleft()
		vis.add(u)
		if u == t:
			return True
		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < len(mat) and 0 <= v[1] < len(mat[0]) and mat[v[0]][v[1]] == '.' and v not in vis:
				vis.add(v)
				q.append(v)

	return False



if g(s,t,mat):
	print 0
else:
	print f(s,t,mat)

Submission status: Time Limit Exceeded

Solution code:
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))

S=list()
G=list()
for h in range(H):
    S.append(input())

    G.append([-2 for w in range(W)])
    for w in range(W):
        if S[h][w] == '.':
            G[h][w] = -1

igraph=0
members=list()

def get_members(i,h,w):
    global members
    global G

    G[h][w] = i
    members[i].append((h,w))
    if h>0:
        if G[h-1][w] == -1:
            get_members(i,h-1,w)
    if h<H-1:
        if G[h+1][w] == -1:
            get_members(i,h+1,w)
    if w>0:
        if G[h][w-1] == -1:
            get_members(i,h,w-1)
    if w<W-1:
        if G[h][w+1] == -1:
            get_members(i,h,w+1)


for h in range(H):
    for w in range(W):
        if G[h][w] == -1:
            members.append([])
            get_members(igraph, h, w)
            igraph += 1

ngraph=igraph
# print(ngraph)
# for h in range(H):
#     print(G[h])

if ngraph == 1:
    ans = 0
    print(ans)
    exit(0)

Cgraph = G[Ch-1][Cw-1]
Dgraph = G[Dh-1][Dw-1]
if Cgraph == Dgraph:
    ans = 0
    print(ans)
    exit(0)

def check_can_warp(igraph, jgraph):
    global members

    for hi,wi in members[igraph]:
        for hj,wj in members[jgraph]:
            if abs(hi-hj) <= 2 and abs(wi-wj) <=2 :
                return 1
    return 0

conn=list()
distance=[None for i in range(ngraph)]
for igraph in range(ngraph):
    conn.append([0 for i in range(ngraph)])
    conn[igraph][igraph] = 1


for igraph in range(ngraph-1):
    for jgraph in range(ngraph):
        conn[igraph][jgraph] = check_can_warp(igraph,jgraph)
        conn[jgraph][igraph] = conn[igraph][jgraph]     

# print("conn=", conn)

def make_distance(i,d):
    global conn
    global distance
    global ngraph

    distance[i] = d

    for j in range(ngraph):
        if j != i and conn[i][j] == 1:
            if distance[j] is None or distance[j]>d+1:
                make_distance(j,d+1)




make_distance(Cgraph,0)

if distance[Dgraph] is not None:
    print(distance[Dgraph])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    Ch, Cw = LI_()
    Dh, Dw = LI_()
    S = [list(SS()) for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1)) 
    color = 0

    def dfs(cy, cx, tmp):
        S[cy][cx] = color
        tmp.add((cy, cx))
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == '.':
                dfs(ny, nx, tmp)

    # 連結成分
    # 連結成分でないところに対してはワープが必要だが、ワープすれば行けるとは保証できない
    # ワープありでの連結成分を調べる
    group_C = -1
    group_D = -1
    con = []
    for i, j in itertools.product(range(H), range(W)):
        if S[i][j] == '.':
            tmp = set()
            dfs(i, j, tmp)
            color += 1
            con.append(tmp)

    # for i in S:
    #     print(i)
    for i in range(len(con)):
        if (Ch, Cw) in con[i]:
            group_C = i
        if (Dh, Dw) in con[i]:
            group_D = i

    # print(group_C, group_D)

    G = [set() for _ in range(len(con))]

    for i, j in itertools.product(range(H), range(W)):
        if S[i][j] != '#':
            for dy, dx in itertools.product(range(-2, 3), repeat=2):
                ny = i + dy
                nx = j + dx
                if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != '#':
                    if S[ny][nx] != S[i][j]:
                        G[S[i][j]].add(S[ny][nx])
    # print(G)

    ans = [INF]
    def dfs2(c, path):
        if c == group_D:
            ans[0] = min(len(path) - 1, ans[0])
        else:
            for n in G[c]:
                if n not in path:
                    path.append(n)
                    dfs2(n, path)
                    path.pop()

    dfs2(group_C, [group_C])

    if ans[0] == INF:
        print(-1)
    else:
        print(ans[0])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
maze = [['#']*(W+2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#']*(W+2)]
around = [[-1,0], [0,-1], [1,0], [0,1]]
ind = 0

def paint(h, w, ind):
    if maze[h][w] == '.':
        maze[h][w] = ind
        for i, j in around:
            paint(h+i, w+j, ind)

for h in range(1, H+1):
    for w in range(1, W+1):
        if maze[h][w] == ".":
            paint(h, w, ind)
            ind += 1

path = [set() for _ in range(ind)]
for h in range(1, H+1):
    for w in range(1, W+1):
        if maze[h][w] != '#':
            for i in range(max(h-2, 0), min(h+3, H+2)):
                for j in range(max(w-2, 0), min(w+3, W+2)):
                   if maze[i][j] != '#' and maze[i][j] != maze[h][w]:
                       path[maze[h][w]].add(maze[i][j])

ind_s = maze[start[0]][start[1]]
ind_g = maze[goal[0]][goal[1]]
if ind_s == ind_g:
    print(0)
else:
    t, already, que = 1, set(), deque([ind_s])
    while len(que) > 0:
        nque = set()
        while len(que) > 0:   
            x = que.popleft()
            for y in path[x]:
                if y == ind_g:
                    print(t)
                    exit()
                if y not in already:
                    nque.add(y)
                    already.add(y)
        que = deque(nque)
        t += 1
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
a = [list(input())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

dx=[1,0,-1,0,  2,1,0,-1,-2,  2,1,-1,-2,  2,-2,  2,1,-1,-2,  2,1,0,-1,-2]
dy=[0,1,0,-1,  2,2,2,2,2,  1,1,1,1,  0,0,  -1,-1,-1,-1,  -2,-2,-2,-2,-2]
m = len(dx)

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False

    while q:
        p = q.popleft()
        #print((p[0],p[1]),d[p[1]][p[0]])
        if p[0] == gx and p[1] == gy:
            goal = True

        for i in range(m):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if i < 4:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]]
            else:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]] + 1

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())