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:
from copy import deepcopy 
import sys
sys.setrecursionlimit(10**6+10)

INF=10**6+10
h,w=[int(_) for _ in input().split()]

ch,cw=[int(_) for _ in input().split()]
dh,dw=[int(_) for _ in input().split()]

ch-=1
cw-=1
dh-=1
dw-=1

s=[[_ for _ in input()]for j in range(h)]

t=[[INF for i in range(w)]for j in range(h)]


i,j=ch,cw
cu=[[i,j]]
t[i][j]=0
next=[]
d=0
while len(cu)!=0:
    while len(cu)!=0:
        i,j=cu.pop()
        for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and (t[i+k][j+l]==INF or t[i+k][j+l]==d+1):
                t[i+k][j+l]=d
                cu.append([i+k,j+l])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]==INF:
                    t[i+k][j+l]=d+1
                    next.append([i+k,j+l])
                    # print(i+k,j+l)
    
    # print(next)
    cu=deepcopy(next)
    next=[]
    d+=1
    # print(d)
if t[dh][dw]==INF:
    t[dh][dw]=-1

print(t[dh][dw])

# print(t)

Submission status: Time Limit Exceeded

Solution code:

import heapq

dx = [-1,0,1,0]
dy = [0,-1,0,1]

def bfs(ch,cw):
    q = []#queue.Queue()
    S[ch][cw] = 0
    heapq.heappush(q,(S[ch][cw],[ch,cw]))
    while q:
        p = heapq.heappop(q)[1]
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                heapq.heappush(q,(S[next_p[0]][next_p[1]],next_p))
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    heapq.heappush(q,(S[next_p[0]][next_p[1]],next_p))
                    
            
    return 
        
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
S = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1


bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
class UnionFind:
    def __init__(self, n):
        self.setSize = [1] * n
        self.numSets = n
        self.rank = [0] * n
        self.p = [i for i in range(n)]
    def findSet(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.findSet(self.p[i])
            return self.p[i]
    def isSameSet(self, i, j):
        return self.findSet(i) == self.findSet(j)
    def unionSet(self, i, j):
        if not self.isSameSet(i, j):
            self.numSets -= 1
            x = self.findSet(i)
            y = self.findSet(j)
            if self.rank[x] > self.rank[y]:
                self.p[y] = x
                self.setSize[x] += self.setSize[y]
            else:
                self.p[x] = y
                self.setSize[y] += self.setSize[x]
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1
    def numDisjointSets(self):
        return self.numSets
    def sizeOfSet(self, i):
        return self.setSize[self.findSet(i)]


h, w = [int(i) for i in input().split()]
ch, cw = [int(i)-1 for i in input().split()]
dh, dw = [int(i)-1 for i in input().split()]
A = [input() for i in range(h)]
uf = UnionFind(h*w)
twoonemap = dict()
counter = 0
for i in range(h):
    for j in range(w):
        twoonemap[(i,j)] = counter
        counter += 1
for i in range(h):
    for j in range(w):
        if A[i][j] == '.':
            if j+1 < w and A[i][j+1] == '.':
                uf.unionSet( twoonemap[(i,j)], twoonemap[(i, j+1)])
            if i+1 < h and A[i+1][j] == '.':
                uf.unionSet( twoonemap[(i,j)], twoonemap[(i+1, j)])

source_set = uf.findSet(twoonemap[(ch, cw)])
target_set = uf.findSet(twoonemap[(dh, dw)])
if source_set == target_set:
    print(0)
    # now find the distance between the disjoint component
else:
    g = defaultdict(set)
    for i in range(h):
        for j in range(w):
            if A[i][j] == '.':
                first_set = uf.findSet(twoonemap[(i,j)])
                #for k1 in range(i-2, i+3):
                #    for k2 in range(j-2, j+3):
                for k1 in range(i-2, i+3):
                    for k2 in range(j-2, j+3):
                        if 0<= k1 < h and 0<= k2 < w and A[k1][k2] == '.':
                            second_set = uf.findSet(twoonemap[(k1,k2)])
                            if first_set != second_set:
                                g[first_set].add(second_set)
                                g[second_set].add(first_set)
    visited = [False] * (h*w) 
    dist = [-1] *  (h*w)
    q = deque()
    q.append(source_set)  # set
    dist[source_set] = 0
    visited[source_set] = True
    while q:
        w = q.popleft()
        for v in g[w]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
                dist[v] = dist[w] + 1
    print(dist[target_set])

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

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
#d
h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
s = [input() for _ in range(h)]
inf = 99999999
dist = [[inf]* w for i in range(h)]
queue = []
queue.append([ch-1,cw-1])
dist[ch-1][cw-1] = 0

dx=[1,0,-1,0]
dy=[0,1,0,-1]

wx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy=[-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
import sys
warp = 0
wall = []
while True:
    while queue!=[]:
        y,x = map(int, queue.pop())

        if x == dw-1 and y ==dh-1:
            print(dist[y][x])
            sys.exit()

        for i in range(len(dx)):#まず壁探知
            next_x = x +dx[i]
            next_y = y +dy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]
                    else:
                        wall.append([y,x]) 
    wall = list(map(list, set(map(tuple, wall))))
    while wall != []:
        y,x = map(int, wall.pop())
        for i in range(len(wx)):
            next_x = x +wx[i]
            next_y = y +wy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]+1
    queue = list(map(list, set(map(tuple, queue))))
    
    if queue == []:
        print("-1")
        sys.exit()

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())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                q.append([next_y, next_x])
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(dist[DH - 1][DW - 1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

import heapq

#edgeには[weight,v]を追加していく
def dijkstra(s,edge,n):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append([1,r2])
                    checked.add((r1,r2))
dist=dijkstra(uf.FindRoot((sy-1)*w+(sx-1)),edges,h*w)
ans=dist[uf.FindRoot((gy-1)*w+(gx-1))]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

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

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
print f(s,t,mat)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue as Q


bloques = Q()
totreat = Q()

def voisins(x,y):
	lst = []
	for i in range(x-2,x+3):
		for j in range(y-2, y+3):
			if (i,j)!=(x,y): lst+=[(i,j)]
	return lst

def bfs():
	# ~ print("bfs")
	while not totreat.empty():
		x,y = totreat.get()
		# ~ print(x,y,"en traitement")
		vis[x][y] = True
		bou = False
		for a,b in ((x,y+1),(x,y-1),(x+1,y),(x-1,y)):
			if 0<=a<H and 0<=b<W:
				if g[a][b]=='.':
					if not vis[a][b]:
						bou = True
						vis[a][b] = True
						dist[a][b] = min(dist[a][b],dist[x][y])
						totreat.put((a,b))
				else:
					# ~ print(x,y,"est bloque") 
					if not deja[x][y]:
						bloques.put((x,y))
						deja[x][y] = True

def bfs_magic():
	# ~ print("bfsmagic")
	while not bloques.empty():
		x,y = bloques.get()
		vis[x][y] = True
		for a,b in voisins(x,y):
			if 0<=a<H and 0<=b<W and g[a][b]=='.':
				vis[a][b] = True
				dist[a][b] = min(dist[a][b],dist[x][y]+1)
				totreat.put((a,b))

H,W = [int(i) for i in input().split()]
CH,CW = [int(i)-1 for i in input().split()]
DH,DW= [int(i)-1 for i in input().split()]
g = [input() for i in range(H)]
vis = [[False]*W for i in range(H)]
deja = [[False]*W for i in range(H)]
dist = [[float('inf')]*W for i in range(H)]
dist[CH][CW] = 0
vis[CH][CW] = True
totreat.put((CH,CW))

while not totreat.empty():
	bfs()
	if not bloques.empty():
		bfs_magic()
	if vis[DH][DW]:
		print(dist[DH][DW])
		break
	

if not vis[DH][DW]: print("-1")
# ~ else:print(dist[DH][DW])

# ~ print("dist")
# ~ for d in dist:
	# ~ print(d)
# ~ print("vis")
# ~ for d in vis:
	# ~ print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin
h,w =map(int, stdin.readline().split())
ch,cw = map(int, stdin.readline().split())
dh,dw =map(int, stdin.readline().split())

g = []
for i in range(h):
  s = list(input())
  g.append(s)
inf = float("inf")
dist = [[inf]*w for i in range(h)]
queue = deque()
start = [ch-1,cw-1,0]
queue.append(start)
while queue:
    y, x,wapu = queue.popleft()
    if dist[y][x]<wapu:
      continue
    dist[y][x] = wapu
    for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue           
            elif wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = wapu
                queue.append([new_y, new_x,wapu])
    for new_y, new_x in ([y+1, x+1], [y+1, x-1], [y-1, x+1], [y-1, x-1], [y+2, x-1], [y-2, x-1], [y-2, x], [y+2, x], [y+2, x+1], [y-2, x+1], [y-1, x+2], [y, x+2], [y+1, x+2], [y+2, x+2], [y-2, x-2], [y-2, x+2], [y+2, x-2], [y-1, x-2], [y, x-2], [y+1, x-2]):
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue       
            else:
                 new_wapu= wapu +1
            if new_wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = new_wapu
                queue.append([new_y, new_x,new_wapu])

ans = dist[dh-1][dw-1]
if ans == inf:
  print(-1)
else:
  print(dist[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq


    def ok(i, j):
        return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

    H, W = map(int, input().split())
    C_h, C_w = map(int, input().split())
    C_h -= 1
    C_w -= 1
    D_h, D_w = map(int, input().split())
    D_h -= 1
    D_w -= 1
    S = [[None] * W for _ in range(H)]
    for i in range(H):
        for j, c in enumerate(input()):
            S[i][j] = c


    if S[D_h][D_w] == '#' or S[C_h][C_w] == '#':
        print(-1)
    else:
        queue = [(0, (C_h, C_w))]
        dist = {(C_h, C_w): 0}
        while queue:
            score, cur = heapq.heappop(queue)
            if cur == (D_h, D_w):
                print(score)
                break
            i, j = cur
            for offset in (1, -1):
                i_next = i + offset
                j_next = j + offset
                if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                    heapq.heappush(queue, (score, (i_next, j)))
                    dist[i_next, j] = score
                if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                    heapq.heappush(queue, (score, (i, j_next)))
                    dist[i, j_next] = score

            for a in [-2, -1, 0, 1, 2]:
                for b in [-2, -1, 0, 1, 2]:
                    if a == b == 0:
                        continue
                    i_jump = i + a
                    j_jump = j + b
                    if ok(i_jump, j_jump) and ((i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1):
                        heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                        dist[i_jump, j_jump] = score + 1
        else:
            print(-1)


main()

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[h][w]
x = [list(input()) for i in range(h)]
#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:
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()))

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:
				if (v not in r) or r[v] > d:
					heapq.heappush(heap,(d+1,v))
					r[v] = d + 1
	return -1
print f(s,t,mat)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
    s.append(input().rstrip('\n'))

d = [10 ** 18 for j in range(h*w)]

stack = deque([[ch-1, cw-1, 0]])

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.':
            stack.append([nh, nw, cnt])
    for nh in range(curh-2, curh+3):
        if nh >= 0 and nh < h:
            for nw in range(curw-2,curw+3):
                if nw >= 0 and nw < w and s[nh][nw] == '.':
                     stack.append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == 10 ** 18:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1)])
d=[[INF]*w for _ in range(h)]
d[sh-1][sw-1]=0
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y=q.popleft()
  if (x,y)==(gh-1,gw-1):
    print(d[gh-1][gw-1])
    break
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
      d[nx][ny]=d[x][y]
      q.append((nx,ny))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
else:print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
Ch, Cw = MAP()
Dh, Dw = MAP()
S = [input() for _ in range(H)]

cnt = [[10**6]*W for _ in range(H)]
cnt[Ch-1][Cw-1] = 0

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

def wizard_cnt(start_y, start_x):
	q = deque([(start_y, start_x)])
	while q:
		y, x = q.pop()
		flg = True
		for i in range(24):
			if i == 4 and flg:
				break
			ny = y + dy[i]
			nx = x + dx[i]
			if ny < 0 or nx < 0 or H <= ny or W <= nx:
				continue
			elif i < 4:
				if S[ny][nx] == "." and cnt[y][x] < cnt[ny][nx]:
					cnt[ny][nx] = cnt[y][x]
					q.append((ny, nx))
				elif S[ny][nx] == "#":
					flg = False
			elif 4 <= i and S[ny][nx] == "." and cnt[y][x]+1 < cnt[ny][nx]:
				cnt[ny][nx] = cnt[y][x]+1
				q.append((ny, nx))

wizard_cnt(Ch-1, Cw-1)

if cnt[Dh-1][Dw-1] == 10**6:
	print(-1)
else:
	print(cnt[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)
dist[S[0]][S[1]] = 0

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

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in [-2, -1, 0, 1, 2]:
                for g in [-2, -1, 0, 1, 2]:
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))