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 sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
from itertools import product
def resolve():
    m, n = map(int, input().split())
    si, sj = map(lambda x : int(x) - 1, input().split())
    ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    queue = deque([(si, sj)])
    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in product(range(-2, 3), repeat = 2):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if not (0 <= ni < m and 0 <= nj < n):
                continue
            if grid[ni][nj] == '#':
                continue
            dd = int(abs(di) + abs(dj) > 1)
            nd = dist[i][j] + dd
            if nd < dist[ni][nj]:
                dist[ni][nj] = nd
                if dd == 0:
                    queue.appendleft((ni, nj))
                else:
                    queue.append((ni, nj))


    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]

visited = [[-1] * W for i in range(H)]
visited[Ch - 1][Cw - 1] = 0
h = [(Ch - 1, Cw - 1)]
c = 0
while True :
  done = []
  while h :
    cy, cx = h.pop()
    done.append((cy, cx))
    visited[cy][cx] = c
    for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
      ny, nx = cy + dy, cx + dx
      if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.' and visited[ny][nx] == -1 :
        h.append((ny, nx))
        visited[ny][nx] = c

  h = []
  for cy, cx in done :
    for dy in range(-2, 3) :
      for dx in range(-2, 3) :
        ny, nx = cy + dy, cx + dx
        if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.' and visited[ny][nx] == -1 :
          h.append((ny, nx))
  if not h :
    break
  c += 1  
  
print(visited[Dh - 1][Dw - 1])

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    sh, sw = map(lambda x: int(x) - 1, input().split())
    gh, gw = map(lambda x: int(x) - 1, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]

    maze = [[f_inf] * W for _ in range(H)]
    maze[sh][sw] = 0
    que = deque([[sh, sw]])
    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if grid[next_h][next_w] == ".":
                if maze[next_h][next_w] > maze[h][w]:
                    maze[next_h][next_w] = maze[h][w]
                    que.appendleft([next_h, next_w])
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                if grid[next_h][next_w] == ".":
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
    print(maze[gh][gw] if maze[gh][gw] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())
si, sj, gi, gj = si+1, sj+1, gi+1, gj+1
X = [[1] * (W + 4)] * 2 + [[1] * 2 + [1 if a == "#" else 0for a in input()] + [1] * 2 for _ in range(H)] + [[1] * (W + 4)] * 2
H += 4
W += 4

Y = [(-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)]
Z = [(-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)]

def BFS():
    Q = deque([(si, sj)])
    D = [-1] * (H * W)
    D[si*W + sj] = 0
    while Q:
        i, j = Q.popleft()
        x = i * W + j
        for di, dj in Y:
            ni, nj = i+di, j+dj
            y = ni * W + nj
            if X[ni][nj] == 0:
                if D[y] == -1 or D[y] > D[x]:
                    D[y] = D[x]
                    Q.appendleft((ni, nj))
        for di, dj in Z:
            ni, nj = i+di, j+dj
            y = ni * W + nj
            if X[ni][nj] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append((ni, nj))
    return D[gi * W + gj]

print(BFS())

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque

R, C = [int(x) for x in input().split()]
source = tuple([int(x) - 1 for x in input().split()])  # 0 indexed
dest = tuple([int(x) - 1 for x in input().split()])  # 0 indexed
grid = [input() for r in range(R)]


drdc = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def getNbrGrid(node):
    r, c = node
    for dr, dc in drdc:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
            yield nr, nc



def bfs(source, getNbr):
    q = deque([source])
    dist = {source: 0}
    while q:
        node = q.popleft()
        d = dist[node]
        for nbr in getNbr(node):
            if nbr not in dist:
                q.append(nbr)
                dist[nbr] = d + 1
    return dist


numComps = 0
compId = {}
for r in range(R):
    for c in range(C):
        if grid[r][c] != "#" and (r, c) not in compId:
            dist = bfs((r, c), getNbrGrid)
            for node in dist:
                compId[node] = numComps
            numComps += 1

if False:
    for r in range(R):
        for c in range(C):
            print(str(compId.get((r, c), ' ')).rjust(3), end="")
        print()

graph = defaultdict(set)
for r in range(R):
    for c in range(C):
        if grid[r][c] != '#':
            comp1 = compId[(r, c)]
            for dr in range(-2, 3):
                for dc in range(-2, 3):
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
                        comp2 = compId[(nr, nc)]
                        graph[comp1].add(comp2)

def getNbrComp(node):
    return graph[node]


if source not in compId or dest not in compId:
    print(-1)
    exit()
sourceComp = compId[source]
destComp = compId[dest]
dist = bfs(sourceComp, getNbrComp)
if destComp not in dist:
    print(-1)
    exit()
print(dist[destComp])

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 19 + 7
EPS = 10 ** -10

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            nh = h + dh
            nw = w + dw
            if grid[nh][nw] == '#':
                continue
            if dist[nh][nw] <= dist[h][w]:
                continue
            dist[nh][nw] = dist[h][w]
            que.appendleft((nh, nw))
        for nh in range(h-2, h+3):
            if nh < 0 or nh >= H:
                continue
            for nw in range(w-2, w+3):
                if nw < 0 or nw >= W:
                    continue
                if grid[nh][nw] == '#':
                    continue
                if dist[nh][nw] <= dist[h][w] + 1:
                    continue
                dist[nh][nw] = dist[h][w] + 1
                que.append((nh, nw))
    return dist

H, W = MAP()
sh, sw = MAP()
th, tw = MAP()
grid = build_grid(H, W, '#', str, space=0, padding=1)

res = bfs(grid, [(sh, sw)])
ans = res[th][tw]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    s = [input().replace("\n", "") for _ in range(h)]
    
    ans = [[-1]*w for _ in range(h)]
    ans[ch-1][cw-1] = 0
    not_yet = deque([(ch-1, cw-1)])
    one_time = deque([])
    while not_yet:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        if x > 0 and ans[x-1][y] == -1 and s[x-1][y] == ".":
            not_yet.append((x-1, y))
            ans[x-1][y] = ans[x][y]
        if x < h-1 and ans[x+1][y] == -1 and s[x+1][y] == ".":
            not_yet.append((x+1, y))
            ans[x+1][y] = ans[x][y]
        if y > 0 and ans[x][y-1] == -1 and s[x][y-1] == ".":
            not_yet.append((x, y-1))
            ans[x][y-1] = ans[x][y]
        if y < w-1 and ans[x][y+1] == -1 and s[x][y+1] == ".":
            not_yet.append((x, y+1))
            ans[x][y+1] = ans[x][y]
        if not not_yet:
            while one_time:
                x2, y2 = one_time.popleft()
                for i in range(max(0, x2-2), min(h, x2+3)):
                    for j in range(max(0, y2-2), min(w, y2+3)):
                        if ans[i][j] == -1 and s[i][j] == ".":
                            ans[i][j] = ans[x][y]+1
                            not_yet.append((i, j))

    print(ans[dh-1][dw-1])
            
            
            
        
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF=float('inf')
from collections import deque
def mbfs(G,sh,sw,H,W):
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='#'):
                continue
            if dist[nh][nw]>dist[h][w]:
                dist[nh][nw]=dist[h][w]
                d.appendleft([nh,nw])
        for i in range(h-2,h+3):
            for j in range(w-2,w+3):
                if (i>H-1 or i<0 or j>W-1 or j<0):
                    continue
                if (G[i][j]=='#'):
                    continue
                if dist[i][j]>dist[h][w]+1:
                    dist[i][j]=dist[h][w]+1
                    d.append([i,j])
    return dist

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())
G=[list(input()) for i in range(H)]

dist=mbfs(G,Ch,Cw,H,W)
if dist[Dh][Dw]!=INF:
    print(dist[Dh][Dw])
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    h, w = mi()
    ch, cw = mi_0()
    dh, dw = mi_0()
    grid = [input() for _ in range(h)]
    d = ((-1, 0), (1, 0), (0, 1), (0, -1))

    def bfs(start):
        q = deque()
        q.append((start, 0))    # point, 魔法使用回数
        visited = [[False] * w for _ in range(h)]
        while q:
            point, num = q.popleft()
            ux, uy = point
            # print(f'{ux} {uy} {num}')
            if ux == dh and uy == dw:
                return num
            if not visited[ux][uy]:
                visited[ux][uy] = True
                for dx, dy in d:
                    nx, ny = ux + dx, uy + dy
                    if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == '.' and not visited[nx][ny]:
                        q.appendleft(((nx, ny), num))    # move
                for dx in range(-2, 3):
                    for dy in range(-2, 3):
                        if dx == 0 and dy == 0:
                            continue
                        nx, ny = ux + dx, uy + dy
                        if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == '.' and not visited[nx][ny]:
                            q.append(((nx, ny), num + 1))    # warp
        return -1
    
    start = (ch, cw)
    print(bfs(start))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 1,0-bfs?
from collections import deque

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

S = [list(input()) for _ in range(h)]
walk = [[False] * (w) for _ in range(h)]
jump = [[False] * (w) for _ in range(h)]
# S[h][w]

que = deque([])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que.append((sx, sy, 0))
walk[sx][sy] = True
jump[sx][sy] = True

ans = -1
while que:
    nowx, nowy, times = que.popleft()
    if nowx == gx and nowy == gy:
        ans = times
        break
    for i in range(4):
        nx = nowx + dx[i]
        ny = nowy + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if walk[nx][ny]:
            continue
        if S[nx][ny] == ".":
            walk[nx][ny] = True
            que.appendleft((nx, ny, times))
    for ddx in range(5):
        for ddy in range(5):
            nx = nowx + ddx - 2
            ny = nowy + ddy - 2
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if jump[nx][ny]:
                continue
            if S[nx][ny] == ".":
                jump[nx][ny] = True
                que.append((nx, ny, times + 1))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(input() for i in range(H)) #改行行列
    ch-=1;cw-=1;dw-=1;dh-=1
    N=H*W
    def dfs(start,goal):
        q=deque([(start,0)])
        visited=[-1]*N
        while len(q):
            e,d=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
            
            if e==goal:
                return d
            if visited[e]!=-1:continue
            
            cx,cy=divmod(e,W)

            visited[e]=d
            for dx,dy in ((-1,0),(1,0),(0,1),(0,-1)):
                if 0<=cx+dx<H and 0<=cy+dy<W and S[cx+dx][cy+dy]==".":
                    ne=(cx+dx)*W+cy+dy
                    q.appendleft((ne,d))
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if 0<=cx+dx<H and 0<=cy+dy<W and S[cx+dx][cy+dy]==".":
                        ne=(cx+dx)*W+cy+dy
                        q.append((ne,d+1))
        return -1
    print(dfs(ch*W+cw,dh*W+dw))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy,sx = sy-1,sx-1
gy,gx = gy-1,gx-1
S = [input() for i in range(H)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx+sy*W)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    y,x = divmod(v,W)
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '#': continue
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx+ny*W))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx+ny*W))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])

Submission status: Accepted

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


d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
d_ = [-2, -1, 0, 1, 2]


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 6

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
visited = [[INF] * w for i in range(h)]

visited[ch][cw] = 0
val = 0
q = deque([(ch, cw, val)])
while q:
    i, j, val = q.popleft()
    if val > visited[i][j]:
        continue
    val = visited[i][j]

    for di, dj in d:
        nxt_i, nxt_j = i + di, j + dj
        if not(0 <= nxt_i < h and 0 <= nxt_j < w):
            continue
        elif s[nxt_i][nxt_j] == "#":
            continue
        elif visited[nxt_i][nxt_j] > val:
                visited[nxt_i][nxt_j] = val
                q.appendleft((nxt_i, nxt_j, val))

    for di in d_:
        for dj in d_:
            nxt_i, nxt_j = i + di, j + dj
            if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                continue
            elif s[nxt_i][nxt_j] == "#":
                continue
            elif visited[nxt_i][nxt_j] > val + 1:
                visited[nxt_i][nxt_j] = val + 1
                q.append((nxt_i, nxt_j, val + 1))

if visited[dh][dw] == INF:
    print(-1)
else:
    print(visited[dh][dw])

Submission status: Accepted

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

d = [[10**20]*w for i in range(h)]

dq = deque([(ch-1,cw-1,0)])
d[ch-1][cw-1] = 0
dx = [0,-1,0,1]
dy = [-1,0,1,0]

while dq:
    nx,ny,nd = dq.popleft()
    if nd < d[nx][ny]:continue
    for delta in range(4):
        tx,ty = nx+dx[delta], ny + dy[delta]
        if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]:
            d[tx][ty] = d[nx][ny]
            dq.appendleft((tx,ty,d[tx][ty]))
    for deltax in range(-2,3):
        for deltay in range(-2,3):
            tx,ty = nx+deltax, ny + deltay
            if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]+1:
                d[tx][ty] = d[nx][ny] + 1
                dq.append((tx,ty,d[tx][ty]))

print(d[dh-1][dw-1] if d[dh-1][dw-1] != 10**20 else -1)

Submission status: Accepted

Solution code:
from collections import deque
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 = [input() for _ in range(h)]
vis = [[False] * w for _ in range(h)]
a = [[0] * w for _ in range(h)]
def bfsA(x, y, ai):
    q = deque()
    vis[x][y] = True
    a[x][y] = ai
    q.append((x, y))
    while q:
        u, v = q.popleft()
        for du, dv in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            uu = u + du
            vv = v + dv
            if 0 <= uu < h and 0 <= vv < w and not vis[uu][vv] and s[uu][vv] == '.':
                vis[uu][vv] = True
                a[uu][vv] = ai
                q.append((uu, vv))
c = 0
for x in range(h):
    for y in range(w):
        if vis[x][y] or s[x][y] == '#':
            continue
        c += 1
        bfsA(x, y, c)
e = [[] for _ in range(c + 3)]
for x in range(h):
    for y in range(w):
        if not vis[x][y] or s[x][y] == '#':
            continue
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx = x + dx
                yy = y + dy
                if 0 <= xx < h and 0 <= yy < w and vis[xx][yy] and s[xx][yy] == '.':
                    e[a[x][y]].append(a[xx][yy])
                    e[a[xx][yy]].append(a[x][y])
vis = [False] * (c + 3)
d = [h * w * 2] * (c + 3)
def bfsB(st):
    q = deque()
    vis[st] = True
    d[st] = 0
    q.append(st)
    while q:
        u = q.popleft()
        for v in e[u]:
            if not vis[v]:
                vis[v] = True
                d[v] = d[u] + 1
                q.append(v)
bfsB(a[ch][cw])
if d[a[dh][dw]] < h * w * 2:
    print(d[a[dh][dw]])
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
from collections import deque

H,W=map(int,input().split())
sy,sx=map(int1,input().split())
gy,gx=map(int1,input().split())
S=[input() for _ in range(H)]
used=[[False]*W for _ in range(H)]
que=deque([(sy,sx)])
dy,dx=(1,0,-1,0),(0,1,0,-1)
for ans in range(10**6):
    warp=set()
    if not que:
        print(-1)
        exit()
    while que:
        y,x=que.popleft()
        if not used[y][x]:
            used[y][x]=True
            for k in range(4):
                ny,nx=y+dy[k],x+dx[k]
                if 0<=ny<H and 0<=nx<W and not used[ny][nx]:
                    if S[ny][nx]=='.':
                        que.append((ny,nx))
                    else:
                        warp.add((y,x))
    if used[gy][gx]:
        print(ans)
        exit()
    for y,x in warp:
        for i in range(-2,3):
            for j in range(-2,3):
                ny,nx=y+i,x+j
                if not (i==j==0) and 0<=ny<H and 0<=nx<W and not used[ny][nx] and S[ny][nx]=='.':
                    que.append((ny,nx))