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 sys
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
S = []
for _ in range(H):
    S.append(input())
P = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            P[i][j] = -1
P[Ch][Cw] = 1
P[Dh][Dw] = 100
yudlr = [0, 0, 1, -1]
xudlr = [1, -1, 0, 0]
D = deque()
Q = deque()
Q.append([Ch, Cw])
c = 0
while len(Q) > 0 or len(D) > 0:
    while len(Q) > 0:
        q = Q.popleft()
        y, x = q[0], q[1]
        for i in range(4):
            y1 = y + yudlr[i]
            x1 = x + xudlr[i]
            if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                continue
            if P[y1][x1] == 100:
                print(c)
                sys.exit()
            if P[y1][x1] == -1 and P[y][x] == 1:
                D.append([y, x])
                P[y][x] = 2
                continue
            if P[y1][x1] != 0:
                continue
            Q.append([y1, x1])
            P[y1][x1] = 1
    c += 1
    while len(D) > 0:
        d = D.popleft()
        y, x = d[0], d[1]
        for i in range(-2, 3):
            for j in range(-2, 3):
                y1 = y + i
                x1 = x + j
                if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                    continue
                if P[y1][x1] == 100:
                    print(c)
                    sys.exit()
                if P[y1][x1] != 0:
                    continue
                Q.append([y1, x1])
                P[y1][x1] = 1
print(-1)

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())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)
queue = []
heapq.heappush(queue,[0,ch-1,cw-1])
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = heapq.heappop(queue)
    if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
        continue
    if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
        continue
    if road_map[dot[1]][dot[2]] == "#":
        continue
    used_map[dot[1]][dot[2]] = dot[0]
    if used_map[dh-1][dw-1] > -1 and dot[0] >= used_map[dh-1][dw-1]:
        break

    if not (dot[2] - 1 < 0):
        heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
    if not (dot[2] + 1 >= w):
        heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
    if not (dot[1]+1 >= h):
        heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
    if not (dot[1]-1 < 0):
        heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                if not(used_map[dot[1]+x][dot[2]+y] > -1 and used_map[dot[1]+x][dot[2]+y] <= dot[0]+1):
                    heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])
    
print(used_map[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import heapq

H,W = map(int,input().split())
C_pos=list(map(lambda x:int(x)-1,input().split()))

C_pos=(C_pos[0],C_pos[1])

D_pos=list(map(lambda x:int(x)-1,input().split()))

Grid=[[c for c in input()] for _ in range(H)]

Dist=[[float("inf")]*W for _ in range(H)]

Dist[C_pos[0]][C_pos[1]]=0


Q=[]
heapq.heappush(Q,(0,C_pos[0],C_pos[1]))

DX=[-1,1,0,0]
while Q:
    #上下左右の道
    dist,cx,cy=heapq.heappop(Q)

    if cx==D_pos[0] and cy==D_pos[1]:
        break

    for dx,dy in zip(DX,reversed(DX)):
        nx = cx+dx
        ny=cy+dy
        if 0<=nx<H and 0<=ny<W and Grid[nx][ny]==".":
            if Dist[nx][ny]>dist:
                Dist[nx][ny]=dist
                Q.append((dist,nx,ny))
    #ワープ
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx==0 and dy==0:
                continue
            nx = cx+dx
            ny=cy+dy
            if 0<=nx<H and 0<=ny<W and Grid[nx][ny]==".":
                if Dist[nx][ny]>dist+1:
                    Dist[nx][ny]=dist+1
                    Q.append((dist+1,nx,ny))


#print(Dist)
ans=Dist[D_pos[0]][D_pos[1]]
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(x) for x in input().split()]
Ch, Cw = [int(x) - 1 for x in input().split()]
Dh, Dw = [int(x) - 1 for x in input().split()]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([10**9] * W)

queue = deque()
queue.appendleft((Ch, Cw, 0))

answer = 10**9
while queue:
    now_h, now_w, use_magic = queue.pop()
    warp_count[now_h][now_w] = use_magic

    if now_h == Dh and now_w == Dw:
        if answer > use_magic:
            answer = use_magic

        continue

    # 壁じゃない場合
    if not maze[now_h][now_w] == '#':

        # 上下左右に移動
        if now_h + 1 < H:
            if warp_count[now_h + 1][now_w] > use_magic:
                queue.appendleft((now_h+1, now_w, use_magic))
        if now_h - 1 >= 0:
            if warp_count[now_h - 1][now_w] > use_magic:
                queue.appendleft((now_h-1, now_w, use_magic))
        if now_w + 1 < W:
            if warp_count[now_h][now_w + 1] > use_magic:
                queue.appendleft((now_h, now_w + 1, use_magic))
        if now_w - 1 >= 0:
            if warp_count[now_h][now_w - 1] > use_magic:
                queue.appendleft((now_h, now_w - 1, use_magic))

        for h in range(-2, 3):
            for w in range(-2, 3):
                warp_h = now_h + h
                warp_w = now_w + w

                if warp_h >= 0 and warp_h < H:
                    if warp_w >= 0 and warp_w < W:
                        if warp_count[warp_h][warp_w] > use_magic + 1:
                            queue.append((warp_h, warp_w, use_magic + 1))
                else:
                    break


if answer == 10**9:
    print(-1)
else:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
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 = [input() for i in range(h)]

reach = [[False]*w for i in range(h)]
reach[ch][cw] = True

import heapq
q = [[0,ch,cw]]
heapq.heapify(q)

ans = -1
while q:
    cnt,cx,cy = heapq.heappop(q)
    reach[cx][cy] = True
    if cx==dh and cy==dw:
        ans = cnt
        break

    for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
        if not(0<=cx+dx<h and 0<=cy+dy<w):continue
        if s[cx+dx][cy+dy]=='.':
            if not reach[cx+dx][cy+dy]:
                heapq.heappush(q,[cnt,cx+dx,cy+dy])

    for dx in range(-2,3):
        for dy in range(-2,3):
            if [dx,dy] in [[0,0],[0,1],[0,-1],[1,0],[-1,0]]:continue
            if not(0<=cx+dx<h and 0<=cy+dy<w):continue
            if not reach[cx+dx][cy+dy] and s[cx+dx][cy+dy]=='.':
                heapq.heappush(q,[cnt+1,cx+dx,cy+dy])

    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)






if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    road_types = []
    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]
    for i in range(H):
        for j in range(W):
            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                for dy in range(-2, 3, 1):
                    for dx in range(-2, 3, 1):
                        if(-1< i+dy and i+dy < H and -1< j+dx and j+dx < W and flag_searched[i+dy][j+dx]==False):
                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)
    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])

Submission status: Time Limit Exceeded

Solution code:
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            v[hi][wi] = True

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    v = [[False]*w for _ in range(h)]
    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        for pi in p:
            walk(s, w1, h1, *pi, c, v)
        p = []
        for j, sv in enumerate(zip(s, v)):
            sj, vj = sv
            for i, svj in enumerate(zip(sj, vj)):
                sij, vij = svj
                if sij is not None or (not vij):
                    continue
                p.append((i, j))
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(h, w, cnt):
  global H
  global W
  global S
  tmp = []
  if (h<H-1) and (S[h+1][w]=='.') and (ans[h+1][w]<0):
    ans[h+1][w] = cnt
    tmp.append([h+1, w])
  if (w<W-1) and (S[h][w+1]=='.') and (ans[h][w+1]<0):
    ans[h][w+1] = cnt
    tmp.append([h, w+1])
  if (0<h) and (S[h-1][w]=='.') and (ans[h-1][w]<0):
    ans[h-1][w] = cnt
    tmp.append([h-1, w])
  if (0<w) and (S[h][w-1]=='.') and (ans[h][w-1]<0):
    ans[h][w-1] = cnt
    tmp.append([h, w-1])
  return tmp

def sub(h, w, cnt):
  global H
  global W
  global S
  tmp = []
  for x in range(max(h-2, 0), min(h+3, H)):
    for y in range(max(w-2, 0), min(w+3, W)):
      if (S[x][y]=='.') and (ans[x][y]<0):
        ans[x][y] = cnt
        tmp.append([x, y])
  return tmp

ans = [[-1]*W for i in range(H)]
ans[ch-1][cw-1] = 0
lis = [[ch-1, cw-1]]
li = [[ch-1, cw-1]]
flag = False
for i in range(1000000):
  for j in range(1000000):
    l = []
    for n in li:
      l += main(n[0], n[1], i)
    if l == []:
      break
    elif [dh-1, dw-1] in l:
      flag = True
      break
    else:
      lis += l
      li = l
  if flag:
    break
  else:
    z = []
    for m in lis:
      z += sub(m[0], m[1], i+1)
    if z == []:
      break
    else:
      lis = z
      li = z
print(ans[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    res = [-1]*W
    s = readline().rstrip().decode('utf-8')
    for i in range(W):
        if s[i] == ".":
            res[i] = 0
    maze.append(res)
    #maze += [list(readline().rstrip().decode().replace(".",0).replace("#",-1))]
    

ct = 1
for h in range(H):
    for w in range(W):
        if maze[h][w] == 0:
            y,x = h,w
            maze[y][x] = ct
            stack = deque([[y,x]])
            while stack:
                i,j = stack.pop()
                for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
                    if not 0 <= i + ni < H or not 0 <= j + nj < W:
                        continue
                    if maze[i+ni][j+nj] == 0:
                        maze[i+ni][j+nj] = ct
                        stack.append([i+ni,j+nj])
            ct += 1

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze[h][w] != -1:
                for i in range(3):
                    for j in range(-2,3):
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze[h+i][w+j] != -1 and \
                            not g2[maze[h][w]][maze[h+i][w+j]]:
                            g[maze[h][w]].append((1,maze[h+i][w+j]))
                            g[maze[h+i][w+j]].append((1,maze[h][w]))
                            g2[maze[h][w]][maze[h+i][w+j]] = 1
                            g2[maze[h+i][w+j]][maze[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #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] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze[sh-1][sw-1]
goal = maze[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    else:
        if [a,b] not in wq:
            wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    else:
        if [a,b] not in wq:
            wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    else:
        if [a,b] not in wq:
            wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    else:
        if [a,b] not in wq:
            wq.append([a,b])

    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])

    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])

    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])

    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])

    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))
ch,cw=ch+1,cw+1

s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
def is_sosed(h1, w1):
    if h1 > 0:
        if (dp[h1-1][w1] == -1):
            if (m[h1-1][w1] == '.'):
                dp[h1-1][w1] = dp[h1][w1]
                is_sosed(h1-1, w1)
            else:
                dp[h1-1][w1] = 10000
    if w1 > 0:
        if (dp[h1][w1-1] == -1):
            if (m[h1][w1-1] == '.'):
                dp[h1][w1-1] = dp[h1][w1]
                is_sosed(h1, w1-1)
            else:
                dp[h1][w1-1] = 10000
    if h1 < h - 1:
        if (dp[h1+1][w1] == -1):
            if (m[h1+1][w1] == '.'):
                dp[h1+1][w1] = dp[h1][w1]
                is_sosed(h1+1, w1)
            else:
                dp[h1+1][w1] = 10000
    if w1 < w - 1:
        if (dp[h1][w1+1] == -1):
            if (m[h1][w1+1] == '.'):
                dp[h1][w1+1] = dp[h1][w1]
                is_sosed(h1, w1+1)
            else:
                dp[h1][w1+1] = 10000

def find_warps(now):
    if dp[dh-1][dw-1] > -1:
        return True
    fl = True
    for i in range(h):
        for j in range(w):
            if dp[i][j] == now:
                for k in range(max(0, i-2), min(h, i+3)):
                    for p in range(max(0, j-2), min(w, j+3)):
                        if dp[k][p] == -1:
                            if m[k][p] == '.':
                                fl = False
                                dp[k][p] = dp[i][j] + 1
                                if dp[dh-1][dw-1] > -1:
                                    return True
                                stack.append([k, p])
                            else:
                                dp[k][p] = 10000
    return fl

def main():
    global dp, m, h, w, dh, dw, stack
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    m = [[] for i in range(h)]
    dp = [[-1]*w for i in range(h)]
    for i in range(h):
        m[i] = input()
    dp[ch-1][cw-1] = 0
    stack = [[ch-1, cw-1]]
    now = 0
    fl = False
    while dp[dh-1][dw-1] == -1:
        while stack:
            h11, w11 = stack.pop()
            is_sosed(h11, w11)
            if dp[dh-1][dw-1] > -1:
                break
        fl = find_warps(now)
        now += 1
        if fl:
            break
    print(dp[dh-1][dw-1])

main()

Submission status: Time Limit Exceeded

Solution code:
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 = []
for _ in range(H):
    row = list(input())
    S.append(row)
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)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = read().split()
    dist = [[INF] * W for _ in range(H)]
    walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    warp = [[1, 1], [1, -1], [-1, 1], [-1, -1], \
            [2, 0], [2, 1], [2, 2], [2, -1], [2, -1], [2, -2], \
            [-2, 0], [-2, 1], [-2, 2], [-2, -1], [-2, -1], [-2, -2], \
            [0, 2], [1, 2], [-1, 2], [0, -2], [1, -2], [-1, -2]]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh][nw] > dist[h][w]:
                    dist[nh][nw] = dist[h][w]
                    Q.append((nh,nw))
        for dh, dw in warp:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[h][w] + 1 < dist[nh][nw]:
                    dist[nh][nw] = dist[h][w] + 1
                    Q.append((nh,nw))

    if dist[gh][gw]==INF:
        print(-1)
    else:
        print(dist[gh][gw])




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque
def LI():
    return list(map(int,input().split()))
INF=float("inf")

h,w=LI()
ch,cw=LI()
# ch-=1
# cw-=1
dh,dw=LI()
# dh-=1
# dw-=1

maze=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
# S=[input() for _ in range(h)]

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

q=deque()
q.append((ch,cw))
p=deque()
while q:
    x,y=q.popleft()
    visited[x][y]=True
    for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
        xn,yn=x+i,y+j
        if maze[xn][yn]=="." and visited[xn][yn]==False:
            visited[xn][yn]=True
            q.append((xn,yn))
    for i in range(-2,3,1):
        for j in range(-2,3,1):
            xm,ym=x+i,y+j
            try:
                if visited[xm][ym]==False:
                    if maze[xm][ym]==".":
                        p.append((xm,ym))
            except:pass
if visited[dh][dw]==True:
    print(0)
    exit()

for pp in p:
    if visited[pp[0]][pp[1]]==False:
        q.append(pp)
if len(q)==0:
    print(-1)
    exit()
for ttt in range(1,100000):
    while q:
        x,y=q.popleft()
        visited[x][y]=True
        for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
            xn,yn=x+i,y+j
            if maze[xn][yn]=="." and visited[xn][yn]==False:
                visited[xn][yn]=True
                q.append((xn,yn))
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                xm,ym=x+i,y+j
                try:
                    if visited[xm][ym]==False:
                        if maze[xm][ym]==".":
                            p.append((xm,ym))
                except:pass
    
    if visited[dh][dw]==True:
        print(ttt)
        exit()
        
    for pp in p:
        if visited[pp[0]][pp[1]]==False:
            q.append(pp)
    if len(q)==0:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

def bfs(h, w, m, start, goal):
    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    canwarp=True
    cnt=0
    while canwarp:
        #print(goal)
        mimi=100000
        k=0
        t=[]
        trace=[]
        while not a.empty():
            hh, ww = map(int, a.get())
            #print(hh,ww)
            d[hh][ww]=1
            trace.append([hh,ww])
            if hh == goal[0] and ww==goal[1]:
                flg = True
                break
            for i in range(4):
                nx, ny = ww+dx[i], hh+dy[i]
                if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0:
                    a.put([ny, nx])
                    d[ny][nx] = 1
                    """
                for i in range(-2,3):
                    for j in range(-2,3):
                        if 0 <= hh+i < h and 0 <= ww+j < w and m[hh+i][ww+j]=="." and mimi>goal[1]-(hh+i)+goal[0]-(ww+j) and d[hh+i][ww+j] == 0:
                            t=[hh+i,ww+j]
                            mimi=goal[1]-(hh+i)+goal[0]-(ww+j)
                            k=1"""
        if flg==True:
            break

        #mimi=100000
        #k=0
        for item in trace:
            for i in range(-2,3):
                for j in range(-2,3):
                    if 0 <= item[0]+i < h and 0 <= item[1]+j < w and m[item[0]+i][item[1]+j]=="." and d[item[0]+i][item[1]+j] == 0:
                        t.append([item[0]+i,item[1]+j])
                        k=1
        #print(t)
        if k>0:
            for i in range(len(t)):
                a.put(t[i])
            cnt+=1
        else:
            canwarp=False
            break

    return cnt if flg else -1

def main():
    h,w=map(int, input().split())
    start=list(map(int, input().split()))
    goal=list(map(int, input().split()))
    m = [list(input().rstrip("\n")) for i in range(h)]
    start[0]-=1
    start[1]-=1
    goal[0]-=1
    goal[1]-=1
    #print(m,start,goal,h,w)
    print(bfs(h, w, m, start, goal))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd,deque as dq
import sys
inf=1000000
input=sys.stdin.readline
print=sys.stdout.write
n,m=map(int,input().split())
cx,cy=map(int,input().split())
cx-=1
cy-=1
dx,dy=map(int,input().split())
dx-=1
dy-=1
ll=[]
for i in range(n):
    ll.append(input().split()[0])
q=dq([cx*m+cy])
dis=dd(lambda :inf)
xx=[0,-1,0,1]
yy=[1,0,-1,0]
des=dx*m+dy
d=[[] for i in range(n*m)]
for x in range(n):
    for y in range(m):
        for i in range(4):
            X=x+xx[i]
            Y=y+yy[i]
            if(X<n and X>=0 and Y<m and Y>=0 and ll[X][Y]=='.'):
                d[x*m+y].append((X*m+Y,0))
        X=x-2
        Y=Y-2
        for i in range(5):
            for j in range(5):
                if(X+i>=0 and X+i<n and Y+j>=0 and Y+j<m and ll[X+i][Y+j]=='.'):
                    d[x*m+y].append(((X+i)*m+Y+j,1))
dis[q[0]]=0
lol=0
while q:
    curr=q.pop()
    #print(curr)
    if(curr==des):
        print(str(dis[curr]))
        lol=1
        break
    for j in d[curr]:
        temp,val=j
        if(dis[temp]>dis[curr]+val):
            dis[temp]=dis[curr]+val
            if(val==0):
                q.append(temp)
            else:
                q.appendleft(temp)
if(lol==0):
    print(str(-1))