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: Runtime Error

Solution code:
import itertools
import math
import sys
import heapq

h, w = map(int, input().split())
Ch, Cw = map(int, input().split()) #start
Dh, Dw = map(int, input().split()) #goal
s = [input() for _ in range(w)]

x, y = Ch, Cw
cnt = 0

def WallCheck(s, x, y):
    try:
        if s[x][y-1] == ".":
            return True
        elif s[x+1][y] == ".":
            return True
        elif s[x][y+1] == ".":
            return True
        elif s[x-1][y] == ".":
            return True
        else:
            return False
    except:
        continue

def WarpCheck(s, x, y):
    for i in range(-2, 3):
        for j in range(-2, 3):
            try:
                if s[(x-i)][(y-j)] == "." and i == j == 0:
                    return True
            except:
                continue
    return False

def Manhattan(x, y):
    return math.sqrt(pow(x -Dh, 2) + pow(y-Dw, 2))

def Move(s, x, y, n):
    next = []
    for i in range(-n, n+1):
        for j in range(-n, n+1):
            try:
                if s[(x-i)][(y-j)] == "." and i == j == 0:
                    next.append([i, j])
            except:
                continue
    min_x, min_y = 100, 100
    for i in range(len(next)):
        Manhattan(next[i][0], next[i][1])
        if min_x + min_y >= Manhattan(next[i][0], next[i][1]):
            min_x, min_y = next[i][0], next[i][1]
    return min_x, min_y

def GoalCheck(s, x, y):
    if x == Dh and y == Dw:
        return True
    else:
        return False
    
while True:
        if not WallCheck(s, x, y):
            if not WarpCheck(s, x, y):
                print(-1)
                exit()
            else:
                # ワープ処理
                x, y = Move(s, x, y, 2)
                cnt += 1
        else:
            # 歩く
            x, y = Move(s, x, y, 1)
        
        if GoalCheck(s, x, y):
            print(cnt)
            exit()

Submission status: Runtime Error

Solution code:
from collections import deque
def LI():
    return list(map(int,input().split()))

h,w=LI()
ch,cw=LI()
# ch-=1
# cw-=1
dh,dw=LI()
# dh-=1
# dw-=1

maze=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
# S=[input() for _ in range(h)]

visited=[[False]*(w+2) for _ in range(h+2)]

q=deque()
q.append((ch*10**4+cw))
p=deque()
while q:
    num=q.popleft()
    x,y=num//10**4,num%10**4
    visited[x][y]=True
    for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
        xn,yn=x+i,y+j
        if maze[xn][yn]=="." and visited[xn][yn]==False:
            visited[xn][yn]=True
            q.append((xn*10**4+yn))
    for i in range(-2,3,1):
        for j in range(-2,3,1):
            xm,ym=x+i,y+j
            try:
                if visited[xm][ym]==False:
                    if maze[xm][ym]==".":
                        p.append((xm*10**4+ym))
            except:pass
if visited[dh][dw]==True:
    print(0)
    exit()

for pp in p:
    x,y=pp//10**4,pp%10**4
    if visited[x][y]==False:
        q.append(pp)
if len(q)==0:
    print(-1)
    exit()
for ttt in range(1,100000):
    while q:
        num=q.popleft()
    	x,y=num//10**4,num%10**4
        visited[x][y]=True
        for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
            xn,yn=x+i,y+j
            if maze[xn][yn]=="." and visited[xn][yn]==False:
                visited[xn][yn]=True
                q.append((xn*10**4+yn))
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                xm,ym=x+i,y+j
                try:
                    if visited[xm][ym]==False:
                        if maze[xm][ym]==".":
                            p.append((xm*10**4+ym))
                except:pass
    
    if visited[dh][dw]==True:
        print(ttt)
        exit()
    for pp in p:
    x,y=pp//10**4,pp%10**4
    if visited[x][y]==False:
        q.append(pp)
    if len(q)==0:
        print(-1)
        exit()

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import os
from collections import deque
import itertools

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        データが属するグループのID(と考えて良いはず)を取得する。
        :調査するグループ x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つのデータが属するグループを結合する。
        :結合するデータ(1つ目) x:
        :結合するデータ(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        # 集合を結合する。
        # ※ここ、「要素数の大きい集合に、少ない集合を結合」しているが、こうすることで以後の「処理量を削減」するテクニックである。
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        指定したグループに属するデータの数を返す。
        :調査グループ x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

    def is_same(self, x, y):
        return self.getroot(x) == self.getroot(y)

    def members(self, x):
        """
        指定したグループに属するデータの一覧を返す。size()と比較して速度が圧倒的に遅いので注意。
        :調査グループ x:
        """
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


h = 0


def getpoint(point):
    global h
    return h * point[0] + point[1] - h


# 実装を行う関数
def resolve(test_def_name=""):
    global h

    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    gorl = list(map(int, input().split()))
    maze = [list(input()) for i in range(h)]

    # スタート地点の候補を選定する
    start_list = []
    for i_len, i in enumerate(range(h)):
        for j_len, j in enumerate(range(w)):
            # 自分が壁なら対象外
            if maze[i][j] == "#":
                continue
            start_list.append([i_len, j_len])

    # 集合の分類(-1：未調査)
    ed_list = [[-1 for i in range(w)] for j in range(h)]

    # UnionFindにて集合を明確にする。
    uf = UnionFind(h * w + 1)

    que = deque()
    que.extend(start_list)

    ng_uf_list = []
    # スタート地点の候補数だけ、BFSを行う(今回の問題固有で必要なループ)
    # BFS開始
    while len(que) is not 0:
        now = que.pop()

        # 各方向に集合が存在するか確認
        for i, j in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
            # 処理対象の座標
            target = [now[0] + i, now[1] + j]

            # 処理対象のチェック
            # 外なら何もしない
            if not 0 <= target[0] < h or not 0 <= target[1] < w:
                continue

            # 処理済みなら何もしない
            if ed_list[target[0]][target[1]] != -1:
                continue

            ed_list[target[0]][target[1]] = 1

            # 壁なら結合しない
            if maze[target[0]][target[1]] == "#":
                # ng_uf_list.append(getpoint(target))
                continue

            uf.union(getpoint(target), getpoint(now))

    # 探索処理
    # ng_uf_list = set(ng_uf_list)

    move_list = [[] for i in range(h * w)]

    # 移動できるか確認
    que.extend(start_list)

    # BFS開始
    while len(que) is not 0:
        now = que.pop()

        # 各方向に集合が存在するか確認
        for i, j in [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
                     (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]:
            # 処理対象の座標
            target = [now[0] + i, now[1] + j]

            if not 0 <= target[0] < h or not 0 <= target[1] < w:
                continue

            if maze[target[0]][target[1]] == "#":
                continue

            if uf.is_same(getpoint(now), getpoint(target)):
                continue

            move_list[uf.getroot(getpoint(now))].append(uf.getroot(getpoint(target)))

    moved_list = [0 for a in range(h * w)]
    move_list = [set(a) for a in move_list]

    que.append(uf.getroot(getpoint(start)))
    while len(que) is not 0:
        now = que.pop()
        movetarget = move_list[now]

        for aaa in movetarget:

            # 距離が設定済みなら何もしない
            if not moved_list[aaa] == -1:
                continue

            # キューに追加
            que.appendleft(aaa)

            # 最短距離を設定
            moved_list[aaa] = moved_list[now] + 1

    if uf.is_same(getpoint(start), getpoint(gorl)):
        print(0)
        return

    if moved_list[uf.getroot(getpoint(gorl))] == -1:
        print(-1)
        return

    print(moved_list[uf.getroot(getpoint(gorl))] + 1)

    # テストクラス


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        pass


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Runtime Error

Solution code:
from collections import deque
sys.setrecursionlimit(10 ** 9)
h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
s = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
visited[ch][cw] = 1
queue = deque([[ch, cw, 0]])
queue2 = deque([])


def bfs():
    global s, visited, queue, queue2
    while queue:
        tmp_h, tmp_w, res = queue.pop()
        for p, q in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = tmp_h+p, tmp_w+q
            if (new_h, new_w) == (dh, dw):
                return res
            if new_h < 0 or new_h >= h or \
               new_w < 0 or new_w >= w:
                continue
            elif s[new_h][new_w] != '#' and \
                    visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                queue.appendleft([new_h, new_w, res])
            elif s[new_h][new_w] == '#':
                for p_ in [-2, -1, 0, 1, 2]:
                    for q_ in [-2, -1, 0, 1, 2]:
                        new_h, new_w = tmp_h+p_, tmp_w+q_
                        if new_h < 0 or new_h >= h or \
                                new_w < 0 or new_w >= w:
                            continue
                        elif s[new_h][new_w] != '#' and \
                                visited[new_h][new_w] == 0:
                            queue2.appendleft([new_h, new_w, res+1])
    while queue2:
        tmp_h, tmp_w, res = queue2.pop()
        if visited[tmp_h][tmp_w] == 0:
            queue.appendleft([tmp_h, tmp_w, res])
            break

    if (not queue) and (not queue2):
        return -1

    return bfs()


print(bfs())

Submission status: Runtime Error

Solution code:
from collections import deque

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

grid = []
for _ in range(H):
    grid.append(input())

search = [[0] * W for _ in range(H)]

# for i in range(H):
#     for j in range(W):

q = []
q = deque(q)

q.append((Ch, Cw, 0))
while q:
    v = q.popleft()
    vh = v[0]
    vw = v[1]
    wall = v[2]
    for i in range(-2, 3):
        for j in range(-2, 3):
            try:
                if grid[vh+i][vw+j] == '.':
                    search[vh+i][vw+j] = wall + 1
            except:
                pass
    for t in ((vh+1, vw), (vh, vw+1), (vh-1, vw), (vh, vw-1)):


print('-----output-----')
# 記念提出

Submission status: Runtime Error

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(1000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return
def aaa(g,memo,www,c):
    ww = www[g]
    memo[g]=c
    c2 = (c+1)
    for i in range(len(ww)):
        w=ww[i]
        if w==1 and w!=g:
            if memo[w]==-1 or memo[w] > c2:
                aaa(w,memo,www,c2)

def tansaku(y,x,mp,done,grp,wrp,w,h,gm,xxx):
    wlkh=[y,y,y-1,y+1]
    wlkw=[x-1,x+1,x,x]
    nun=y*w+x
    grp.add(nun)
    gm[nun]=xxx
    for zzz in range(4):
        zh=wlkh[zzz]
        zw=wlkw[zzz]
        if zh < 0:
            continue
        if zh >= h:
            continue
        if zw < 0:
            continue
        if zw >= w:
            continue
        if mp[zh][zw] == "." and done[zh][zw]==0:
            done[zh][zw]=1
            tansaku(zh,zw,mp,done,grp,wrp,w,h,gm,xxx)
    for i in range(y-2,y+3):
        for j in range(x-2,x+3):
            if i < 0:
                continue
            if i >= h:
                continue
            if j < 0:
                continue
            if j >= w:
                continue
            if mp[i][j]==".":
                wrp.add(i*w+j)

def resolve():
    readline=sys.stdin.readline

    h,w=map(int, readline().rstrip().split())
    ch,cw=map(int, readline().rstrip().split())
    dh,dw=map(int, readline().rstrip().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    mp=[]

    cN=ch*w+cw
    dN=dh*w+dw

    done=[[0 for i in range(w)] for j in range(h)]
    gm=[-1] * ((h*w)+3)

    road=0
    for i in range(h):
        ss=readline().rstrip()
        road+=ss.count(".")
        mp.append(ss)

    gs = []
    ws=[]
    xxx=-1
    for y in range(h):
        for x in range(w):
            masu=y*w+x
            if mp[y][x] == "." and done[y][x]==0:
                grp=set()
                wrp=set()
                xxx+=1
                tansaku(y,x,mp,done,grp,wrp,w,h,gm,xxx)
                gs.append(grp)
                ws.append(wrp)
            else:
                done[y][x]=1
    cnt=len(gs)
    www=[[0 for i in range(cnt)] for j in range(cnt)]
    for i in range(cnt):
        gp = gs[i]
        wp = ws[i]
        for pp in wp:
            j=gm[pp]
            www[i][j]=1
            www[j][i]=1
    memo=[-1]*cnt
    aaa(gm[cN],memo,www,0)
    print(memo[gm[dN]])
    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Runtime Error

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 solve(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(solve(H, W, grid, wiz, goal))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', 'i8, i8, i8, u1[:,:], i8[:], i8[:],')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
Done = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
heappush(Q,[0,C])
while Q:
  score,score = heappop(Q)
  x = z[0];y=z[1]
  print(z,reach[x][y])
  if Done[x][y]:
    #print(z,reach[x][y],"DONE")
    continue
  Done[x][y] = True
  #print(z,reach[x][y],Done[x][y])
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      heappush(Q,[score,u])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      #if Done[mx][my]:
      #  continue
      heappush(Q,[score+1,p])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Submission status: Runtime Error

Solution code:
#N=int(input())
H,W=map(int,input().split(" "))
ch,cw=map(int,input().split(" "))
dh,dw=map(int,input().split(" "))

s=[]
for i in range(H):
  t=input()
  s.append(t)

min_warp=0
total_warp=0
pos=[ch,cw]
c=0

#1 migi
#2 shita
#3 hidari
#4 ue

def ido(a, b, w, S):
  if a==dh and b==dw:
    if min_warp > w:
      min_warp = w
  elif a+1 <= ch:
    if S[a+1][b] == ".":
  　  S[a+1][b]="x"
   　 ido(a+1,b,w,S)
  elif b+1 <= cw:
    if S[a][b+1] == ".":
      S[a][b+1]="x"
      ido(a, b+1)
  elif a-1 >= 0:
    if S[a-1][b] == ".":
      S[a-1][b]="x"
      ido(a-1, b)
  elif b-1 >= 0:
    if S[a][b-1] == ".":
      S[a][b-1]="x"
      ido(a-1, b)
  elif a+2 <= ch:
    if S[a+2][b] == ".":
      S[a+2][b]="x"
      w=w+1
      ido(a+2,b,w,S)
  elif b+2 <= cw:
    if S[a][b+2] == ".":
      S[a][b+2]="x"
      w=w+1
      ido(a, b+1)
  elif a-2 >= 0:
    if S[a-2][b] == ".":
      S[a-2][b]="x"
      w=w+1
      ido(a-2, b)
  elif b-2 >= 0:
    if S[a][b-2] == ".":
      S[a][b-2]="x"
      w=w+1
      ido(a-2, b)

idp(ch,cw,total_warp,s)  

print(min_warp)

Submission status: Runtime Error

Solution code:
import math

h,w,m = map(int, input().split())
grid = [[0]*w]*h
ans = 0
pos = []
for _ in range(m):
    y,x = map(int,input().split())
    pos.append([y-1,x-1])
for t in pos:
    grid[t[0]][t[1]]+=1
    for i in range(h):
        print(i)
        if(i!= t[0]):
            grid[i][t[1]]+=1
            ans = max(grid[i][t[1]], ans)
    for b in range(w):
        if(b!= t[1]):
            grid[t[0]][b]+=1
            ans = max(grid[t[0]][b], ans)
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '#' * W * 2
for _ in range(H-4):
  grid += '##' + input() + '##'
grid += '#' * W * 2

def bfs(start):
  INF = 10 ** 9
  dist = [INF] * (H*W)
  magic = [INF] * (H*W)
  dist[start] = 0
  magic[start] = 0
  q = deque([start])
  move_list = [-1, 1, W, -W]
  mag_list1 = [-2*W, -W, 0, W, 2*W]
  mag_listW = [-2, -1, 0, 1, 2]
  while q:
    v = q.popleft()
    dv = dist[v]
    mv = magc[v]
    magic_list = []
    for move in move_list:
      w = v + move
      if grid[w] == '#':
        magic_list.append(move)
      dw = dv + 1
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.append(w)
    for move in magic_list:
      if abs(move) == 1:
        for mag in mag_list1:
          w = v + 2*move + mag
          if grid[w] == '#':
            continue
          mw = mv + 1
          if mw >= magic[w]:
            continue
          magic[w] = mw
          q.append(w)
      else:
        for mag in mag_list2:
          w = v + 2*move + mag
          if grid[w] == '#':
            continue
          mw = mv + 1
          if mw >= magic[w]:
            continue
          magic[w] = mw
          q.append(w)
  return magic

print(bfs(W*(2+Ch-1)+2+Cw)[W*(2+Dh-1)+2+Dw])

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
l = [list(input())for i in range(h)]
dist=[[-1 for _ in range(w)] for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
D=[[1,0],[0,1],[-1,0],[0,-1],[1,1],[-1,1],[-1,1],[-1,-1],[0,2],[2,0],[0,-2],[-2,0],[1,2],[1,-2],[-1,2],[-1,-2],[2,1],[2,-1],[-2,1],[-2,-1],[2,2],[2,-2],[-2,2],[-2,-2]]
M = [-1]
ans = 0

q=deque([[ch-1,cw-1]])
dist[ch-1][cw-1]=0
while q:
    y,x=q.pop()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny and ny<h and 0<=nx and nx<w and dist[ny][nx]==-1:
            if l[ny][nx]=='.':
                q.append([ny,nx])
            if l[nx][ny]=='#':
                for Dx,Dy in D:
                    Nx,Ny = y+Dx,y+Dy
                    if 0<=ny and ny<h and 0<=nx and nx<w and dist[ny][nx]==-1:
                        if l[ny][nx]=='.':
                            q.append([Ny,Nx])
                        if l[Ny][Nx]=='#':
                            q.appendleft([ny,nx])
            dist[ny][nx]=dist[y][x]+(l[ny][nx]=='#')
print(dist[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()

d = [[0, -1], [1, 0], [0, 1], [-1, 0]]
ans = 0
stock 
root_list = []
def dfs(start_h, start_w, r2):
    a[start_h][start_w] = '#'
    if (start_h==Dh) && (start_w==Dw):
        return True
    for i in range(-2, 3):
        for j in range(-2, 3):
            if ((i<-1)||(i>1)) && ((j<-1)||(j>1)):
                s_h = start_h+i; s_w = start_w+j
                if(0<=(start_h+i)<h) && (0<=(start_w+j)<w):
                    if a[s_h][s_w]=='.':
                        root_list.append([s_h, s_w, ans])
    for i in d:
        next_h=start_h+i[0]; next_w=start_w+i[1]
        if(0<=next_h<h) && (0<=next_w<w) && (a[next_h][next_w]=='.')):
            dfs(next_h, next_w, root_list)
def main():
    if(dfs(Ch, Cw, 0)):
        print(0)
        return
    while root_list:
        r0 = root_list[0][0]; r1 = root_list[0][1]; r2=root_list[0][2]+1
        root_list.pop(0)
        if a[r0][r1] == '.':
            root_list[2]
            if dfs(r0, r1, r2):
                print(r2)
                break
    print(-1)
main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    from collections import deque
    import sys
    H, W = map(int, stdin.readline().split())
    ch, cw = map(int, stdin.readline().split())
    dh, dw = map(int, stdin.readline().split())
    ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
    S = [input() for _ in range(H)]
    d = [[0]*W for _ in range(H)]

    que = deque([[cw, ch]])
    count = 0
    while que:
        while que:
            x, y = que.popleft()
            if x == dw and y == dh:
                print(count)
                sys.exit()
                
            d[y][x] = -1
            for i in range(-2, 3):
                for j in range(-2, 3):
                    nnx, nny = x+i, y+j
                    if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                        d[nny][nnx] = 1
        
            for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                    if nx == dw and ny == dh:
                        print(count)
                        sys.exit()
                
                    d[ny][nx] = -1
                    for i in range(-2, 3):
                        for j in range(-2, 3):
                            nnx, nny = nx+i, ny+j
                            if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                                d[nny][nnx] = 1
                    que.append([nx, ny])
                
        for i in range(W):
            for j in range(H):
                if d[j][i] == 1:
                    d[j][i] == -1
                    que.append([i, j])
        count += 1
    print(-1)
if __name__ == __main__:
	main()

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [list(map(str, input())) for _ in range(H)]
T = [[-1 for _ in range(W)] for __ in range(H)] #その点にスタート地点から到達するためのワープの回数
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,-2,-1,0,1,2,2,-2,-2,2,-2,2,-2,-1,0,1,2]
def dfs(y,x,warp):
  # 移動Aで行けるところを埋める
  T[y][x] = warp
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < H and 0 <= ny < W:
      if S[ny][nx] != "#" and T[ny][nx] == -1:
        dfs(ny,nx,warp)
  for i in range(len(ddx)):
    nx = x + ddx[i]
    ny = y + ddy[i]
    if 0 <= nx < H and 0 <= ny < W:
      if S[ny][nx] != "#" and T[ny][nx] == -1:
        dfs(ny,nx,warp+1)
  

dfs(C[0]-1,C[1]-1,0)
print(T[D[0]-1][D[1]-1])

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
f=lambda x:int(x)-1
c1,c2=map(f,input().split())
d1,d2=map(f,input().split())
l=[input() for _ in range(h)]

queue=[]
queue.append([c1,c2])
visit=[[0]*w for _ in range(h)]

wapcnt=0
nokori=h+w-2
while True:
  while len(queue)>0:
    x,y=queue.pop(0)
    if x==d1 and y==d2:
      print(wapcnt)
      exit()
    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      if 0<=x+i<=h-1 and 0<=y+j<=w-1:
        if visit[x+i][y+j]==0 and l[x+i][y+j]=='.':
          visit[x+i][y+j]=1
          queue.append([x+i,y+j])
          nokori=min(nokori,abs(x+i-d1)+abs(y+j-d2))
  if nokori<=4 and abs(x+i-d1)<=2 and abs(y+j-d2)<=2:
    wapcnt+=1
    print(wapcnt)
    exit()
  m=4
  ll=[]
  for p in range(-2,3):
    for q in range(-2,3):
      if 0<=x+p<h and 0<=y+q<w:
        if l[x+p][y+q]=='.' and visit[x+p][y+q]==0:
          if not p==q==0:
            m=min(m,abs(x+p-d1)+abs(y+q-d2))
            ll.append([p,q,abs(x+p-d1)+abs(y+q-d2)])
  if ll==[]:
    print(-1)
    exit()
  nokori-=m
  for lll in ll:
    if lll[2]==m:
      a=lll[0]
      b=lll[1]
  queue.append([x+a,y+b])
  wapcnt+=1