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 collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque()

while route:
    while route:
        y, x = route.popleft()
        wroute.append([y, x])
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = list(map(int, input().split()))

Chw = list(map(int, input().split()))
Dhw = list(map(int, input().split()))

Ss = []
for _ in range(H):
    tmp = input()
    Ss.append(list(tmp))

mazeArray = np.zeros((H+6, W+6), dtype = 'int64')

for i in range(H+6):
    for j in range(W+6):
        if(i < 3 or i > H+2):
            mazeArray[i][j] = -1
        
        elif(j < 3 or j > W+2):
            mazeArray[i][j] = -1
        
        else:
            if(Ss[i - 3][j-3] == "#"):
                mazeArray[i][j] = -1
            else:
                mazeArray[i][j] = 100000

#前準備完了

H_que = collections.deque()
W_que = collections.deque()

H_que.append(Chw[0])
W_que.append(Chw[1])

mazeArray[Chw[0]+2][Chw[1]+2] = 0

#print(mazeArray)

for _ in range(10**5):
    H_iti = H_que.popleft() + 2
    W_iti = W_que.popleft() + 2

    #上移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti - 1][W_iti]):
        mazeArray[H_iti - 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 3)
        W_que.append(W_iti - 2)

    elif(mazeArray[H_iti - 1][W_iti] == -1):
        for i in range(H_iti-2, H_iti):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)
                
    #下移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti + 1][W_iti]):
        mazeArray[H_iti + 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 1)
        W_que.append(W_iti - 2)
        
    elif(mazeArray[H_iti+1][W_iti] == -1):
        for i in range(H_iti+1, H_iti+3):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #左移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti - 1]):
        mazeArray[H_iti][W_iti - 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 3)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti -2, W_iti):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #右移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti + 1]):
        mazeArray[H_iti][W_iti + 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 1)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti +1, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #移動Bパターン
    if(mazeArray[Dhw[0]+2][Dhw[1]+2] != 100000):
        print(mazeArray[Dhw[0]+2][Dhw[1]+2])
        sys.exit()

    if(len(H_que) == 0):
        break

#print(mazeArray)

if(mazeArray[Dhw[0]+2][Dhw[1]+2] == 100000):
    print(-1)

else:
    print(mazeArray[Dhw[0]+2][Dhw[1]+2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

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

maze=[[i for i in input()] for _ in range(H)]

visited = [[-1]*W for _ in range(H)]
queue = deque([])
queue.append((sx,sy))
visited[sy][sx] = 0
def bfs(v,queue,gx,gy,maze):
    check=deque([])



    while len(queue) != 0:
        n = queue.popleft()
        x,y = n[0], n[1]
        flag=0

        if n == (gx,gy):
            print(v)
            exit()

        for i, j in [(1,0), (0,1), (-1,0), (0,-1)]:
            if (x+i < 0) or (x+i >=W) or (y+j < 0) or (y+j >=H):
                continue
            if maze[y+j][x+i] == '.' and visited[y+j][x+i] == -1:
                queue.append((x+i,y+j))
                visited[y+j][x+i] = v
            elif maze[y+j][x+i] == '#':
                flag=1
        if flag==1:
            check.append((x,y))

    while len(check) != 0:
        n=check.popleft()
        x,y=n[0],n[1]
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i < 0) or (x+i >=W) or (y+j < 0) or (y+j >=H):
                    continue
                if maze[y+j][x+i] == '.' and visited[y+j][x+i] == -1:
                    queue.append((x+i,y+j))
                    visited[y+j][x+i] = v+1

    if len(queue)!=0:
        bfs(v+1,queue,gx,gy,maze)



bfs(0,queue,gx,gy,maze)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" :
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=[[0,a-1,b-1]]
heapify(stack)
if x==a-1 and y==b-1 and arr[x][y]=="#":
    print(-1)
    quit()
mi=inf
ans=[[inf]*m for i in range(n)]
while(stack):
    cost,xx,yy=heappop(stack)
    ans[xx][yy]=cost
    if xx==x and yy==y:
        mi=min(mi,cost)
        break

    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    if ans[xx+i][yy+j]>cost:
                        heappush(stack,[cost,xx+i,yy+j])
                else:
                    if ans[xx+i][yy+j] > cost+1:
                        heappush(stack,[cost+1, xx+i, yy + j])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def bfs(root):
    x, y, d = root
    dp[y, x] = 0
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    queue.appendleft((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    queue.append((nx, ny, d+1))
bfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

move = [[0,1], [0,-1], [1,0], [-1,0]]

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch+1, cw+1, dh+1, dw+1

s =[[-1 for j in range(w+4)] for i in range(h+4)]
for i in range(h):
  a = input()
  for j in range(2, w+2):
    s[i+2][j] = w*h+1 if a[j-2]=='.' else -1

    
#for i in s:
#  print(i)
q1 = deque([[ch,cw]])
s[ch][cw] = 0
while(s[dh][dw] == w*h+1 and q1):
  q2 = q1.copy()
  while q1:
    now = q1.popleft()
    nows = s[now[0]][now[1]]
    for m in move:
      nh, nw = now[0]+m[0], now[1]+m[1]
      if(s[nh][nw] > nows):
        s[nh][nw] = nows
        q1.append([nh, nw])
        q2.append([nh, nw])
 
  if(s[dh][dw] != w*h+1):
    break
    
  while q2:
    now = q2.popleft()
    nows = s[now[0]][now[1]]
    
    for i in range(-2,3):
      for j in range(-2,3):
        nh, nw = now[0]+i, now[1]+j
        if(s[nh][nw] > nows+1):
          s[nh][nw] = nows+1
          q1.append([nh, nw])

if(s[dh][dw] == w*h+1):
  print(-1)
else:
  print(s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import heapq, copy
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)]

lands = copy.deepcopy(s)
l = 0
def find_dot():
    for i in range(h):
        for j in range(w):
            if lands[i][j] == '.':
                return True, (i,j)
    return False, (0,0)

while True:
    b, (i,j) = find_dot()
    q = [(i,j)]
    if not b:
        break
    while len(q) > 0:
        i,j = q.pop()
        lands[i][j] = l
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and lands[ii][jj] == '.':
                q += [(ii, jj)]
    l += 1
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] == '.' and lands[ii][jj] != lands[i][j]:
            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 itertools
from heapq import *
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)]

directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [
    [
    [2, i],
    [1, i],
    [0, i],
    [-1, i],
    [-2, i],
    ] for i in range(-2, 2 + 1)
]
magic = list(itertools.chain(*magic))
# for i in range(5):
#     for j in range(5):
#         print(magic[i * 5 + j], end=" ")
#     print()
# print(magic, len(magic))
# print(magic[12])
# print("---")

que = [(0, ch, cw)]
visited = [[None] * w for _ in range(h)]
while que:
    cost, y, x = heappop(que)

    if visited[y][x] is not None:
        continue
    visited[y][x] = cost
    for d in directions:
        ny, nx = y + d[0], x + d[1]
        if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
            heappush(que, (cost, ny, nx))
    for d in magic:
        ny, nx = y + d[0], x + d[1]
        if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
            heappush(que, (cost + 1, ny, nx))

# for v in visited:print(v)
print(visited[dh][dw] if visited[dh][dw] is not None else -1)

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]

q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]

while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break

                
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
graph = [0] + [0] * h
inverse = [0] + [0] * h
for i in range(h):
    graph[i + 1] = [0] + list(input().strip())
    inverse[i + 1] = [0] + [-1] * w

from collections import deque

def bfs(graph, queue, inverse, part_seq):
    part = set()
    while queue:
        current_h, current_w = queue.popleft()
        part.add((current_h, current_w))
        inverse[current_h][current_w] = part_seq

        for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            next_h, next_w = current_h + dh, current_w + dw
            if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
                continue
            if graph[next_h][next_w] == '#':
                continue
            if inverse[next_h][next_w] != -1:
                continue
            queue.append((next_h, next_w))
    return part

part_seq = 0
parts = dict()
start_part = None
end_part = None
for i in range(1, h+1):
    for j in range(1, w+1):
        if graph[i][j] == '#':
            continue
        if inverse[i][j] != -1:
            continue
        else:
            part_seq += 1
            queue = deque([(i, j)])
            part = bfs(graph, queue, inverse, part_seq)
            parts[part_seq] = part
            if (ch, cw) in part:
                start_part = part_seq
            if (dh, dw) in part:
                end_part = part_seq

if start_part == end_part:
    print(0)
    sys.exit(0)

def can_warp(start_part, next_part):
    for current_h, current_w in parts[start_part]:
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                next_h, next_w = current_h + dh, current_w + dw
                if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
                    continue
                if graph[next_h][next_w] == '#':
                    continue
                if inverse[next_h][next_w] == -1:
                    continue
                if inverse[next_h][next_w] == next_part:
                    return True
    return False

new_graph = [0] + [[] for _ in range(part_seq)]
for i in range(1, part_seq+1):
    for j in range(i + 1, part_seq+1):
        if can_warp(i, j):
            new_graph[i].append(j)
            new_graph[j].append(i)

dist = [0] + [-1] * part_seq
dist[start_part] = 0
queue = deque([start_part])
while queue:
    current = queue.popleft()

    for n in new_graph[current]:
        if dist[n] != -1:
            continue
        else:
            dist[n] = dist[current] + 1
            queue.append(n)

if dist[end_part] != -1:
    print(dist[end_part])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    H, W = mi()
    Ch, Cw = mi()
    Dh, Dw = mi()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [input() for i in range(H)]
    

    d = deque([(Ch, Cw)])
    visited = [[math.inf]*W for i in range(H)]
    visited[Ch][Cw] = 0

    check = [[False]*W for i in range(H)]

    while d:
        now_h, now_w = d.pop()
        check[now_h][now_w] = True

        # 行けるとこリスト
        nexts = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0:
                    continue
                if 0 <= now_h+i < H and 0 <= now_w+j < W and S[now_h+i][now_w+j] == '.':
                        nexts.append((now_h+i, now_w+j))


        for next in nexts:
            next_h, next_w = next

            if abs(now_h-next_h)+abs(now_w-next_w) == 1:
                visited[next_h][next_w] = min(visited[next_h][next_w], visited[now_h][now_w])
                if not check[next_h][next_w]:
                    d.append(next)
            else:
                visited[next_h][next_w] = min(visited[next_h][next_w], visited[now_h][now_w]+1)
                if not check[next_h][next_w]:
                    d.appendleft(next)

    ans = visited[Dh][Dw]
    if ans != math.inf:
        print(ans)
    else:
        print(-1)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
H,W=[int(_) for _ in input().split()]
Ch,Cw=[int(_) for _ in input().split()]
Dh,Dw=[int(_) for _ in input().split()]
chizu=[list(input()) for j in range(H)]
costlist=[[float("inf") for a in range(W)] for b in range(H)]
costlist[Ch-1][Cw-1]=0
willvisit=deque()
willvisit.append((Ch-1,Cw-1))
while willvisit:
    currentpos=willvisit.popleft()
    if currentpos[0]>0:
        if chizu[currentpos[0]-1][currentpos[1]]=="." and costlist[currentpos[0]-1][currentpos[1]]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]-1][currentpos[1]]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0]-1,currentpos[1]))
    if currentpos[1]>0:
        if chizu[currentpos[0]][currentpos[1]-1]=="." and costlist[currentpos[0]][currentpos[1]-1]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]][currentpos[1]-1]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0],currentpos[1]-1))
    if currentpos[0]<H-1:
        if chizu[currentpos[0]+1][currentpos[1]]=="." and costlist[currentpos[0]+1][currentpos[1]]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]+1][currentpos[1]]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0]+1,currentpos[1]))
    if currentpos[1]<W-1:
        if  chizu[currentpos[0]][currentpos[1]+1]=="." and costlist[currentpos[0]][currentpos[1]+1]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]][currentpos[1]+1]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0],currentpos[1]+1))
    for a in range(25):
        dx=(a//5)-2
        dy=(a%5)-2
        ygoto=currentpos[0]+dy
        xgoto=currentpos[1]+dx
        if 0<=ygoto<=H-1 and 0<=xgoto<=W-1:
            if chizu[ygoto][xgoto]==".":
                if costlist[ygoto][xgoto]>costlist[currentpos[0]][currentpos[1]]+1:
                    costlist[ygoto][xgoto]=costlist[currentpos[0]][currentpos[1]]+1
                    willvisit.append((ygoto,xgoto))
if costlist[Dh-1][Dw-1]==float("inf"):
    print(-1)
else:
    print(costlist[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:

def     RemoveDoublons(pile, elem):
    i = 0
    l = len(pile)
    while (i < l):
        val = pile[i]
        if (val[0] == elem[0] and val[1] == elem[1]):
            pile.pop(i)
            l -= 1
        i += 1
    return pile

def     findCloser(pile, distance):
    pos = 0
    elem = pile[0]
    bestDist = distance[elem[0]][elem[1]]
    if (bestDist == 0):
        return 0
    for i in range(len(pile)):
        val = pile[i]
        if (distance[val[0]][val[1]] < bestDist):
            elem = val
            bestDist = distance[elem[0]][elem[1]]
            pos = i
            if (bestDist == 0):
                return pos
    return pos

def     isValidCase(i, j, size, mappy):
    if (i < 0 or  j < 0 or i >= size[0] or j >= size[1] or not mappy[i][j]):
        return False
    return True

def     Calculdist(i, j, elem):
    if ((i == elem[0] and  abs(j - elem[1]) == 1) or (j == elem[1] and  abs(i - elem[0]) == 1)):
        return 0
    return 1

def printMappy(distance):
    for i in range(len(distance)):
        print(distance[i])

def     parcour(mappy, distance, start, end, size):
    pile = [start]
    distance[start[0]][start[1]] = 0

    while(len(pile) > 0):
        pos = findCloser(pile, distance)
        elem = pile.pop(pos)
        pile = RemoveDoublons(pile, elem)
        myDist = distance[elem[0]][elem[1]]
        if (elem[0] == end[0] and elem[1] == end[1]):
            return myDist
        for i in range(elem[0] - 2, elem[0] + 3):
            for j in range(elem[1] - 2, elem[1] + 3 ):
                if (isValidCase(i, j, size, mappy) and not (i == elem[0] and j == elem[1])):
                    dist = Calculdist(i, j, elem)
                    if (myDist + dist < distance[i][j]):
                        distance[i][j] = myDist + dist
                        pile.append([i,j])
    return -1


data = input().split()
size = [int(data[0]) , int(data[1])]
data = input().split()
start = [int(data[0]) - 1, int(data[1]) - 1]
data = input().split()
end = [int(data[0]) - 1, int(data[1]) - 1]

LIM = 999999
mappy = []
distance = []
for i in range(size[0]):
    tmp = [False] * size[1]
    tmp2 = [LIM] * size[1]
    s = input()
    for j in range(size[1]):
        if (s[j] == '.'):
            tmp[j] = True
    mappy.append(tmp)
    distance.append(tmp2)
res = parcour(mappy, distance, start, end, size)
print(res)