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

def main():

    input = sys.stdin.readline

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

    S[Ch-1][Cw-1] = 0

    while len(d) > 0:
        Ph,Pw = d.popleft()

        # if (Ph == Dh-1) & (Pw == Dw-1):
        #     goal = True
        #     break

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if S[nh][nw] == ".":
                S[nh][nw] = S[Ph][Pw]
                d.appendleft((nh,nw))
            elif S[nh][nw] > S[Ph][Pw]:
                S[nh][nw] = min(S[nh][nw],S[Ph][Pw])
                d.appendleft((nh,nw))





        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if S[nh][nw] == ".":
                S[nh][nw] = S[Ph][Pw] + 1
                d.append((nh,nw))
            elif S[nh][nw] > S[Ph][Pw] + 1:
                S[nh][nw] = min(S[nh][nw],S[Ph][Pw]+1)
                d.append((nh,nw))

    if S[Dh-1][Dw-1] == ".":
        print("-1")
    else:
        print(S[Dh-1][Dw-1])
         

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
import copy

def main():
    hh,ww = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    maze=[list(input()) for l in range(hh)]
    warp=[[0]* ww for i in range(hh)]

    numwarp = 0
    warpcost = 10000

    # Maze preprocess
    for y in range(hh):
        for x in range(ww):
            if maze[y][x]=='.':
                maze[y][x]=math.inf
            elif maze[y][x] == '#':
                maze[y][x]=int(-1)


    maze[ch-1][cw-1] = 0
    que = deque([[ch-1, cw-1]])
#    print(que)
    while que:
#        print(que, maze)
        current_hh, current_ww = que.popleft()
        for i in [-2, -1, 0, 1, 2]:
            for j in [-2, -1, 0, 1, 2]:
                #print([i,j])
                if i == 0 and j == 0:
                    continue
                next_hh, next_ww = current_hh + i, current_ww + j
                if (next_hh >= 0) & (next_ww >= 0) & (next_hh < hh) & (next_ww < ww):
                    dist = maze[next_hh][next_ww]
                    #print([next_hh,next_ww])
                    if dist != -1:
                        if abs(i) == 2 or abs(j) == 2 or i*j != 0:
                            if (dist > maze[current_hh][current_ww] + 1) & (dist > 0):
                                maze[next_hh][next_ww] = maze[current_hh][current_ww] + 1
                                que.append([next_hh, next_ww])
                        else:
                            if (dist > maze[current_hh][current_ww]) & (dist > 0):
                                maze[next_hh][next_ww] = maze[current_hh][current_ww]
                                que.append([next_hh, next_ww])

    mydist = maze[dh-1][dw-1]
    if mydist == math.inf:
        mydist = -1
 #   print(mydist,warp[dh-1][dw-1])
    print(mydist)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    seen_cost0 = set()
    seen_cost1 = set()
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                return now_count
            # cost 0 でたどり着けるマス
            maze[now_y][now_x] == '#'
            for dx, dy in [(1,0), (-1,0), (0, 1), (0, -1)]:
                nx = now_x + dx
                ny = now_y + dy
                if maze[ny][nx] == '#':
                    continue
                maze[ny][nx] = '#'
                seen_cost0.add((ny, nx))
                dq.appendleft((ny, nx, now_count))
            # cost 1 でたどり着けるマス
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    if dx == dy == 0: continue
                    nx = now_x + dx
                    ny = now_y + dy
                    if maze[ny][nx] == '#':
                        continue
                    if (ny, nx) in seen_cost0:
                        continue
                    dq.append((ny, nx, now_count+1))
        return None

    res = bfs(maze, ch+1, cw+1)
    if res is not None:
        print(res)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy): return dist[gx][gy]
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny)) 
    return -1
H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, 2]


def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx, ny = u[0] + mX[i], u[1] + mY[i]

            if nx < 0 or H <= nx or ny < 0 or W <= ny or S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(-2, 3):
            for j in range(-2, 3):
                wx = u[0] + i
                wy = u[1] + j
                if wx < 0 or H <= wx or wy < 0 or W <= wy or S[wx][wy] == "#":
                    continue
                if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]] + 1:  # state を確認
                    M[wx][wy] = M[u[0]][u[1]] + 1
                    q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

    print(M[Dh - 1][Dw - 1])


main()

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):
    def search(queue):
        delta = [(dx, dy) for dx, dy in product(range(-2, 3), repeat=2) if abs(dx) + abs(dy) >= 2]
        
        while queue:
            x, y = queue.pop()
            d = dp[y, x]
            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:
                    dp[ny, nx] = d
                    queue.append((nx, ny))
        for x, y in product(range(w), range(h)):
            if dp[y, x] == d:
                 for dx, dy in delta:
                    nx, ny = x+dx, y+dy
                    if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                        dp[ny, nx] = d+1
                        queue.append((nx, ny))
        if queue:
            search(queue)
    
    x, y = root
    dp[y, x] = 0
    queue = deque([root])
    search(queue)
    
bfs((cw-1, ch-1))
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
H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [list(input()) for i in range(H)]
INF = float("inf")

distance = [[INF]*W for i in range(H)]
Q = deque([[C_h,C_w,0]])
K = deque([])
while Q:
    while Q:
        k = 0
        h,w,d = Q.popleft()
        if d >= distance[h][w]:
            continue
        distance[h][w] = d
        for i_h,i_w in [[h+1,w],[h-1,w],[h,w+1],[h,w-1]]:
            if min(i_h,i_w)<0 or i_h >= H or i_w >= W:
                if k==0:
                    K.append([h,w,d])
                    k += 1
                continue
            if S[i_h][i_w] != "#":
                Q.append([i_h,i_w,d])
            if S[i_h][i_w] == "#" and k==0:
                K.append([h,w,d])
                k += 1
    while K:
        h,w,d = K.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j) <= 1:
                    continue
                i_h,i_w = h+i,w+j
                if min(i_h,i_w)<0 or i_h >= H or i_w >= W:
                    continue
                if S[i_h][i_w] != "#":
                    Q.append([i_h,i_w,d+1])

ans = distance[D_h][D_w]
print(-1 if ans == INF else ans)

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

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
ans[ch-1][cw-1]=0
count=0

def bfs(ans):
  qu = deque([])
  qu.append((cw-1,ch-1))
  while qu:
    x,y=qu.popleft()

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
            if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
              qu.appendleft((i,j))
              ans[j][i] = ans[y][x]
            elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
              ans[j][i]=(ans[y][x]+1)
              qu.appendleft((i,j))

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

Submission status: Time Limit Exceeded

Solution code:
def solve(now_x, now_y):
    for next_y in range(-2, 3):
        for next_x in range(-2, 3):
            x, y = now_x + next_x, now_y + next_y
            if 0 <= x < w and 0 <= y < h:
                if c[y][x] not in "#=!":
                    c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                    d2.append([x, y])


from collections import deque
import sys

input = sys.stdin.readline
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
c = [input().rstrip() for _ in range(h)]
cw -= 1
ch -= 1
dw -= 1
dh -= 1
c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
d1 = deque([[cw, ch]])
d2 = deque([])

for cnt in range(5000):
    for _ in range(1000000):
        for _ in range(len(d1)):
            now_x, now_y = d1.popleft()
            for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                x, y = now_x + next_x, now_y + next_y
                if 0 <= x < w and 0 <= y < h:
                    if x == dw and y == dh:
                        print(cnt)
                        exit()
                    c_xy = c[y][x]
                    if c_xy == "#":
                        solve(now_x, now_y)
                    elif c_xy != "=":
                        c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                        d1.append([x, y])
    else:
        if [dw, dh] in d2:
            print(cnt + 1)
            exit()
        if not d2:
            print(-1)
            exit()
        d1 = d2.copy()
        d2.clear()

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

def main():
    li = [["" for i in range(w)]for j in range(h)]
    
    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    que = deque()

    mx = []
    my = []

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            mx.append(i)
            my.append(j)

    lin = [[inf for i in range(w)]for j in range(h)]
    lin[ch][cw] = 0#ここをスタートの座標に変えること
    que.append((ch,cw))#ここもスタートの座標に変えること

    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]
        se = set()#被りがないかの確認

        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j

            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#":
                continue
            else:
                if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                    if lin[nx][ny] > lin[x][y]:
                        que.appendleft((nx,ny))
                        se.add((nx,ny))
                        lin[nx][ny] = lin[x][y]# 直接行ける
                else:
                    if lin[nx][ny] > lin[x][y]+1:
                        if (nx,ny) not in se:
                            que.append((nx,ny))
                            lin[nx][ny] = lin[x][y]+1# 魔法の力で行く

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def main():

    input = sys.stdin.readline

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]
    F=[ [-1] * W for i in range(H)]
    dist=[ [10000000] * W for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

    F[Ch-1][Cw-1] = 0
    dist[Ch-1][Cw-1] = 0

    while len(d) > 0:
        Ph,Pw = d.popleft()

        # if (Ph == Dh-1) & (Pw == Dw-1):
        #     goal = True
        #     break

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.appendleft((nh,nw))
                F[nh][nw] = 0
            if dist[nh][nw] > dist[Ph][Pw]:
                dist[nh][nw] = dist[Ph][Pw]
                d.appendleft((nh,nw))

        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.append((nh,nw))
                F[nh][nw] = 0
            if dist[nh][nw] > dist[Ph][Pw] + 1:
                dist[nh][nw] = dist[Ph][Pw] + 1
                d.appendleft((nh,nw))

    if dist[Dh-1][Dw-1] >= 10000000:
        print("-1")
    else:
        print(dist[Dh-1][Dw-1])
         

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase
from collections import deque

# %% define phase
global afx
global afy
global ans
ans = 0

def check(s, x, y, o, cnt):
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        if s[x+i][y+j] == '.':
            o.append([x+i, y+j, cnt])
            s[x+i][y+j] = str(cnt)
    return o, s

def wcheck(s, x, y, o, cnt):
    for i in range(5):
        a = i-2
        for j in range(5):
            b = j-2
#            if x+a>=0 and y+b>=0 and \
#            x+a<=h+2 and y+b<=w+2 and\
#            s[x+a][y+j] == '.':
            if s[x+a][y+b] == '.':
                if [x+a, y+b] not in o:
                    o.append([x+a, y+b, cnt+1])    
    return o
    
def bfs(s, x, y, h, w):
    cnt = 0
    f = deque()
    wf = deque()
    wf.append([x, y, cnt])
    while wf:
        [x, y, ncnt] = wf.popleft()
        if s[x][y] == '.':
            s[x][y] = str(cnt)
            cnt = ncnt
            f.append([x, y, cnt])
            while f:
                [x, y, cnt] = f.popleft()
    #            if [x, y, cnt+1] in wf:
    #                wf.remove([x, y, cnt+1])
                if [x, y] == [h, w]:
                    wf.clear()
                    return cnt
                f, s = check(s, x, y, f, cnt)
                wf = wcheck(s, x, y, wf, cnt)
#                print('--------')
#                for si in s:
#                    print(si)
#                print('--------')
    return -1

    
    

# %% input phase
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
ch += 1
cw += 1
dh, dw = list(map(int, input().split()))
dh += 1
dw += 1
s = [[] for _ in range(h+4)]
s[0] = list('#'*(w+4))
s[1] = list('#'*(w+4))
for i in range(h):
    si = input()
    s[i+2] = list('##' + si + '##')
s[h+2] = list('#'*(w+4))
s[h+3] = list('#'*(w+4))

# %% process phase
ans = bfs(s, ch, cw, dh, dw)

    

# %%output phase
print(ans)

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

if ch == dh and dw == cw:
    print(0)
    exit()

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    while len(que) != 0:
        sh, sw, count = que.popleft()
        memo_que.append([sh, sw, count])
        #print(sh, sw, count)
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if sh + ph == dh - 1 and sw + pw == dw - 1:
                    print(count)
                    exit()
                if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[(sh + ph, sw + pw)] = count
                    memo_que.append([sh + ph, sw + pw, count])
    #templist = []
    for sh, sw, count in memo_que:
        #print(sh, sw, count)
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]]:
                    if 0 <= sh + ph < h and 0 <= sw + pw < w:
                        if sh + ph == dh - 1 and sw + pw == dw - 1:
                            print(count + 1)
                            exit()
                        if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                            continue
                        if slist[sh + ph][sw + pw] == ".":
                            que.append([sh + ph, sw + pw, count + 1])
                            memo[(sh + ph, sw + pw)] = count + 1
                            #templist.append([sh + ph, sw + pw, count + 1])
    #memo_que = deque(templist)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# 方針は分かったのでヨシ！バチャやって実装力つけたい
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy): return dist[gx][gy]
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny)) 
    return -1
H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

que = deque()

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること

def main():
    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]
        se = set()#被りがないかの確認

        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j
            
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#":
                continue
            else:
                if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                    if lin[nx][ny] > lin[x][y]:
                        que.appendleft((nx,ny))
                        se.add((nx,ny))
                        lin[nx][ny] = lin[x][y]# 直接行ける
                else:
                    if lin[nx][ny] > lin[x][y]+1:
                        if (nx,ny) not in se:
                            que.append((nx,ny))
                            lin[nx][ny] = lin[x][y]+1# 魔法の力で行く

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

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

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    h, w = get_int_list()
    sr, sc = get_int_list()
    er, ec = get_int_list()

    d = [[-1] * (w+2) for _ in range(h+2)]

    for i in range(h):
        wk = get_string()
        for ii in range(w):
            if wk[ii] == ".":
                d[i+1][ii+1] = 10 ** 6

    d[sr][sc] = 0
    q = deque([])
    q2 = deque([])
    q.append([sr,sc])
    q2.append([sr,sc])

    def idou(i,ii,cnt_mahou):
        if 1 <= i <= h and 1 <= ii <= w:
            if d[i][ii] == 10 ** 6:
                q.append([i, ii])
                d[i][ii] = cnt_mahou


    ans = -1
    flg = True
    finish = False
    while flg:
        flg = False
        while q:
            wk = q.popleft()
            q2.append(wk)

            i = wk[0]
            ii = wk[1]
            cnt_mahou = d[i][ii]

            idou(i - 1, ii, cnt_mahou)
            idou(i + 1, ii, cnt_mahou)
            idou(i, ii - 1, cnt_mahou)
            idou(i, ii + 1, cnt_mahou)

            if d[er][ec] != 10 ** 6:
                ans = d[er][ec]
                finish = True
                break

        if finish:
            break

        while q2:
            wk = q2.popleft()
            i = wk[0]
            ii = wk[1]
            # 魔法を使う
            for wk in range(-2, 3):
                for wk2 in range(-2, 3):
                    if abs(wk) + abs(wk2) > 1:
                        flg = True
                        idou(i + wk, ii + wk2, cnt_mahou + 1)

    print(ans)

    #print(time.time() - start)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 後だし

import collections

H, W = map(int, input().split())
C = tuple((int(x)-1 for x in input().split()))
D = tuple((int(x)-1 for x in input().split()))
S = list()
for _ in range(H):
    S.append(list(input()))

queue = collections.deque()
visited = collections.deque()
queue.append(C)
cy, cx = C
S[cy][cx] = 0

while len(queue):
    while len(queue):
        y, x = queue.popleft()
        visited.append((y, x))
        cost = S[y][x]
        for i, j in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
            if not (0 <= i < H and 0 <= j < W):
                continue
            if S[i][j] == '.':
                S[i][j] = cost
                queue.append((i, j))

    while len(visited):
        y, x = visited.popleft()
        cost = S[y][x]
        for i in range(y-2, y+2+1):
            for j in range(x-2, x+2+1):
                if not (0 <= i < H and 0 <= j < W):
                    continue
                if S[i][j] == '.':
                    S[i][j] = cost+1
                    queue.append((i, j))

dy, dx = D
result = S[dy][dx]
if result == '.':
    print(-1)
else:
    print(result)

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())
maze=[]

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)

def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
l=[[Ch-1,Cw-1]]
l=deque(l)
maze[Ch-1][Cw-1]=0
l2=[[0]*W for i in range(H)]

cnt=0
while l:
  cnt+=1
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]

  target=l[0]
  h,w=target
  l.popleft()
  if l2[h][w]:
    continue
  l2[h][w]=1
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      l.appendleft([h+vector[0],w+vector[1]])
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      maze[h+i//5-2][w+i%5-2]=maze[h][w]+1
      l.append([h+i//5-2,w+i%5-2])
print(maze[Dh-1][Dw-1])