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
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        # print(warp)
        d = deque()
        wd = deque()
        self.set(start[1], start[0], 0)
        d.append((0, cx, cy))
        while (d or wd):
            # print(len(d), len(wd))
            if d:
                cc, cx, cy = d.popleft()
            else:
                cc, cx, cy = wd.popleft()
            # print(cc, cx, cy)
            if self.get(cx, cy) < cc:
                continue
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    d.append((cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    wd.append((cc + 1, nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return





def solve():
    h, w = getList()
    start = getList()
    goal = getList()
    G = TwoDimGrid(h, w)
    G.search(start, goal)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
h, w = (int(x) for x in input().split())
ch, cw = (int(x) for x in input().split())
dh, dw = (int(x) for x in input().split())
ch-=1
cw-=1
dh-=1
dw-=1
directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
directions_warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, 2], [0, -2], [0, 2], [1, -2], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2], [-1, -1], [1, 1], [-1, 1], [1, -1]]
s = []
for i in range(h):
    sh = input()
    s.append(sh)
gone = [[-1]*w for i in range(h)]
que = deque([[ch, cw]])
gone[ch][cw]=0
boo = True
count = 0
while boo ==True:
    now = []
    while que:
        nh, nw = que.pop()
        now.append((nh, nw))
        for gh, gw in directions:
            if nh+gh<0 or nh+gh>=h or nw+gw<0 or nw+gw>=w:
                pass
            elif gone[nh+gh][nw+gw]==0:
                pass
            else:
                if s[nh+gh][nw+gw]=="#":
                    pass
                else:
                    now.append((nh+gh, nw+gw))
                    gone[nh+gh][nw+gw]=0
                    que.appendleft([nh+gh, nw+gw])
    if gone[dh][dw]==0:
        print(count)
        break
    boo2 = False
    for nh, nw in now:
        for gh, gw in directions_warp:
            if nh+gh<0 or nh+gh>=h or nw+gw<0 or nw+gw>=w:
                pass
            else:
                if s[nh+gh][nw+gw]=="#":
                    pass
                elif gone[nh+gh][nw+gw]==0:
                    pass
                else:
                    boo2 = True
                    gone[nh+gh][nw+gw]=0
                    que.appendleft([nh+gh, nw+gw])
    if boo2 == False:
        print(-1)
        break
    count+=1

Submission status: Accepted

Solution code:
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
tmp=False
check=deque()

M=[[0 if j=='.' else 1 for j in input()]for i in range(H)]

# 0通路 1壁 2確認済み

ans=0
check.append([Sx,Sy])
while True:
    hit=set()
    while check:
        x,y = check.pop()
        #goul
        if x==Gx and y==Gy:
            tmp=True
            break
        M[x][y]=2
        #壁があるか
        for dx,dy in [ [x+1,y],[x-1,y],[x,y-1],[x,y+1] ]:
            if not(0<=dx and dx<H and 0<=dy and dy<W):
                continue
            if M[dx][dy]==1:
                hit.add((x,y))
            if M[dx][dy]==0:
                check.append([dx,dy])
    if tmp:
        print(ans)
        break
    if len(hit)==0:
        print(-1)
        break
    for e in hit:
        x,y=e
        for i in range(-2,3):
            for j in range(-2,3):
                if 0<=x+i and x+i<H and 0<=y+j and y+j<W and M[x+i][y+j]==0:
                    check.append([x+i,y+j])
    if len(check)==0:
        print(-1)
        break

    ans+=1

Submission status: Accepted

Solution code:
from __future__ import  print_function
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    num = 0
    visited = set()
    stack = []
    for i in range(h):
        for j in range(w):
            if (not s[i][j] == "#") and (not i*h + j in visited):
                visited.add(i*h + j)
                who[i][j] = num
                stack.append((i,j))
                while stack:
                    cur = stack.pop()
                    who[cur[0]][cur[1]] = num
                    for nb in getnb(cur[0], cur[1]):
                        ii = nb[0]
                        jj = nb[1]
                        if (not s[ii][jj] == "#") and (not ii*h + jj in visited):
                            stack.append(nb)
                            visited.add(ii*h + jj)
                num += 1
    #
    # for row in who:
    #     print(*row)
    edges = [set() for _ in range(num)]
    for i in range(h):
        for j in range(w):
            cg = who[i][j]
            if not cg == -1:
                for a in range(0, 3):
                    for b in range(-2, 3):
                        if 0 <= i+a < h and 0<= j+b < w:
                            ng = who[i+a][j+b]
                            if ng not in (-1, cg) and (ng not in edges[cg]):
                                edges[cg].add(ng)
                                edges[ng].add(cg)
    # final bfs
    start = who[ch-1][cw-1]
    goal = who[dh-1][dw-1]
    count = 0
    stack = [start]
    visited = set()
    while stack:
        new_stack = []
        for el in stack:
            if not el in visited:
                visited.add(el)
                if el == goal:
                    print(count)
                    exit()
                new_stack.extend(list(edges[el]))
        stack = new_stack
        count += 1
    print(-1)
    exit()

    return


def getnb(i, j):
    nb = []
    if i > 0:
        nb.append((i-1, j))
    if i < h-1:
        nb.append((i+1, j))
    if j > 0:
        nb.append((i, j -1))
    if j < w-1:
        nb.append((i, j +1))
    return nb








h, w = RA()
ch, cw = RA()
dh, dw = RA()
s = [list(raw_input()) for _ in range(h)]
who = [[-1 for _ in range(w)] for _ in range(h)]
solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys
MAX_INT = -100


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


class Maze():
    def __init__(self, maze, start, goal, h, w):
        self.maze = maze
        self.h = h
        self.w = w
        self.start = start
        self.goal = goal

    def clastering(self):
        group = 0
        for i in range(self.h):
            for j in range(self.w):
                if self.maze[i][j] != -1:
                    continue
                self.fill([i, j], group)
                group += 1
        self.num_group = group

    def fill(self, point, group):
        self.maze[point[0]][point[1]] = group
        deque = cl.deque([point])
        ways = [[-1, 0], [0, -1], [0, 1], [1, 0]]

        while len(deque) > 0:
            cur = deque.popleft()

            for way in ways:
                next_i = cur[0] + way[0]
                next_j = cur[1] + way[1]
                if self.isReachable(next_i, next_j) and self.maze[next_i][next_j] != group:
                    self.maze[next_i][next_j] = group
                    deque.append([next_i, next_j])

    def isReachable(self, i, j):
        return 0 <= i < self.h and 0 <= j < self.w and self.maze[i][j] != MAX_INT

    def solve(self):
        self.clastering()

        connected = [[]for i in range(self.num_group)]

        for i in range(self.h):
            for j in range(self.w):
                if not self.isReachable(i, j):
                    continue

                for i_plus in [-2, -1, 0, 1, 2]:
                    for j_plus in [-2, -1, 0, 1, 2]:
                        next_i = i + i_plus
                        next_j = j + j_plus
                        if self.isReachable(next_i, next_j):
                            next_group = self.maze[next_i][next_j]
                            cur_group = self.maze[i][j]
                            if next_group != cur_group:
                                connected[cur_group
                                          ].append(next_group)

        for g in range(len(connected)):
            connected[g] = list(set(connected[g]))

        start_group = self.maze[self.start[0] - 1][self.start[1]-1]
        goal_group = self.maze[self.goal[0]-1][self.goal[1] - 1]

        if start_group == goal_group:
            print(0)
            return

        if len(connected[start_group]) == 0 or len(connected[goal_group]) == 0:
            print(-1)
            return

        costs = [10**19] * len(connected)

        costs[start_group] = 0
        deque = cl.deque([connected[start_group]])
        cost = 1
        while len(deque) > 0:
            cur = deque.popleft()
            if len(cur) == 0:
                break
            next_g = []
            for group in cur:
                if costs[group] > cost:
                    costs[group] = cost
                    next_g.extend(connected[group])

            cost += 1
            deque.append(next_g)

        print(costs[goal_group])


def main():
    h, w = MI()
    start = LI()
    goal = LI()
    maze = [[MAX_INT for i in range(w)] for j in range(h)]

    for i in range(h):
        row = input()
        for j in range(len(row)):
            if row[j] == "#":
                continue
            maze[i][j] = -1

    solver = Maze(maze, start, goal, h, w)
    solver.solve()


main()

Submission status: Accepted

Solution code:
import sys
import heapq as hq
import functools, collections
import math, random
from collections import Counter, defaultdict
import threading

# threading.stack_size(2**27)
# sys.setrecursionlimit(10**6 + 5)

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


# https://codeforces.com/blog/entry/80158?locale=en
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


def dijkstra(G, s):
    n = len(G)
    visited = [False]*n
    weights = [math.inf]*n
    path = [None]*n
    queue = []
    weights[s] = 0
    hq.heappush(queue, (0, s))
    while len(queue) > 0:
        g, u = hq.heappop(queue)
        visited[u] = True
        for v, w in G[u]:
            if not visited[v]:
                f = g + w
                if f < weights[v]:
                    weights[v] = f
                    path[v] = u
                    hq.heappush(queue, (f, v))
    return path, weights


def solve(grid, sx, sy, ex, ey):  # fix inputs here
    console("----- solving ------")

    grid = [[0 if cell == "#" else 1 for cell in row] for row in grid]
    grid = [[0] * len(grid[0])]*2 + grid + [[0] * len(grid[0])]*2
    grid = [[0,0] + row + [0,0] for row in grid]
    sx, sy, ex, ey = sx+1, sy+1, ex+1, ey+1

    labels = [[False for _ in row] for row in grid]
    diffs = [(-1,0), (1,0), (0,-1), (0,1)]

    # @bootstrap
    def dfs(var):
        x,y,cur_label = var
        for dx,dy in diffs:
            xx, yy = x+dx, y+dy
            if labels[xx][yy]:
                continue
            if grid[xx][yy] == 0:
                continue
            labels[xx][yy] = cur_label
            var2 = xx,yy,cur_label
            dfs(var2)

    cur_label = 0
    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if labels[i][j]:
                continue
            if grid[i][j] == 0:
                continue
            cur_label += 1
            labels[i][j] = cur_label
            var = i,j,cur_label
            dfs(var)
            
    console("label")
    console(labels)


    start = labels[sx][sy]
    end = labels[ex][ey]
    console("start and end", start, end)

    connections = defaultdict(set)

    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if cell == 0:
                continue
            for dx in [-2,-1,0,1,2]:
                for dy in [-2,-1,0,1,2]:
                    if labels[i][j] != False and labels[i+dx][j+dy] != False:
                        if labels[i][j] != labels[i+dx][j+dy]:
                            connections[labels[i][j]].add(labels[i+dx][j+dy])
                            connections[labels[i+dx][j+dy]].add(labels[i][j])

    console("connections", connections)

    G = [[] for _ in range(cur_label+1)]

    for k,lst in connections.items():
        G[k].extend([(x,1) for x in lst])

    console("G", G)

    _, result = dijkstra(G, start)
    
    console("result", result)

    if result[end] > 10**6:
        return -1
    return result[end]



def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

def main():
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    nrows, w = list(map(int,input().split()))
    sx, sy = list(map(int,input().split()))
    ex, ey = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(list(input()))

    res = solve(grid, sx, sy, ex, ey)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

main()
# t = threading.Thread(target=main)
# t.start()
# t.join()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
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 print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

BLOCK = '#'
ROAD = '.'

warps = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) not in [(-1, 0), (0, 1), (1, 0), (0, -1), (0, 0)]:
            warps.append((i, j))

def bfs(graph, initial, goal, H, W):
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    q = deque([(initial, 0)])
    visited = [[False for i in range(W)] for i in range(H)]
    dist = [[-1 for i in range(W)] for i in range(H)]
    visited[initial[0]][initial[1]] = True
    block_li = set([])

    while len(q) != 0:
        p, cnt = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j]:
                if graph[i][j] != BLOCK:
                    visited[i][j] = True
                    q.append(((i, j), cnt))

                    if goal[0] == i and goal[1] == j:
                        return cnt
                else:
                    block_li.add((p[0], p[1]))

        if len(q) == 0 and len(block_li) != 0:
            # print(block_li)
            for bp in block_li:
                for d in warps:
                    i = bp[0] + d[0]
                    j = bp[1] + d[1]

                    if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] != BLOCK:
                        tmp = cnt + 1
                        visited[i][j] = True
                        q.append(((i, j), tmp))

                        if goal[0] == i and goal[1] == j:
                            return tmp
            block_li = set()
    return -1


def main():
    H, W = MI()
    CH, CW = MI()
    DH, DW = MI()
    graph = [None] * H
    CH -= 1
    CW -= 1
    DH -= 1
    DW -= 1

    for i in range(H):
        graph[i] = list(S())

        for j in range(W):
            if graph[i][j] == 'S':
                pass

    ret = bfs(graph, (CH, CW), (DH, DW), H, W)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def dfs(y, x, c):
    S[y][x] = c
    for dy, dx in [(-1,0), (1,0), (0,1), (0,-1)]:
            ny = y+dy
            nx = x+dx
            if nx>=0 and nx<W and ny>=0 and ny<H and S[ny][nx]=='.':
                dfs(ny, nx, c)

c = 0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            dfs(i, j, c)
            c+=1

arr = {i:[] for i in range(c)}

for i in range(H):
    for j in range(W):
        cla = S[i][j]
        if cla!='#':
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx = j+dx
                    ny = i+dy
                    if nx>=0 and nx<W and ny>=0 and ny<H and S[ny][nx]!='#':
                        if S[ny][nx]!=cla and S[ny][nx] not in arr[cla]:
                            arr[cla].append(S[ny][nx])

current = S[Ch-1][Cw-1]
goal = S[Dh-1][Dw-1]
dis = {current:0}
queue = [current]
cnt = 1
while queue:
    now = queue.pop(0)
    if arr[now]!=[]:
        for one in arr[now]:
            if one not in dis:
                dis[one] = dis[now]+1
                queue.append(one)

if goal in dis:
    print(dis[goal])
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)
#print(seen)
now = [s]
ans = 0
def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])
while now:
  for x in now:
    a,b = x
    check(a-1,b)
    check(a+1,b)
    check(a,b-1)
    check(a,b+1)
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  ans += 1
  last = now
  now = []
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
else:
  print(-1)

Submission status: Accepted

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

def inValidRegion(i,j,H,W):
    return i >= 0 and i < H and j >= 0 and j < W


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = []
    for i in range(H):
        S.append(list(input()))
    # print(S)
    R = []
    for i in range(H):
        R.append([])
        for j in range(W):
            R[i].append(-1 if S[i][j]=="#" else 0)
    currentId = 1
    for ii in range(H):
        for ij in range(W):
            if R[ii][ij] != 0:
                continue
            init = (ii,ij)
            c = set()
            c.add(init)
            while len(c) > 0:
                i,j = c.pop()
                R[i][j] = currentId
                if inValidRegion(i+1,j,H,W) and R[i+1][j] == 0:
                    c.add((i+1,j))
                if inValidRegion(i,j+1,H,W) and  R[i][j+1] == 0:
                    c.add((i,j+1))
                if inValidRegion(i-1,j,H,W) and R[i-1][j] == 0:
                    c.add((i-1,j))
                if inValidRegion(i,j-1,H,W) and  R[i][j-1] == 0:
                    c.add((i,j-1))
            currentId+=1
    # print(R)
    Connections = [set() for i in range(currentId)]
    Ca = R[Ch-1][Cw-1]
    Da = R[Dh-1][Dw-1]
    # print(Ca,Ch,Cw)
    # print(Da,Dh,Dw)
    if Ca == Da:
        print(0)
    else:
        for i in range(H):
            for j in range(W):
                a = R[i][j]
                if a == -1:
                    continue
                for k in range(-2,3):
                    for l in range(-2,3):
                        if inValidRegion(i+k,j+l,H,W):
                            a2 = R[i+k][j+l]
                            if a2 != a and a2 > 0:
                                Connections[a].add(a2)
                                Connections[a2].add(a)
        # print(Connections)
        reached = set([Ca])
        nextSet = set([Ca])
        warp = 0
        while len(nextSet) > 0:
            currentSet = nextSet
            nextSet = set()
            warp += 1
            while len(currentSet) > 0:
                current = currentSet.pop()
                for c in Connections[current]:
                    if c not in reached:
                        reached.add(c)
                        nextSet.add(c)
                    if c == Da:
                        print(warp)
                        return
        print(-1)

    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

def walk(i, j):
    ans = []
    for h, w in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
        # print(h, w)
        if h >= 0 and w >= 0 and h < H and w < W:
            # print('hoen')
            if S[h][w] == '.':
                if maze[h][w] == -1:
                    ans.append((h, w))
    return ans

def warp(i, j):
    tmp = []
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if not (dh == 0 and dw == 0):
                tmp.append([i + dh, j + dw])
    ans = []
    for h, w in tmp:
        if h >= 0 and w >= 0 and h < H and w < W:
            if S[h][w] == '.':
                if maze[h][w] == -1:
                    ans.append((h, w))
    return ans

maze = [[-1]*W for _ in range(H)]
warp_n = 0
maze[Ch][Cw] = 0
walk_stack= deque(walk(Ch, Cw))
warp_set = set(warp(Ch, Cw))
# print(walk(Ch, Cw))
# print(warp(Ch, Cw))
# print('-----')
while walk_stack or warp_set:
    while walk_stack:
        h, w = walk_stack.pop()
        if maze[h][w] == -1:
            maze[h][w] = warp_n
            walk_stack.extend(walk(h, w))
            warp_set |= set(warp(h, w))
    warp_n += 1
    # print(*maze, sep='\n')
    # print('-----')
    next_warp = set()
    for h, w in warp_set:
        if maze[h][w] == -1:
            maze[h][w] = warp_n
            walk_stack.extend(walk(h, w))
            next_warp |= set(warp(h, w))
    warp_set = next_warp
print(maze[Dh][Dw])

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a,b = map(int,input().split())
c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1

g = []
for _ in range(h):
    s = list(input())
    tmp = []
    for i in s:
        tmp.append(i)
    g.append(tmp)
if g[c][d] =='#':print(-1);exit()
from collections import deque
q = deque([])
p  =deque([])
dp = [[float('inf')]*w for _ in range(h)]

q.append((a,b,0))
dist = [(1,0),(0,1),(0,-1),(-1,0)]
seen = [[False]*w for _ in range(h)]

dp[a][b] = 0
seen[a][b] = True

while p or q:
    while q:
        x,y,cnt = q.popleft()
        p.append((x,y,cnt+1))
        for dx,dy in dist:
            X = x+dx
            Y = y + dy
            if 0<=X<h and 0<=Y<w and not seen[X][Y] and g[X][Y]=='.':
                if dp[X][Y]>cnt:
                    dp[X][Y] = min(dp[X][Y],cnt)
                    seen[X][Y] = True
                    q.append((X,Y,cnt))
                    p.append((X,Y,cnt+1))
    while p:
        x,y,cnt = p.popleft()
        for dx in range(-2,3,1):
            for dy in range(-2,3,1):
                X = x+dx
                Y = y + dy
                if 0<=X<h and 0<=Y<w and not seen[X][Y] and g[X][Y]=='.':
                    if dp[X][Y]>cnt:
                        dp[X][Y] = min(dp[X][Y],cnt)
                        seen[X][Y] = True
                        q.append((X,Y,cnt))
    # print(dp)
print(dp[c][d] if dp[c][d]!=float('inf') else -1)