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 collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

# 時間制限Py厳しすぎませんか？E3ｓにする暇があったらこっちを3ｓにしましょうよ
def input(): return sys.stdin.readline().rstrip()


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

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0


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


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


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

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

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

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

Submission status: Time Limit Exceeded

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

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[int(ch == '#') for ch in input().rstrip()] for _ in range(H)]

from sys import exit
from collections import deque
from itertools import product
que = deque([c])
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()

        if maze[h][w]:
            continue

        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in que and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))

        for dh,dw in [
            [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
            [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
            [0,-2], [0, 2], 
            [1,-2], [1,-1], [1, 1], [1, 2], 
            [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
        ]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in nque and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))

        maze[h][w] = 1
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
adjacent = {}
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            adjacent[i, j] = []

for i in range(h):
    for j in range(w):
        if S[i, j] != '.':
            continue
        if i > 0 and S[i - 1, j] == '.' and (i-1, j) not in adjacent[i, j]:
            adjacent[i, j].append((i-1, j))
        if j > 0 and S[i , j - 1] == '.' and (i, j-1) not in adjacent[i, j]:
            adjacent[i, j].append((i, j-1))
        if i < h-1 and S[i + 1, j] == '.' and (i+1, j) not in adjacent[i, j]:
            adjacent[i, j].append((i+1, j))
        if j < w-1 and S[i, j+1] == '.' and (i, j+1) not in adjacent[i, j]:
            adjacent[i, j].append((i, j+1))

index = 0
section = {}
reached = {k: False for k in adjacent}

for p in adjacent:
    if reached[p]:
        continue
    else:
        reached[p] = True
        stack = [p]
        section[p] = index
        while stack:
            v = stack.pop()
            for u in adjacent[v]:
                if not reached[u]:
                    reached[u] = True
                    stack.append(u)
                    section[u] = index
        index += 1

#print(adjacent)
#print(section)
if section[c] == section[d]:
    print(0)
    exit(0)

vertex = range(index)
edges = {i: set() for i in vertex}
for i, j in adjacent:
    head = section[i, j]
    square = product(range(max(i-2, 0), min(i+3, h)), range(max(j-2, 0), min(j+3, w)))
    for m in square:
        if S[m] == '.':
            tail = section[m]
            if tail != head and S[m] == '.':
                edges[tail].add(head)
                edges[head].add(tail)

source = section[c]
target = section[d]
distance = {v: math.inf for v in vertex}
distance[source] = 0
reached_ = {k: False for k in vertex}
reached_[source] = True
queue = deque([source])
while queue:
    u = queue.popleft()
    for v in edges[u]:
        if not reached_[v]:
            reached_[v] = True
            distance[v] = distance[u] + 1
            queue.append(v)

if distance[target] != math.inf:
    print(distance[target])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map( int, input().split() )
c_h, c_w = map( int, input().split() )
c = ( c_h - 1 ) * w + ( c_w - 1 )
d_h, d_w = map( int, input().split() )
d = ( d_h - 1 ) * w + ( d_w - 1 )
s = []
for _ in range( h ):
    s_h = str( input() )
    # s.append( s_h )
    for s_h_w in s_h:
        s.append( s_h_w )

move_a = []
for i in range( h * w ):
    move_a_i = []
    if i % w > 0:
        if s[ i - 1 ] != "#":
            move_a_i.append( i - 1 )
    if i // w > 0:
        if s[ i - w ] != "#":
            move_a_i.append( i - w )
    if i % w < w - 1:
        if s[ i + 1 ] != "#":
            move_a_i.append( i + 1 )
    if i // w < h - 1:
        if s[ i + w ] != "#":
            move_a_i.append( i + w )
    move_a.append( move_a_i )

move_b = []
for i in range( h * w ):
    move_b_i = []
    if s[ i ] == "#":
        move_b.append( move_b_i )
        continue
    if i % w > 1:
        if s[ i - 2 ] != "#":
            move_b_i.append( i - 2 )
    if i % w > 0 and i // w > 0:
        if s[ i - 1 - w ] != "#":
            move_b_i.append( i - 1 - w )
    if i % w > 1 and i // w > 1:
        if s[ i - 2 - 2 * w ] != "#":
            move_b_i.append( i - 2 - 2 * w )
    if i // w > 1:
        if s[ i - 2 * w ] != "#":
            move_b_i.append( i - 2 * w )
    if i // w > 0 and i % w < w - 1:
        if s[ i - w + 1 ] != "#":
            move_b_i.append( i - w + 1 )
    if i // w > 1 and i % w < w - 2:
        if s[ i - 2 * w + 2 ] != "#":
            move_b_i.append( i - 2 * w + 2 )
    if i % w < w - 2:
        if s[ i + 2  ] != "#":
            move_b_i.append( i + 2 )
    if i % w < w - 1 and i // w < h - 1:
        if s[ i + 1 + w ] != "#":
            move_b_i.append( i + 1 + w )
    if i % w < w - 2 and i // w < h - 2:
        if s[ i + 2 + 2 * w  ] != "#":
            move_b_i.append( i + 2 + 2 * w )
    if i // w < h - 2:
        if s[ i + 2 * w  ] != "#":
            move_b_i.append( i + 2 * w )
    if i % w > 0 and i // w < h - 1:
        if s[ i + w - 1 ] != "#":
            move_b_i.append( i + w - 1 )
    if i % w > 1 and i // w < h - 2:
        if s[ i + 2 * w - 2  ] != "#":
            move_b_i.append( i + 2 * w - 2 )

    if i % w > 2 and i // w > 0:
        if s[ i - w - 2  ] != "#":
            move_b_i.append( i - w - 2 )
    if i % w > 1 and i // w > 1:
        if s[ i - 2 * w - 1  ] != "#":
            move_b_i.append( i - 2 * w - 1 )
    if i % w < w - 1 and i // w > 2:
        if s[ i - 2 * w + 1  ] != "#":
            move_b_i.append( i - 2 * w + 1 )
    if i % w < w - 2 and i // w > 1:
        if s[ i - w + 2 ] != "#":
            move_b_i.append( i - w + 2 )
    if i % w < w - 2 and i // w < h - 1:
        if s[ i + w + 2 ] != "#":
            move_b_i.append( i + w + 2 )
    if i % w < w - 1 and i // w < h - 2:
        if s[ i + 2 * w + 1 ] != "#":
            move_b_i.append( i + 2 * w + 1 )
    if i % w > 0 and i // w < h - 2:
        if s[ i + 2 * w - 1 ] != "#":
            move_b_i.append( i + 2 * w - 1 )
    if i % w > 1 and i // w < h - 1:
        if s[ i + w - 2 ] != "#":
            move_b_i.append( i + w - 2 )
    move_b.append( move_b_i )

from heapq import heappush, heappop
INF = 10 ** 10
VISITED = 1
NOT_VISITED = 0
      
cost = [ INF ] * ( h * w )
cost[ c ] = 0
visit = [ NOT_VISITED ] * ( h * w )
visit[ c ] = VISITED
queue = [ ( cost[ c ], c ) ]
while len( queue ) > 0:
    c, v = heappop( queue )
    visit[ v ] = VISITED
    for u in move_a[ v ]:
        if visit[ u ] == VISITED:
            continue
        if cost[ u ] > cost[ v ]:
            cost[ u ] = cost[ v ]
            heappush( queue, ( cost[ u ], u ) )
    for t in move_b[ v ]:
        if visit[ t ] == VISITED:
            continue
        if cost[ t ] > cost[ v ] + 1:
            cost[ t ] = cost[ v ] + 1
            heappush( queue, ( cost[ t ], t ) )

if cost[ d ] == INF:
    print( -1 )
else:
    print( cost[ d ] )

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

layer_set = set()
layer_set.add((ch-1,cw-1))
loop = 0
while used_map[dh-1][dw-1] == -1 and queue != []:
    #move walk
    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]
        layer_set.add((dot[1],dot[2]))

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

    temp = []
    for s in layer_set:
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                    if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == ".":
                        temp = [s[0]+x,s[1]+y]
                if temp != []:
                    break
            if temp != []:
                break
        if temp != []:
            break 
    if temp != []:
        heapq.heappush(queue,[loop+1,temp[0],temp[1]])
    loop+=1
    
print(used_map[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = ['*']*(W+4)
S[1] = ['*']*(W+4)
S[-2] = ['*']*(W+4)
S[-1] = ['*']*(W+4)
for h in range(2,H+2):
  S[h] = ['*']*2 + list(input()) + ['*']*2

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
S[gh][gw] = 'g'
d.append(g)

while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if S[h1][w1]=='.':
      S[h1][w1]='g'
      d.append(a1)

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if S[h1][w1]=='g':
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.append(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if S[h2][w2]=='g':
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

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

def main():
    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)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx in range(-2,3):
                for dy in range(-2,3):
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.' and (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x]
                    elif S[sy][sx] == '.' and (dx,dy) not in ((-1,0),(1,0),(0,-1),(0,1)):
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x] + 1
                    elif (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        if S[sy][sx] > S[y][x]:
                            S[sy][sx] = S[y][x]
                            que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# Date [ 2020-08-22 21:07:07 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit, u1

#@njit(i8(i8, i8, u1[:,:], i8[:], i8[:]), cache=True)
def search(h, w, grid, wiz, goal):
    visit = np.full((h, w), False, dtype=np.bool)
    
    visit[wiz[0] - 1][wiz[1] - 1] = True
    cnt = np.full((h, w), -1, dtype=np.int64)

    que = deque([[wiz[0] - 1, wiz[1] - 1]])
    cnt[wiz[0] - 1][wiz[1] - 1] = 0

    dx = np.array([1, 0, -1, 0],dtype=np.int64)
    dy = np.array([0, 1, 0, -1],dtype=np.int64)
    dx8 = np.array([0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1],dtype=np.int64)
    dy8 = np.array([2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2], dtype=np.int64)

    while que:
        y, x = que.popleft()
        if y == goal[0] - 1 and x == goal[1] - 1:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < w and 0 <= ny < h and grid[ny][nx] != '#' and (visit[ny][nx] == False or cnt[ny][nx] > -1):
                que.append([ny, nx])
                visit[ny][nx] = True
                cnt[ny][nx] = cnt[y][x]
            
            if 0 <= nx < w and 0 <= ny < h and grid[ny][nx] == '#':
                for i in range(16):
                    nx = x + dx8[i]
                    ny = y + dy8[i]
                    if 0 <= nx < w and 0 <= ny < h and grid[ny][nx] != '#' and visit[ny][nx] == False:
                        que.append([ny, nx])
                        visit[ny][nx] = True
                        cnt[ny][nx] = cnt[y][x] + 1

    return cnt[goal[0] - 1][goal[1] - 1]


def Main():
    H, W = read_ints()
    wiz = np.array(read_int_list(),dtype=np.int64)
    goal = np.array(read_int_list(),dtype=np.int64)
    grid = np.array([read_str() for _ in range(H)], dtype=np.str)
    
    print(search(H, W, grid, wiz, goal))


if __name__ ==  '__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

h,w=NM()
sh,sw=NM()
sh-=1
sw-=1
gh,gw=NM()
gh-=1
gw-=1
l=[[j for j in input()] for i in range(h)]
from collections import deque
def dijkstra(s,n,g):
    d = [float('inf') for i in range(n+1)]
    pq = deque([])
    d[s]=0
    pq.append((0,s))
    while pq:
        dist,u = pq.popleft()
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            pq.append((d[v],v))
    return d[g]
edge=[[] for i in range(h*w)]

def v(i,j):
    return (j*h+i)
def f(i,j,x,y):
    if x>=h or y>=w or x<0 or y<0:
        return
    if l[x][y]==".":
        edge[v(i,j)].append((v(x,y),1))
        edge[v(x,y)].append((v(i,j),1))
for x in range(h*w):
        i=x%h
        j=x//h
        if l[i][j]=="#":
            continue
        if i<h-1:
            if l[i+1][j]==".":
                edge[v(i,j)].append((v(i+1,j),0))
                edge[v(i+1,j)].append((v(i,j),0))
        if j<w-1:
            if l[i][j+1]==".":
                edge[v(i,j)].append((v(i,j+1),0))
                edge[v(i,j+1)].append((v(i,j),0))
        f(i,j,i+1,j+1)
        f(i,j,i+2,j+1)
        f(i,j,i+2,j+2)
        f(i,j,i+1,j+2)
        f(i,j,i+2,j)
        f(i,j,i,j+2)
        
        f(i,j,i-1,j+1)
        f(i,j,i-2,j+1)
        f(i,j,i-2,j+2)
        f(i,j,i-1,j+2)


d=dijkstra(v(sh,sw),h*w,v(gh,gw))
if d==float("inf"):
    print(-1)
else:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch, Cw = map(lambda x: int(x)-1,input().split())
Dh, Dw = map(lambda x: int(x)-1,input().split())
S = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = {}
  now = set()
  d[(sh,sw)]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and (nh,nw) not in d) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[(nh,nw)]=d[(h,w)]

    if queue: continue
    for h,w in now:
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and (nh,nw) not in d) == False: continue
          d[(nh,nw)]=d[(h,w)]+1
          queue.append((nh,nw))
    now = set()
    #print(queue)
  return d

d = bfs(Ch,Cw)
if (Dh,Dw) not in d: 
  print(-1)
  exit()
print(d[(Dh,Dw)])

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]

    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    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(dx,dy):
            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 lin[nx][ny] > lin[x][y]:
                    se.add((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        # 魔法の力をもってすれば行ける
        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 lin[nx][ny] > lin[x][y]+1:
                    se.add((nx,ny))
                    lin[nx][ny] = lin[x][y]+1

        que += se

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

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

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

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 dh, dw in nex:
        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+1])

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

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

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = ["" for _ in range(h)]
p = [[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si  
i = 0
flag = False
q = queue.Queue()
q.put((ch,cw))
p[ch][cw] = 0
l = [(ch,cw)]
while True:
  while not q.empty():
    j,k = q.get()
    if j == dh and k == dw:
      print(i)
      exit()
    p[j][k] = i
    for hi,wi in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            l.append((j+hi,k+wi))
  nl = []
  nla = nl.append
  for j,k in l:
    for hi,wi in [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]:
      if  0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            nla((j+hi,k+wi))
            p[j+hi][k+wi] = i+1
  if q.empty():
    print(-1)
    exit()
  l = nl
  i += 1

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = list(map(int,input().split(' ')))
sy,sx = list(map(int,input().split(' ')))
gy,gx = list(map(int,input().split(' ')))
maze = [[None]*w]*h
for i in range(h):
    maze[i] = list(input())

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

d = [[float("inf")] * w for i in range(h)]
warp = [[float("inf")] * w for i in range(h)]

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


que = deque([])

que.append((sy,sx))

d[sy][sx] = 0
warp[sy][sx] = 0


while que:
    p = que.popleft()

    if p[0] == gy and p[1] == gx:
        break

    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]

        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):

            que.append((ny, nx))

            if warp[p[0]][p[1]] < warp[ny][nx]:
                warp[ny][nx] = warp[p[0]][p[1]]
            d[ny][nx] = d[p[0]][p[1]] + 1
    for i in range(-2,3):
        for j in range(-2,3):
            ny = p[0]+i
            nx = p[1]+j
            if 0 <= nx < w and 0 <= ny < h:
                if not (i==0 and j==0) and not (i==-1 and j==0) and not (i==1 and j==0) and not (i==0 and j==-1) and not (i==0 and j==1):
                    if maze[ny][nx] != "#":
                        if d[ny][nx] == float("inf"):
                            que.append((ny, nx))
                            warp[ny][nx] = warp[p[0]][p[1]] + 1
                        if not d[ny][nx] == float("inf"):
                            if warp[p[0]][p[1]]+1 < warp[ny][nx]:
                                warp[ny][nx] = warp[p[0]][p[1]] + 1
                                que.append((ny, nx))
if not warp[gy][gx] == float("inf"):
    print(warp[gy][gx])
else:
    print(-1)