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: Wrong Answer

Solution code:
from collections import deque


H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1:
                q.append([next_y, next_x])
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1
            elif dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]

print(dist[DH - 1][DW - 1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
maze_ini = []
for h in range(H):
    maze_ini.append(list(input()))
    
    
maze = maze_ini
maze[CH-1][CW-1] = "s"
maze[DH-1][DW-1] = "g"


INF = 10**8

d = [[INF for w in range(W)] for h in range(H)] # 各点までの最短距離配列
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#     →,↑,←,↓

ddx = [0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1]
ddy = [2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]


from collections import deque
queue = deque([])

queue.append((DW-1, DH-1))
d[DH-1][DW-1] = 0


while len(queue):
    p = queue.popleft()
    if p == (CW-1, CH-1):
        break

    # 4方向を探索
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != '#':
            queue.append((nx, ny))
            d[ny][nx] = min(d[ny][nx], d[p[1]][p[0]])
    
    if len(queue)==0:
        # ワープ
        for i in range(16):
            nx = p[0] + ddx[i]
            ny = p[1] + ddy[i]

            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != '#' and d[ny][nx] > d[p[1]][p[0]]:
                queue.append((nx, ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
            
if d[CH-1][CW-1] == INF:
    print(-1)
else:
    print(d[CH-1][CW-1])

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
import bisect
from itertools import product
import heapq

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    graph = defaultdict(list)
    for i,j in product(range(h),range(w)):
        if s[i][j] == ".":
            if i > 0 and s[i-1][j] == ".":
                graph[(i,j)].append((0,(i-1,j)))
                graph[(i-1,j)].append((0,(i,j)))
            if j > 0 and s[i][j-1] == ".":
                graph[(i,j)].append((0,(i,j-1)))
                graph[(i,j-1)].append((0,(i,j)))
            for k, l in product(range(max(0,i-2),i),range(max(0,j-2),j)):
                if s[k][l] == ".":
                    graph[(k,l)].append((1,(i,j)))
                    graph[(i,j)].append((1,(k,l)))
            for k, l in product(range(i+1,min(i+3,h)),range(max(0,j-2),j)):
                if s[k][l] == ".":
                    graph[(k,l)].append((1,(i,j)))
                    graph[(i,j)].append((1,(k,l)))
            if i > 1 and s[i-2][j] == ".":
                    graph[(i-2,j)].append((1,(i,j)))
                    graph[(i,j)].append((1,(i-2,j)))
            if j > 1 and s[i][j-2] == ".":
                    graph[(i,j-2)].append((1,(i,j)))
                    graph[(i,j)].append((1,(i,j-2)))
    #print(graph)
    d = [[10**7]*w]*h
    d[ch][cw] = 0
    Q = []
    heapq.heappush(Q,(0,(ch,cw)))
    seen = set([])
    while Q:
        dis, pos1 = heapq.heappop(Q)
        i, j = pos1
        for dd, pos2 in graph[pos1]:
            k, l = pos2
            alt = d[i][j] + dd
            if d[k][l] > alt:
                d[k][l] = alt
                heapq.heappush(Q,(alt,pos2))
    ans = d[dh][dw]
    if ans < 10**7:
        print(ans)
    else:
        print(-1)


            

def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(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):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(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()}


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = []
        for s in S[i:i+1]:
            s[j:j + 1]
            # g += s[max(0, j - 2):j + 3]

        g = set(g)
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True
"""
can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)
"""

Submission status: Wrong Answer

Solution code:
def abc176d_wizard_in_maze():
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start[0] -= 1
    start[1] -= 1
    goal[0] -= 1
    goal[1] -= 1
    maze = []
    for i in range(h):
        maze.append(input())
    dp = [[float('inf')] * w for _ in range(h)]

    dp[start[0]][start[1]] = 0
    q = [[0, start[0], start[1]]]

    while len(q) != 0:
        v = q.pop()
        x, y = v[1], v[2]
        if v[0] >= dp[goal[0]][goal[1]]:
            print(dp[goal[0]][goal[1]])
            return

        for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
            if 0 <= x + dx < h and 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] < dp[x + dx][y + dy]:
                dp[x + dx][y + dy] = dp[x][y]
                q.append([dp[x + dx][y + dy], x + dx, y + dy])

        for dx in [-2, 1, 0, 1, 2]:
            if not 0 <= x + dx < h:
                continue
            for dy in [-2, 1, 0, 1, 2]:
                if 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] + 1 < dp[x + dx][y + dy]:
                    dp[x + dx][y + dy] = dp[x][y] + 1
                    q.append([dp[x + dx][y + dy], x + dx, y + dy])
        q.sort(key=lambda x: x[0], reverse=True)
    if dp[goal[0]][goal[1]] == float('inf'):
        print('-1')
    else:
        print(dp[goal[0]][goal[1]])


abc176d_wizard_in_maze()

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '#':
            S[i][j] = WALL
        else:
            S[i][j] = INI

S[Ch][Cw] = 0
direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]


def dfs(y, x, d):
    if y == Dh and x == Dw:
        print(S[y][x])
        exit()
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            S[next_y][next_x] = S[y][x]
            dfs(next_y, next_x, d)

    for dy in range(-2, 3):
        for dx in range(-2, 3):
            next_y = y + dy
            next_x = x + dx
            if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                continue
            if S[next_y][next_x] == INI:
                d.append((next_y, next_x))
                S[next_y][next_x] = S[y][x] + 1
    return False



d = deque()
d.append((Ch, Cw))
is_goal = False
while len(d):
    y, x = d.popleft()
    dfs(y, x, d)


"""
is_goal = False
while len(d):
    y, x = d.popleft()
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            d.append((next_y, next_x))
            S[next_y][next_x] = S[y][x]
        if next_y == Dh and next_x == Dw:
            is_goal = True

    if warp:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                next_y = y + dy
                next_x = x + dx
                if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                    continue
                if S[next_y][next_x] == INI:
                    d.append((next_y, next_x))
                    S[next_y][next_x] = S[y][x] + 1
                if next_y == Dh and next_x == Dw:                    
                    is_goal = True
    if is_goal:
        break
"""

if is_goal:
    print(S[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def resolve():
    h,w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = []
    for _ in range(h):
        maze.append(list(input()))

    final = [[-1]*w for _ in range(h)]
    mazearv = [[-1]*w for _ in range(h)]
    from collections import deque
    nxt = [[ch, cw]]
    nxt = deque(nxt)
    arv = deque([])
    warp = 0

    while len(nxt) > 0 or len(arv) > 0:
        while len(nxt)>0:
            nowh, noww = nxt.popleft()
            if final[nowh][noww] == -1:
                arv.append([nowh, noww])
            mazearv[nowh][noww] = 1
            final[nowh][noww] = warp
            for i, j in [(-1,0), (1, 0), (0, 1), (0, -1)]:
                if 0 <= nowh+i < h and 0 <= noww+j < w and maze[nowh+i][noww+j] == "." and mazearv[nowh+i][noww+j] == -1:
                    nxt.append([nowh+i, noww+j])

        warp += 1

        while len(arv)>0:
            nowh, noww = arv.popleft()
            for i in range(max(0, nowh-2), min(h, nowh+3)):
                for j in range(max(0, noww-2), min(w, noww+3)):
                    if mazearv[i][j] == -1 and maze[i][j] == "." and final[i][j] == -1:
                        final[i][j] = warp
                        nxt.append([i, j])
    print(final[dh][dw])
resolve()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c1, c2 = map(int,input().split())
d1, d2 = map(int,input().split())
data = []
for i in range(h):data.append(input())
ans = []
for i in range(h):ans.append([1e9]*w)

warp = [-2, -1, 0, 1, 2]
ans[c1-1][c2-1] = 0
for i in range(h):
    for j in range(w):


        for t1 in warp:
            for t2 in warp:
                if(i+t1 < 0 or j+t2 < 0 or i+t1 >= h or j+t2 >= w):continue
                if(data[t1+i][t2+j] == "#"):continue
                if(abs(t1)+abs(t2) <= 1 ):
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j])
                else:
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j]+1)

for i in range(h):
    for j in range(w):
        for t1 in warp:
            for t2 in warp:
                if(i+t1 < 0 or j+t2 < 0 or i+t1 >= h or j+t2 >= w):continue
                if(data[t1+i][t2+j] == "#"):continue
                if(abs(t1)+abs(t2) <= 1 ):
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j])
                else:
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j]+1)


if(ans[d1-1][d2-1] == 1e9):print(-1)
else:print(ans[d1-1][d2-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

def bfs(x,y,z):
    F = 0
    dist[x][y] = 1
    que = deque([[x, y]])
    while que:
        h, w = que.pop()
        for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if maze[nh][nw] == '#':
                F = 1
                continue
            if dist[nh][nw] == -1:
                if nh == Dh and nw == Dw:
                    print(z)
                    exit()
                dist[nh][nw] = 1
                que.appendleft([nh, nw])
        if F == 1 and (h,w,z) not in li:
            li.append((h,w,z))
            que2.append((h,w,z))

H,W = I()
Ch,Cw = I()
Dh,Dw = I()
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
li = deque([])
maze = [list(s()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[Ch][Cw] = 1
que = deque([[Ch, Cw]])
while que:
    F = 0
    h, w = que.pop()
    for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            F = 1
            continue
        if dist[nh][nw] == -1:
            if nh == Dh and nw == Dw:
                print(0)
                exit()
            dist[nh][nw] = 1
            que.appendleft([nh, nw])
    if F == 1:
        li.append((h,w,0))
que2 = copy(li)
lisy = [-2,-1,0,1,2]
lis = []
for i in range(5):
    for j in range(5):
      lis.append([lisy[i],lisy[j]])
while que2:
    h,w,n = que2.pop()
    if h == Dh and w == Dw:
        print(n)
        exit()
    for dh, dw in lis:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if abs(nh-h) > 2 or abs(nw-w) > 2:
            continue
        if dist[nh][nw] == -1:
            print(h,w)
            bfs(nh,nw,n+1)
print(-1)

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m=map(int,input().split())
    p1,p2=map(int,input().split())
    t1, t2 = map(int, input().split())
    ar=[]
    for i in range(n):
        ar.append(list(input()))
    if(ar[t1-1][t2-1]=='#'):
        print('-1')
        exit()
    st1=set()
    dif=[(-1,0),(1,0),(0,-1),(0,1)]
    ct=0
    for p in range(n):
        for r in range(m):
            if(ar[p][r]=='.'):
                ct+=1
                q = deque()
                q.append((p,r))
                while(q):
                    i,j=q.popleft()
                    ar[i][j] = ct
                    for a,b in dif:
                        if(0<=i+a<n and 0<=j+b<m):
                            if(ar[i+a][j+b]=='.'):
                                q.append((i+a,j+b))

    start=ar[p1-1][p2-1]
    end=ar[t1-1][t2-1]
    d=defaultdict(int)
    st=set()
    q=deque()
    if(start==end):
        print(0)
        exit()
    for i in range(n):
        for j in range(m):
            if(ar[i][j]==start):
                st.add((i,j))
                q.append((i,j))
    # print(st)
    # print(q)
    # print(d)
    # d[start]=0
    ans=-1
    while(q):
        i,j=q.popleft()
        for x in range(1,3):
            for y in range(1,3):
                temp=[(-x,y),(-x,-y),(x,-y),(x,y)]
                for a,b in temp:
                    c1,c2=i+a,j+b
                    if(0<=c1<n and 0<=c2<m and ar[c1][c2]!='#' and ar[c1][c2]!=ar[i][j]):
                        if((c1,c2) in st and d[ar[c1][c2]]<=d[ar[i][j]]+1):
                            continue

                        if((c1,c2) in d):
                            d[ar[c1][c2]]=min(d[ar[c1][c2]],d[ar[i][j]]+1)
                        else:
                            d[ar[c1][c2]]=d[ar[i][j]]+1
                        st.add((c1,c2))
                        q.append((c1,c2))
                        if(ar[c1][c2]==end):
                            ans=d[ar[c1][c2]]
    print(ans)



    # print(start,end)
    # for i in ar:
    #     print(i)












BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import time
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
t1 = time.time()
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
    if time.time()-t1 >= 1.70:
        print(-1)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))
 
s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1
 
Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1
 
for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)
 
count = 0
best = 0
 
while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      
      
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))
 
      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))
 
      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))
 
      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))
 
    Q = new_Q
 
  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
 
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
            part.append((x,y))         	
       
    ALL = list(set(part))
    Q = list(ALL)
    
    if (f1,f2) in ALL:
      print(count)
      break
 
    if len(ALL)==0:
      print(-1)
      break
      
    ALL = []

Submission status: Wrong Answer

Solution code:
from collections import deque
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        count+=1
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if nx==goalx and ny==goaly:
                    seen[ny][nx]=seen[y][x]

                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]:
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                
                    
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
    
    #for i in seen:
        #print(*i)

            
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))

Submission status: Wrong Answer

Solution code:
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


h, w = na()
sh, sw = na()
gh, gw = na()

map = []
for _ in range(h):
    s = ns()
    map.append([0 if i=="." else 1 for i in s])

visited = [[100000 for j in range(w)] for i in range(h)]

def warp(nh, nw, now_warp):
    next_p = []
    topleft = [nh-2, nw-2]
    for i in range(5):
        for j in range(5):
            neh = topleft[0]+i
            new = topleft[1]+j
            if check_position(neh, new, now_warp):
                if visited[neh][new] > (now_warp+1):
                    next_p.append([neh, new])
    return next_p


def check_position(hi, wi, now_warp):
    if hi<0 or hi>=h or wi<0 or wi>=w or map[hi][wi]==1 or visited[hi][wi] <= now_warp:
        return False
    return True


positions = deque()
positions.append([sh-1, sw-1, 0])
while len(positions)>0:
    warp_positions = deque()
    while len(positions)>0:
        nh, nw, now_warp = positions.popleft()

        if now_warp >= visited[nh][nw]:
            continue

        visited[nh][nw] = now_warp
        move_cnt = 0
        if check_position(nh+1, nw, now_warp):
            positions.append([nh+1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw+1, now_warp):
            positions.append([nh, nw+1, now_warp])
            move_cnt += 1
        
        if check_position(nh-1, nw, now_warp):
            positions.append([nh-1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw-1, now_warp):
            positions.append([nh, nw-1, now_warp])
            move_cnt += 1

        if move_cnt<4:
            warp_positions.append([nh, nw, now_warp])
    
    while len(warp_positions)>0:
        nh, nw, now_warp = warp_positions.popleft()
        next_warps = warp(nh, nw, now_warp)
        for p in next_warps:
            positions.append([p[0], p[1], now_warp+1])

print(-1 if visited[gh-1][gw-1]==100000 else visited[gh-1][gw-1])

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import time
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
t1 = time.time()
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
    if time.time()-t1 >= 1.50:
        print(-1)
        exit()

print(-1)