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: Accepted

Solution code:
import queue
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
graphlist = []
replacelist = []
grapht = [[-1 for i in range(w+2)] for i in range(h+2)]
meiro = [["#" for i in range(w+2)]]+[["#"]+list(input())+["#"] for i in range(h)]+[["#" for i in range(w+2)]]
lastnum=[0]
donelist = set()
for i in range(1, h+1):
    for j in range(1, w+1):
        if(meiro[i][j] == "."):
            if(grapht[i-1][j] != -1):
                grapht[i][j] = grapht[i-1][j]
            elif(grapht[i][j-1] != -1):
                grapht[i][j] = grapht[i][j-1]
            elif(grapht[i+1][j] != -1):
                grapht[i][j] = grapht[i+1][j]
            elif(grapht[i][j+1] != -1):
                grapht[i][j] = grapht[i][j+1]
            else:
                grapht[i][j] = lastnum
                graphlist.append(set())
                replacelist.append([])
                lastnum = [lastnum[0] + 1]
            if(meiro[i+1][j] == "."):
                grapht[i+1][j] = grapht[i][j]
            if(meiro[i][j+1] == "."):
                if(grapht[i][j+1] == -1):
                    grapht[i][j+1] = grapht[i][j]
                elif(grapht[i][j][0] != grapht[i][j+1][0]):
                        donelist.add(grapht[i][j+1][0])
                        graphlist[grapht[i][j][0]] = graphlist[grapht[i][j][0]] | (graphlist[grapht[i][j+1][0]] - set(grapht[i][j]))
                        for k in graphlist[grapht[i][j+1][0]]:
                            graphlist[k].add(grapht[i][j][0])
                        for k, l in replacelist[grapht[i][j+1][0]]:
                            grapht[k][l][0] = grapht[i][j][0]
                            replacelist[grapht[i][j][0]].append((k, l))
                        grapht[i][j+1][0] = grapht[i][j][0]
                        replacelist[grapht[i][j][0]].append((i,j+1))
                        replacelist[grapht[i][j][0]].append((i,j))
            for k in range(i-2, i+3):
                if(k >= h+1):
                    continue
                for l in range(j-2, j+3):
                    if(l >= w+1):
                        continue
                    if(grapht[k][l] != -1 and grapht[k][l] != grapht[i][j]):
                        graphlist[grapht[i][j][0]].add(grapht[k][l][0])
                        graphlist[grapht[k][l][0]].add(grapht[i][j][0])
start = grapht[ch][cw][0]
end = grapht[dh][dw][0]
nextlist = queue.Queue()
depthlist = [-1]*len(graphlist)
donelist.add(start)
depthlist[start] = 0
while True:
    for i in graphlist[start]:
        if(i not in donelist):
            nextlist.put(i)
            depthlist[i] = depthlist[start]+1
            donelist.add(i)
    if(nextlist.empty()):
        break
    start = nextlist.get()
#import pprint        
#pprint.pprint(grapht)
#print(graphlist)
print(depthlist[end])

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

h,w=map(int,input().split())
sx,sy=map(int,input().split()) ; sx-=1;sy-=1
gx,gy=map(int,input().split()) ;gx-=1;gy-=1

A=[]
for i in range(h):
    A.append(list(input()))

dp=[[10**6]*w for i in range(h)]
dp[sx][sy]=0
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def warp(x,y):
    r=[]    
    for i in range(x-2,x+3):
        for j in range(y-2,y+3):
            if 0<=i<h and 0<=j<w:
                if not (i==x and j==y):
                    if A[i][j]==".":
                        r.append([i,j])
    return r

queue=deque([[sx,sy]])
while queue:
    x,y=queue.pop()
    for i,j in zip(dx,dy):
        if 0<=x+i<h and 0<=y+j<w and dp[x+i][y+j]>dp[x][y] and A[x+i][y+j]==".":
            dp[x+i][y+j]= dp[x][y]
            queue.append([x+i,y+j])
    for a,b in warp(x,y):
        if dp[a][b]>dp[x][y]+1:
            dp[a][b]= dp[x][y]+1
            queue.appendleft([a,b])

print(dp[gx][gy] if dp[gx][gy]!=10**6 else -1)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    warpq = []
    while q:
        while q:
            warpq.append(q[0])
            h, w = q.popleft()
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    warpq = []
    while q:
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Accepted

Solution code:
import sys, math, heapq

def move2(Maps, dists, start, goal, inf):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    queue = []
    heapq.heappush(queue, [0, start[1], start[0]]) # x, y

    while( len(queue) >0 ):
        dist_pos = heapq.heappop(queue)

        dist, x, y = map(int, dist_pos)
        if(dists[y][x] < dist_pos[0]):
            continue
        if(x == goal[1] and y == goal[0]):
            print(dists[y][x])
            return
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)




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() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    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()
    """
    Maps = [ ]
    for i in range(H):
        Maps.append( input().strip() )
    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]

    move2(Maps, dists, start, goal, inf)

Submission status: Accepted

Solution code:
import sys, math, heapq

def move2(Maps, dists, start, goal, inf):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    queue = []
    heapq.heappush(queue, [0, start[1], start[0]]) # x, y

    while( len(queue) >0 ):
        dist_pos = heapq.heappop(queue)

        dist, x, y = map(int, dist_pos)
        if(dists[y][x] < dist_pos[0]):
            continue
        if(x == goal[1] and y == goal[0]):
            print(dists[y][x])
            return
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)




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() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    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()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]

    move2(Maps, dists, start, goal, inf)

Submission status: Accepted

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "is_unsearched", "is_unreachable", "dist"]

    def __init__(
        self, height: int, width: int, grid: List[bytes], road: str = ".",
    ) -> None:
        self.height = height + 4
        self.width = width + 4
        self.is_unsearched = 1 << 30
        self.is_unreachable = -1
        self.dist = self._convert_grid_to_dist(grid, road)

    def _convert_grid_to_dist(self, grid: List[bytes], road: str) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.is_unreachable] * self.height * self.width
        i = self.width * 2 + 1
        for row in grid:
            for c in row.decode():
                i += 1
                if c == road:
                    dist[i] = self.is_unsearched
            i += 4
        return dist

    def _flatten_coordinate(self, x: int, y: int) -> int:
        """Flatten 2D coordinate values.
        Values of a coordinate must be 1-origin.
        """
        return self.width * (x + 1) + y + 1

    def bfs(self, start_2d: Tuple[int, int], goal_2d: Tuple[int, int]) -> int:
        """BFS to compute the distance from start to goal.
        Values of start_2d and goal_2d must be 1-origin.
        """
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        w = self.width
        walk_to_warp = {
            -w: (-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -w - 1),
            w: (w + 1, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2),
            -1: (-w - 2, -2, w - 2, w - 1, 2 * w - 2),
            1: (-w + 1, -2 * w + 2, -w + 2, 2, w + 2),
        }

        dist = self.dist[:]
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for walk, warp in walk_to_warp.items():
                nx = x + walk
                if dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)
                    continue
                if dist[nx] >= 0:
                    continue

                for dx in warp:
                    nx = x + dx
                    if dist[nx] > cur_dist + 1:
                        dist[nx] = cur_dist + 1
                        queue.append(nx)

        return dist[goal] if dist[goal] != self.is_unsearched else self.is_unreachable


def main():
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    (*start,) = map(int, readline().split())
    (*goal,) = map(int, readline().split())
    (*S,) = read().split()

    maze = WarpableMaze(H, W, S)
    print(maze.bfs(start, goal))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import*
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
d=eval('[-1]*w,input(),'*h)
q=deque([(s-1,t-1,0)])
while q:
 y,x,c=q.pop()
 if d[y+y][x]<0:
  for a in range(25):a,b=a//5-2,a%5-2;i=a+y;j=b+x;d[y+y][x]=c;h>i>-1<j<w!=d[i-~i][j]>'#'!=(abs(a)+abs(b)<2!=q.append((i,j,c)),q.appendleft((i,j,c+1)))
print(d[f+f-2][g-1])

Submission status: Accepted

Solution code:
from collections import deque
def good(x,y):
    if (x>=0 and x<h) and (y>=0 and y<w):
        return (mat[x][y] != "#")
h, w = map(int,input().split())
sh, sw = map(int,input().split())
eh, ew = map(int,input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)
x = [1,-1,0,0]
y = [0,0,-1,1]
dist = [[float('inf') for i in range(w)]for j in range(h)]
sh -= 1
sw -= 1
eh -= 1
ew -= 1
dist[sh][sw] = 0
queue = deque()
queue.appendleft((sh,sw))
while queue:
    m = queue.popleft()
    for d in range(4):
        nx = m[0] + x[d]
        ny = m[1] + y[d]
        if good(nx,ny):
            if dist[nx][ny] > dist[m[0]][m[1]]:
                dist[nx][ny] =  dist[m[0]][m[1]]
                queue.appendleft((nx,ny))
    for i in range(m[0]-2,m[0]+3):
        for j in range(m[1]-2,m[1]+3):
            if good(i,j):
                if dist[i][j] > dist[m[0]][m[1]] + 1:
                    dist[i][j] = dist[m[0]][m[1]] + 1
                    queue.append((i,j))
if dist[eh][ew] == float('inf'):
    print(-1)
else:
    print(dist[eh][ew])

Submission status: Accepted

Solution code:
import zlib,base64
exec(zlib.decompress(base64.b85decode("c-l2k%Wi`(5WMphj;e}XSdx$`mw@vl76$_+EaG9nDM`P+j+!2JMw*?~Xtr6VK~z)Uo67Mtu7U?UEiMY6r40#IavmGHp)}vRhj7pqcyz?0y*t4DYJ2vK6h>bd3{=Y>wh;Z9;q4-oq(!v7Of6zC%i7F$0}9q8CFkde1qNHoy%F;z5KnqgCFi}JEMOqG5w&_2>QUrJzZK222rYONiym(VPG`JmDy2Rg&dG`Nr^k$?j-Od4%lMJKk7bp$SH31`-sRg)4vGua71!`1+)2>o3L4`Vm6)G)K3!XD#u|XBqslk@S9;U9w;HGD``E>Q1Zvgzmg?pKe*wqdW>^")))

Submission status: Accepted

Solution code:
from collections import*
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[-1]*w),'*h))
q=deque([(s-1,t-1,0)])
while q:
 y,x,c=q.pop()
 if d[y][x]<0:
  for a in range(25):a,b=a//5-2,a%5-2;i=a+y;j=b+x;d[y][x]=c;h>i>-1<j<w!=m[i][j]>'#'!=(abs(a)+abs(b)<2!=q.append((i,j,c)),q.appendleft((i,j,c+1)))
print(d[f-1][g-1])

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.pop()
 if d[y][x]>c:
  for a in range(25):a,b=a//5-2,a%5-2;i=a+y;j=b+x;d[y][x]=c;h>i>-1<j<w!=m[i][j]>'#'!=(abs(a)+abs(b)<2!=q.append((i,j,c)),q.appendleft((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  for a in range(25):a,b=a//5-2,a%5-2;i=a+y;j=b+x;d[y][x]=c;h>i>-1<j<w!=m[i][j]>'#'!=(abs(a)+abs(b)<2!=q.appendleft((i,j,c)),q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
r=range(-2,3)
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  for a in r:
    for b in r:i=a+y;j=b+x;d[y][x]=c;h>i>-1<j<w!=m[i][j]>'#'!=(abs(a)+abs(b)<2!=q.appendleft((i,j,c)),q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(input()) for _ in range(H)]

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

que = deque([(Ch-1, Cw-1, 0)])
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
while que:
    ci, cj, d = que.popleft()

    if visited[ci][cj] != -1:
        continue
    visited[ci][cj] = d

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
            continue
        if S[ni][nj] == '.':
            que.appendleft((ni, nj, d))

    for di in range(-2, 3):
        for dj in range(-2, 3):
            ni, nj = ci+di, cj+dj
            if not (0 <= ni < H and 0 <= nj < W)  \
                    or visited[ni][nj] != -1:
                continue
            if S[ni][nj] == '.':
                que.append((ni, nj, d+1))
    # print(visited)
    # exit()

if visited[Dh-1][Dw-1] == -1:
    print(-1)
else:
    print(visited[Dh-1][Dw-1])

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):d[y][x]=c;h>i>-1<j<w!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c)),q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):d[y][x]=c;h>i>-1<j<w!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c))or q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):d[y][x]=c;h>i>-1<j<w<d[i][j]!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c))or q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  d[y][x]=c
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):h>i>-1<j<w<d[i][j]!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c))or q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  d[y][x]=c
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c))or q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  d[y][x]=c
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#':
     if abs(y-i)+abs(x-j)<2:q.appendleft((i,j,c))
     else:q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
from collections import*
e=eval
I=9**9
(h,w),(s,t),(f,g)=e('map(int,input().split()),'*3)
m=e('input(),'*h)
d=e('[I]*w,'*h)
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  d[y][x]=c
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#':
     if abs(y-i)+abs(x-j)<2:q.appendleft((i,j,c))
     else:q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
INF=10**6
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
dh,dw=f()
g=[input() for _ in range(h)]
d=[[INF]*w for _ in range(h)]
from collections import *
q=deque([(0,ch-1,cw-1)])
while q:
  c,x,y=q.popleft()
  if d[x][y]<=c: continue
  d[x][y]=c
  for dx in range(-2,3):
    for dy in range(-2,3):
      j=abs(dx)+abs(dy)
      nx,ny=x+dx,y+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and j:
        if j>1: q.append((c+1,nx,ny))
        else: q.appendleft((c,nx,ny))
a=d[dh-1][dw-1]
print([-1,a][a<INF])

Submission status: Accepted

Solution code:
INF=10**6
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
dh,dw=f()
ch-=1
cw-=1
dh-=1
dw-=1
g=[input() for _ in range(h)]
from collections import *
d=[[INF]*w for _ in range(h)]
q=deque([(0,ch,cw)])
while q:
  td,tx,ty=q.popleft()
  if d[tx][ty]<=td: continue
  d[tx][ty]=td
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.':
      q.appendleft((td,nx,ny))
  for dx in range(-2,3):
    for dy in range(-2,3):
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.':
        q.append((td+1,nx,ny))
a=d[dh][dw]
print([-1,a][a<INF])

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[w*[I]for _ in m]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i in range(y-2,y+3):
    for j in range(x-2,x+3):
      if h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#':
        if abs(y-i)+abs(x-j)<2:q.appendleft((i,j,c))
        else:q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
dh,dw=f()
g=[[*input()] for _ in range(h)]
from collections import *
q=deque([(0,ch-1,cw-1)])
while q:
  d,x,y=q.popleft()
  if g[x][y]!='.': continue
  g[x][y]=d
  for dx in range(-2,3):
    for dy in range(-2,3):
      j=abs(dx)+abs(dy)
      nx,ny=x+dx,y+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and j:
        if j>1: q.append((d+1,nx,ny))
        else: q.appendleft((d,nx,ny))
a=g[dh-1][dw-1]
print([a,-1][a=='.'])

Submission status: Accepted

Solution code:
from collections import deque
import copy

h,w=map(int,input().split())
cy,cx=map(int,input().split())
gy,gx=map(int,input().split())
inf=float('inf')
maze=[]
for _ in range(h):
  s=list(input())
  for i in range(w):
    if s[i]=='.':
      s[i]=inf
  maze.append(s)
  
def solve(maze,cy,cx,gy,gx):
  maze1=copy.deepcopy(maze)
  [sy,sx]=[cy-1,cx-1]
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  T=0
  while qu:
    y,x=qu.popleft()
    t=maze[y][x]
    
    if maze1[y][x]!=1:
      
      for i in ([1,0],[0,1],[-1,0],[0,-1]):
        ny=y-i[0]
        nx=x-i[1]
        if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
          if maze[ny][nx]>t:
            maze[ny][nx]=t
            qu.appendleft([ny,nx])
          
      
      for j in range(-2,3):
        for k in range(-2,3):
          ny=y-j
          nx=x-k
          if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
            if maze[ny][nx]>t:
              maze[ny][nx]=t+1
              qu.append([ny,nx])
      maze1[y][x]=1
            
  return maze[gy-1][gx-1]
  
if solve(maze,cy,cx,gy,gx)==inf:
  print(-1)
  
else:
  print(solve(maze,cy,cx,gy,gx))