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:
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

def bfs(h, w, m, start, goal):
    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    canwarp=True
    cnt=0
    while canwarp:
        #print(goal)
        mimi=100000
        k=0
        t=[]
        while not a.empty():
            hh, ww = map(int, a.get())
            #print(hh,ww)
            d[hh][ww]=1
            if hh == goal[0] and ww==goal[1]:
                flg = True
                break
            for i in range(4):
                nx, ny = ww+dx[i], hh+dy[i]
                if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0:
                    a.put([ny, nx])
                    d[ny][nx] = 1
                    """
                for i in range(-2,3):
                    for j in range(-2,3):
                        if 0 <= hh+i < h and 0 <= ww+j < w and m[hh+i][ww+j]=="." and mimi>goal[1]-(hh+i)+goal[0]-(ww+j) and d[hh+i][ww+j] == 0:
                            t=[hh+i,ww+j]
                            mimi=goal[1]-(hh+i)+goal[0]-(ww+j)
                            k=1"""
        if flg==True:
            break

        #mimi=100000
        #k=0
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= hh+i < h and 0 <= ww+j < w and m[hh+i][ww+j]=="." and mimi>goal[1]-(hh+i)+goal[0]-(ww+j) and d[hh+i][ww+j] == 0:
                    t.append([hh+i,ww+j])
                    mimi=goal[1]-(hh+i)+goal[0]-(ww+j)
                    k=1
        #print(t)
        if k>0:
            for i in range(len(t)):
                a.put(t[i])
            cnt+=1
        else:
            canwarp=False
            break

    return cnt if flg else -1

def main():
    h,w=map(int, input().split())
    start=list(map(int, input().split()))
    goal=list(map(int, input().split()))
    m = [list(input().rstrip("\n")) for i in range(h)]
    start[0]-=1
    start[1]-=1
    goal[0]-=1
    goal[1]-=1
    #print(m,start,goal,h,w)
    print(bfs(h, w, m, start, goal))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

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
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used:
            used.add((_i, _j))
            if S[_i][_j] == '.':
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and S[_i][_j] == '.' and (_i, _j) not in used:
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**6+10)

INF=10**6+10
h,w=[int(_) for _ in input().split()]

ch,cw=[int(_) for _ in input().split()]
dh,dw=[int(_) for _ in input().split()]

s=[[_ for _ in input()]for j in range(h)]

t=[[INF for i in range(w)]for j in range(h)]

def wfs(i,j,d):
    for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
        if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]>t[i][j]:
            t[i+k][j+l]=d
            wfs(i+k,j+l,d)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]>t[i][j]+d:
                t[i+k][j+l]=d+1
                wfs(i+k,j+l,d+1)

t[ch-1][cw-1]=0
wfs(ch-1,cw-1,0)
if t[dh-1][dw-1]==INF:
    t[dh-1][dw-1]=-1
print(t[dh-1][dw-1])

# print(t)

Submission status: Wrong Answer

Solution code:
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(str(input()))
  
def main(h, w, cnt):
  global H
  global W
  global S
  tmp = []
  if (h<H-1) and (S[h+1][w]=='.') and (ans[h+1][w]<0):
    ans[h+1][w] = cnt
    tmp.append([h+1, w])
  if (w<W-1) and (S[h][w+1]=='.') and (ans[h][w+1]<0):
    ans[h][w+1] = cnt
    tmp.append([h, w+1])
  if (0<h) and (S[h-1][w]=='.') and (ans[h-1][w]<0):
    ans[h-1][w] = cnt
    tmp.append([h-1, w])
  if (0<w) and (S[h][w-1]=='.') and (ans[h][w-1]<0):
    ans[h][w-1] = cnt
    tmp.append([h, w-1])
  return tmp

def sub(h, w, cnt):
  global H
  global W
  global S
  tmp = []
  for x in range(max(h-2, 0), min(h+3, H)):
    for y in range(max(w-2, 0), min(w+3, W)):
      if (S[x][y]=='.') and (ans[x][y]<0):
        ans[x][y] = cnt
        tmp.append([x, y])
  return tmp

ans = [[-1]*W for i in range(H)]
ans[ch-1][cw-1] = 0
lis = [[ch-1, cw-1]]
li = [[ch-1, cw-1]]
flag = False
for i in range(1000000):
  for j in range(1000000):
    l = []
    for n in li:
      l += main(n[0], n[1], i)
    if l == []:
      break
    elif [dh-1, dw-1] in l:
      flag = True
      break
    else:
      lis += l
      li = l
  if flag:
    break
  else:
    z = []
    for m in lis:
      z += sub(m[0], m[1], i+1)
    if z == []:
      break
    else:
      lis = z
print(ans[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
"""
AtCoder :: Beginner Contest 176 :: 

"""
import sys
from math import inf


def warp_neighbors(wizard_h, wizard_w, H, W, maze):
    neighbors = []
    for off_h in range(-2, 3, 1):
        for off_w in range(-2, 3, 1):
            h0 = wizard_h+off_h
            w0 = wizard_w+off_w
            if h0 >= H or h0 < 0 or w0 >= W or w0 < 0:
                continue
            if maze[h0][w0] == '.':
                neighbors.append((h0, w0))
    return neighbors

def walk_neighbors(wizard_h, wizard_w, H, W, maze):
    neighbors = []
    for off_h in range(-1, 2, 1):
        for off_w in range(-1, 2, 1):
            # Cannot walk diagonally
            if off_h == off_w:
                continue
            h0 = wizard_h+off_h
            w0 = wizard_w+off_w
            if h0 >= H or h0 < 0 or w0 >= W or w0 < 0:
                continue
            if maze[h0][w0] == '.':
                neighbors.append((h0, w0))
    return neighbors

def main():
    """Main program."""
    H, W = (int(i) for i in sys.stdin.readline().split())
    wizard_h, wizard_w = (int(i) for i in sys.stdin.readline().split())
    dest_h, dest_w = (int(i) for i in sys.stdin.readline().split())
    # Convert to zero-based
    wizard_h -= 1
    wizard_w -= 1
    dest_h -= 1
    dest_w -= 1
    maze = [sys.stdin.readline().strip() for _ in range(H)]
    dist = [[inf for w in range(W)] for h in range(H)]
    dist[wizard_h][wizard_w] = 0

    queue = [(wizard_h, wizard_w)]
    while queue:
        new_queue = []
        for h0, w0 in queue:
            for h1, w1 in walk_neighbors(h0, w0, H, W, maze):
                if dist[h1][w1] > dist[h0][w0]:
                    dist[h1][w1] = dist[h0][w0]
                    new_queue.append((h1, w1))
                
            for h2, w2 in warp_neighbors(h0, w0, H, W, maze):
                if dist[h2][w2] > dist[h0][w0] + 1:
                    dist[h2][w2] = dist[h0][w0] + 1
                    new_queue.append((h2, w2))
        queue, new_queue = new_queue, []

    if dist[dest_h][dest_w] == inf:
        print(-1)
    else:
        print(dist[dest_h][dest_w])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w = 4,5
c,d = 1,2
e,f = 2,5
s = ['#.###','####.','#..##','#..##']
x = """
h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []"""
t = []
m = h*w
for i in range(h):
    #s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = [[c,d]]
stc2 = []
while(1):
#for i in range(10):
    if(c > 0 and s[c-1][d] == '.' and t[c-1][d] > cnt):
        t[c-1][d] = cnt
        stc1.append([c-1,d])
    if(d > 0 and s[c][d-1] == '.' and t[c][d-1] > cnt):
        t[c][d-1] = cnt
        stc1.append([c,d-1])
    if(c < h-1 and s[c+1][d] == '.' and t[c+1][d] > cnt):
        t[c+1][d] = cnt
        stc1.append([c+1,d])
    if(d < w-1 and s[c][d+1] == '.' and t[c][d+1] > cnt):
        t[c][d+1] = cnt
        stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w and s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                    t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                    stc2.append([c+j,d+k])
    if(len(stc1) > 1):
        stc1 = stc1[1:]
        c = stc1[0][0]
        d = stc1[0][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
            
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch += 1
    Cw += 1
    Dh += 1
    Dw += 1
    S = [None] * (H + 4)
    S[0] = S[1] = S[-1] = S[-2] = "#" * (W + 4)
    for h in range(2, H + 2):
        S[h] = "".join(["##", input().rstrip(), "##"])

    CC = [[-1] * (W + 4) for _ in range(H + 4)]
    CC_i = 0
    CC_S = -1
    CC_G = -1
    for h in range(2, H + 2):
        for w in range(2, W + 2):
            if CC[h][w] != -1: continue
            if S[h][w] == "#": continue
            queue = deque([(h, w)])
            while queue:
                h, w = queue.popleft()
                CC[h][w] = CC_i
                if h == Ch and w == Cw: CC_S = CC_i
                if h == Dh and w == Dw: CC_G = CC_i
                for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    y, x = h + i, w + j
                    if CC[y][x] != -1: continue
                    if S[y][x] == "#": continue
                    queue.append((y, x))
            CC_i += 1

    G = [[] for _ in range(CC_i)]
    for h in range(2, H + 2):
        for w in range(2, W + 2):
            if S[h][w] == "#": continue
            CC_from = CC[h][w]
            for i in (-2, -1, 0, 1, 2):
                for j in (-2, -1, 0, 1, 2):
                    y, x = h + i, w + j
                    CC_to = CC[y][x]
                    if CC_to == -1: continue
                    if CC_to != CC_from:
                        if CC_to not in G[CC_from]:
                            G[CC_from].append(CC_to)

    ans = -1
    visited_CC = [False] * CC_i
    queue = deque([CC_S])
    n_warp = 0
    while queue:
        cc = queue.popleft()
        visited_CC[cc] = True
        if cc == CC_G:
            ans = n_warp
            break
        for dd in G[cc]:
            if visited_CC[dd]: continue
            queue.append(dd)
        n_warp += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = [input() for _ in range(h)]

sh-=1; sw-=1; gh-=1; gw-=1;

dist = [[-1]*w for _ in range(h)]
dist[sh][sw] = 0
q = deque([(0,sh,sw)])
warpq = deque([])

while q or warpq:
    while q:

        d,vsh,vsw = q.popleft()

        flag = 0
        
        for dh,dw in [(-1,0),(1,0),(0,-1),(0,1)]:
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if s[newh][neww] == "#":
                if flag ==0:
                    warpq.append((d,vsh,vsw))
                    flag = 1
                continue

            if dist[newh][neww] == -1:
                dist[newh][neww] = d
                q.append((d,newh,neww))

    while warpq:

        d,vsh,vsw = warpq.popleft()
        for dh in range(-2,3):
            for dw in range(-2,3):
                newh = vsh+dh
                neww = vsw+dw
                if newh<0 or h<=newh or neww<0 or w<=neww: continue
                if abs(dh)+abs(dw)<=0: continue
                if s[newh][neww] == "#": continue

                if dist[newh][neww] == -1:
                    dist[newh][neww] = d+1
                    q.append((d+1,newh,newh))
            
print(dist[gh][gw])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

ch -= 1
cw -= 1
dh -= 1
dw -= 1

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

cost = [[-1] * w for _ in range(h)]
hq = [(ch,cw,0)]


while(hq):
    ci,xi,yi = heappop(hq)
    if(cost[xi][yi] != -1):
        continue
    cost[xi][yi] = ci

    for dx in range(-2,3):
        for dy in range(-2,3):
            xj,yj = xi+dx,yi+dy
            # print(xi,yi,xj,yj)
            if(xj<0)|(xj>=h)|(yj<0)|(yj>=w):
                continue
            if(cost[xj][yj]!=-1):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                heappush(hq,(ci,xj,yj))
            else:
                heappush(hq,(ci+1,xj,yj))

print(cost[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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
    S = [list(input()) for _ in range(H)]
    dist = [[float('inf')] * W for _ in range(H)]
    cnt = [[0] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    dt = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    dist[Ch][Cw] = 0
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for dh, dw in dt:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    if not ((dh,dw) in [(-1,0),(0,-1),(0,1),(1,0)]):
                        continue
                    if dist[nh][nw] == float('inf'):
                        dist[nh][nw] = dist[h][w]
                        Q.append([nh,nw])
                    else:
                        if dist[nh][nw] > dist[h][w]:
                            dist[nh][nw] = dist[h][w]
                            Q.append([nh,nw])
                else:
                    if cnt[h][w] == 0:
                        cnt[nh][nw] = cnt[h][w] + 1
                        dist[nh][nw] = dist[h][w] + 1
                        Q.append([nh,nw])
    if dist[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(dist[Dh][Dw])




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    score=[[10000]*W  for i in range(H)]
    score[Sy][Sx] = 0
    heapq.heappush(q,(Sx,Sy,0))
    visited = [[False for j in range(W)] for i in range(H)]

    while q:
        x,y,cs = heapq.heappop(q) 

        if visited[y][x]:
            continue
        visited[y][x]=True


        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:
            score[y-1][x]=score[y][x]
            heapq.heappush(q,(x,y-1,cs))
        if y!=H-1 and MP[y+1][x]=='.' and score[y][x]<score[y+1][x]:
            score[y+1][x]=score[y][x]
            heapq.heappush(q,(x,y+1,cs))
  
        if x!=0 and MP[y][x-1]=='.' and score[y][x]<score[y][x-1]:
            score[y][x-1]=score[y][x]
            heapq.heappush(q,(x-1,y,cs))
        if x!=W-1 and MP[y][x+1]=='.' and score[y][x]<score[y][x+1]:
            score[y][x+1]=score[y][x]
            heapq.heappush(q,(x+1,y,cs))

        for i in range(max(0,y-2),min(H,y+3)):
            for j in range(max(0,x-2),min(W,x+3)):

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(j,i,score[y][x]+1))

    if score[Gy][Gx]==10000:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    tizu = [input() for _ in range(h)]
    
    inf = 10 ** 9
    check = [[inf for _ in range(w)] for _ in range(h)]
    queue = deque()
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    check[ch][cw] = 0
    walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    
    queue.append([ch, cw])
    queue.append(0)
    while queue:
        pos = queue.popleft()
        dd = queue.popleft()
        flg = [False, False, False, False]
        for dy, dx in walk:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd:
                continue
            if tizu[n_h][n_w] == "#":
                if dy == 1:
                    flg[0] = True
                elif dy == -1:
                    flg[1] = True
                elif dx == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            check[n_h][n_w] = dd
            queue.append([n_h, n_w])
            queue.append(dd)
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
        
        for dy, dx in magic:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    
    
    if check[dh][dw] == inf:
        print(-1)
    else:
        print(check[dh][dw])
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

H, W = map(int, sys.stdin.readline().rstrip().split())
Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

S = []
for i in range(H):
    S.append(sys.stdin.readline().rstrip())

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

mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]

# BFS #


def bfs(u):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx = u[0] + mX[i]
            ny = u[1] + mY[i]
            if nx < 0 or H <= nx:
                continue
            if ny < 0 or W <= ny:
                continue
            if S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for x in range(-2, 3):
            for y in range(-2, 3):
                wx = u[0] + x
                wy = u[1] + y
                if wx < 0 or H <= wx:
                    continue
                if wy < 0 or W <= wy:
                    continue
                if S[wx][wy] == "#":
                    continue
                if M[wx][wy] == -1:  # state を確認
                    M[wx][wy] = M[u[0]][u[1]] + 1
                    q.append([wx, wy])

M[Ch - 1][Cw - 1] = 0
bfs([Ch - 1, Cw - 1])

print(M[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())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.append((ny,nx))
          D[ny][nx]=D[y][x]
        else:
          cnt+=1
      else:
        cnt+=1
    if cnt==4:
      for i in range(20):
        my=y+ey[i]
        mx=x+ex[i]
        if 0<=my<H and 0<=mx<W:
          if A[my][mx]=='.' and D[my][mx]==10**8:
            q.append((my,mx))
            D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
DDX = (-1, 0, 1, 0, -1, -1, 1, 1)
DDY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DDX[:4]
DY = DDY[:4]


H, W = map(int, input().split())
Cx, Cy = map(int, input().split())
Dx, Dy = map(int, input().split())

grid = ["#" * (W + 2)]
for _ in range(H):
    inp = "#" + input().strip() + "#"
    grid.append(inp)
grid.append("#" * (W + 2))


area = [[-1] * (W + 2) for _ in range(H + 2)]
cnt = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == "#" or area[i][j] != -1:
            continue
        cnt += 1
        node = [(i, j)]
        area[i][j] = cnt
        while node:
            x, y = node.pop()
            for dx, dy in zip(DX, DY):
                nx = x + dx
                ny = y + dy
                if grid[nx][ny] == "#":
                    continue
                if area[nx][ny] == -1:
                    area[nx][ny] = cnt
                    node.append((nx, ny))

if area[Cx][Cy] == area[Dx][Dy]:
    print(0)
    exit()


used = defaultdict(int)

edge = [[] for _ in range(cnt + 1)]
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == ".":
            continue
        memo = set()
        for dx, dy in zip(DDX, DDY):
            if area[i + dx][j + dy] == -1:
                continue
            memo.add(area[i + dx][j + dy])
            for x, y in combinations(memo, 2):
                if x > y:
                    x, y = y, x
                if used[(x, y)]:
                    continue
                edge[x].append(y)
                edge[y].append(x)
                used[(x, y)] = 1


dist = [-1] * (cnt + 1)
ci = area[Cx][Cy]
di = area[Dx][Dy]
dist[ci] = 0
node = deque([ci])
while node:
    s = node.popleft()
    for t in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = dist[s] + 1
        node.append(t)

print(dist[di])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0, 0, 0))
visited = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited:
        if (visited[(x, y)][1] == e and visited[(x, y)][0] <= d) or visited[(x, y)][1] < e:
            continue
    visited[(x, y)] = (d, e)
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H:
            if grid[ny][nx] == "#":
                if 1 < d:
                    continue
                else:
                    d += 1
            # ワープした
            elif grid[ny][nx] == ".":
                if 0 < d:
                    d = 0
                    e += 1
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.append((nx, ny, c+1, d, e))

print(-1 if ans == float("inf") else ans)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**6+10)

INF=10**6+10
h,w=[int(_) for _ in input().split()]

ch,cw=[int(_) for _ in input().split()]
dh,dw=[int(_) for _ in input().split()]

s=[[_ for _ in input()]for j in range(h)]

t=[[INF for i in range(w)]for j in range(h)]

def wfs(i,j,d):
    for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
        if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]>t[i][j]:
            t[i+k][j+l]=d
            wfs(i+k,j+l,d)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]>t[i][j]+d:
                t[i+k][j+l]=d+1
                wfs(i+k,j+l,d+1)

t[ch-1][cw-1]=0
wfs(ch-1,cw-1,0)
print(t[dh-1][dw-1])

# print(t)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
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

maze = []
for i in range(H):
    maze.append(list(input()))

cnt = 0

def bfs():
    global cnt
    reached = [[False for _ in range(W)] for _ in range(H)]

    d = deque()
    d.append((Ch, Cw))
    reached[Ch][Cw] = True
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
                    reached[next_h][next_w] = True
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            d.append((i, j))
                            reached[i][j] = True
        if d:
            cnt += 1

bfs()
print(-1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[-1 if i != C[0] or j != C[1] else 0 for j in range(W)] for i in range(H)]
queue = [C]
ans = 0

while True:
    tmp = queue.pop()
    dfs = [tmp]

    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue

            if toGo[hh][ww] == -1 and S[hh][ww] == '.':
                toGo[hh][ww] = ans
                dfs.append([hh, ww])

    if toGo[D[0]][D[1]] != -1:
        break

    if not len(queue):
        flag = True
        ans += 1
        for i in range(H):
            for j in range(W):
                if toGo[i][j] == ans - 1:
                    for ii in range(-2, 3):
                        for jj in range(-2, 3):
                            hh, ww = i + ii, j + jj
                            if hh >= H or hh < 0 or ww >= W or ww < 0:
                                continue

                            if S[hh][ww] == '.' and toGo[hh][ww] == -1:
                                toGo[hh][ww] = ans
                                flag = False
                                queue.append([hh, ww])
                                break

        if flag:
            print(-1)
            exit()

print(ans)