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
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    P = [[-1 for _ in range(W)] for h in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if P[h][w] == -1 and S[h][w] == ".":
                q.append((h, w))
                while q:
                    ch, cw = q.popleft()
                    if P[ch][cw] == -1:
                        P[ch][cw] = count
                        for dh, dw in move:
                            if 0<=ch+dh<H and 0<=cw+dw<W and S[ch+dh][cw+dw] == "." and P[ch+dh][cw+dw] == -1:
                                q.append((ch+dh, cw+dw))
                count += 1

    q.append((0, sh, sw))
    D = [[-1 for w in range(W)] for h in range(H)]
    while q:
        d, ch, cw = q.popleft()
        if D[ch][cw] == -1:
            D[ch][cw] = d
            for dh, dw in move:
                if 0<=ch+dh<H and 0<=cw+dw<W and S[ch+dh][cw+dw] == "." and D[ch+dh][cw+dw] == -1:
                    if P[ch][cw] == P[ch+dh][cw+dw]: q.append((d, ch+dh, cw+dw))
                    else: q.append((d+1, ch+dh, cw+dw))
    print(D[fh][fw])

    return 0

if __name__ == "__main__":
    solve()

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(list(str(input())))



currentH = ch - 1
currentW = cw - 1
warpCount = 0
errorH = False
errorW = False
while dh - 1 != currentH and dw - 1 != currentW and (errorH == False or errorW == False):
    #縦
    hSize = dh - currentH
    if hSize < 0:
        moveH = -1
    else:
        moveH = 1
    while dh - 1 != currentH:
        if s[currentH + moveH][currentW] == "#":
            if 2 <= abs(dh - 1 - currentH):
                if s[currentH + moveH * 2][currentW] == ".":
                    currentH += moveH * 2
                    warpCount += 1
                else:
                    errorH = True
                    break
            else:
                errorH = True
                break
        else:
            currentH += moveH
        #print(currentH, currentW)
        errorW = False

    #横
    wSize = dw - currentW
    if wSize < 0:
        moveW = -1
    else:
        moveW = 1
    while dw - 1 != currentW:
        if s[currentH][currentW + moveW] == "#":
            if 2 <= abs(dw - 1 - currentW):
                if s[currentH][currentW + moveW * 2] == ".":
                    currentW += moveW * 2
                    warpCount += 1
                else:
                    errorW = True
                    break
            else:
                errorW = True
                break
        else:
            currentW += moveW
        #print(currentH, currentW)
        errorH == False

if errorH == True and errorW == True:
    warpCount = -1

print(warpCount)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import sys
import os
from operator import mul
from collections import deque


sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs():
    ans = -1
    # すべての点を INF で初期化
    d = [[float("inf")] * W for i in range(H)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    # スタート地点をキューに入れ、ワープ数を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    que2 = deque([])
    que2.append((sx, sy))

    while que: 
        while que:
            p = que.popleft()
            que2.append(p)
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                break
            # 移動4方向をループ
            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 移動が可能かの判定とすでに訪れたことがあるかの判定
                # d[nx][ny] != INF なら訪れたことがある
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p までのワープ回数で確定する
                    que.append((nx, ny))
                    que2.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
        dx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
        dy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
        while que2:
            # キューの先頭を取り出す
            p = que2.popleft()
            for i in range(20):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                    que.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]+1    
    return ans

print(bfs())

Submission status: Wrong Answer

Solution code:
def bfs(x, y, check):
    global checked
    if x < 0 or w <= x: return
    if y < 0 or h <= y: return
    if S[y][x] == '#': return
    if check[y][x] == True: return
    check[y][x] = True
    checked[y][x] = True
    bfs(x - 1, y, check)
    bfs(x + 1, y, check)
    bfs(x, y - 1, check)
    bfs(x, y + 1, check)

def bfs2(x, y):
    if x < 0 or w <= x: return False
    if y < 0 or h <= y: return False


def search_goal(x, y, ans):
    check = [[False for i in range(w)] for j in range(h)]
    bfs(x, y, check)
    if checked[gy][gx] == True: return ans

    ret = float('inf')
    for i in range(h):
        for j in range(w):
            if check[i][j] == True:
                for dy in range(-2, 3, 1):
                    if 0 <= i+dy < h:
                        for dx in range(-2, 3, 1):
                            if 0 <= j+dx < w and S[i+dy][j+dx] == '.':
                                if checked[i+dy][j+dx] == False:
                                    cnt = search_goal(i+dy, j+dx, ans + 1)
                                    if cnt != -1:
                                        ret = min(ret, cnt)
    if ret != float('inf'):
        return ret
    else:
        return -1


h, w = map(int, input().split())
cy, cx = map(int, input().split())
cx -= 1
cy -= 1
gy, gx = map(int, input().split())
gy -= 1
gx -= 1

S = [input() for _ in range(h)]

checked = [[False for i in range(w)] for j in range(h)]

print(search_goal(cx, cy, 0))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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
S = [input() for i in range(H)]

ans = 0

kabe_yoko = []
for i in range(H):
    kabe = '#' * W
    if S[i] == kabe:
        kabe_yoko.append(i)

kabe_tate = []
for w in range(W):
    tate = ''
    for h in range(H):
        tate += S[h][w]
    kabe = '#' * H
    if tate == kabe:
        kabe_tate.append(w)

for i in range(len(kabe_yoko) - 1):
    if abs(kabe_yoko[i] - kabe_yoko[i + 1]) == 1 and ch < kabe_yoko[i] < kabe_yoko[i + 1] < dh:
        print('-1')
        exit()

for i in range(len(kabe_tate) - 1):
    if abs(kabe_tate[i] - kabe_tate[i + 1]) == 1 and cw < kabe_tate[i] < kabe_tate[i + 1] < dw:
        print('-1')
        exit()

for i in kabe_yoko:
    if ch < i < dh:
        ans += 1

for i in kabe_tate:
    if cw < i < dw:
        ans += 1

kabe_zigzag_yoko = []
for h in range(H - 1):
    cnt = 0
    for w in range(W):
        if '#' in S[h][w] or '#' in S[h + 1][w]:
            cnt += 1
    if cnt == W:
        kabe_zigzag_yoko.append(h)

kabe_zigzag_tate = []
for w in range(W - 1):
    cnt = 0
    for h in range(H):
        if '#' in S[h][w] or '#' in S[h][w + 1]:
            cnt += 1
    if cnt == W:
        kabe_zigzag_tate.append(w)

for i in kabe_zigzag_yoko:
    if ch < i < dh:
        ans += 1

for i in kabe_zigzag_tate:
    if cw < i < dw:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[100000000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0
flg[C[0]-1][C[1]-1] = 1

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
        flg[ny][nx] = 1

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue

answer = cost[D[0]-1][D[1]-1]
if answer == 100000000:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
import collections

h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

g = {}

def dump():
    print('map')
    for row in s:
        print(''.join(row))
    print('graph')
    print(g)
    print()

def check_range(x, y):
    return (0 <= x < h) and (0 <= y < w)

deq = collections.deque()
ident = 0
def reveal_cluster():
    global ident
    while len(deq):
        x, y, no = deq.popleft()
        if not check_range(x, y):
            continue
        if s[x][y] != '.':
            continue
        
        if no is None:
            ident += 1
            g[ident] = set()

        s[x][y] = str(ident)

        # 移動A
        for dx, dy in [(0, -1), (0, +1), (-1, 0), (+1, 0)]:
            nx, ny = x + dx, y + dy
            if check_range(nx, ny) and s[nx][ny] == '.':
                deq.append((nx, ny, ident))

deq.append((ch - 1, cw - 1, None))
reveal_cluster()

deq.append((dh - 1, dw - 1, None))
reveal_cluster()

for i in range(h):
    for j in range(w):
        deq.append((i, j, None))
        reveal_cluster()
#dump()

def check_cluster_connectivity():
    while len(deq):
        x, y, prev = deq.popleft()

        if not (0 <= x < h) or not (0 <= y < w):
            continue
        if s[x][y] == '#':
            continue

        curr = s[x][y]
        curr = int(curr)
        if prev is not None and curr != prev:
            # warpできる
            k = int(s[x][y])
            g[prev].add(k)

        _prev = int(s[x][y])

        s[x][y] = '#'

        # 移動B
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if check_range(nx, ny) and s[nx][ny] != '#' and s[nx][ny] != s[x][y]:
                    v = (nx, ny, _prev)
                    deq.append(v)

for i in range(h):
    for j in range(w):
        v = (i, j, None)
        deq.append(v)
        check_cluster_connectivity()

dist = {k:None for k in g}
def bfs(pos, d):
    if dist[2] is not None:
        return
    if dist[pos] is not None:
        return
    dist[pos] = d
    for e in g[pos]:
        bfs(e, d + 1)

if len(g) == 1:
    # スタート = ゴール
    print(0)
else:
    bfs(1, 0)
    
    a = dist[2]
    if a is None:
        # 経路なし
        print(-1)
    else:
        # 経路あり
        print(a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
gx, gy = map(int, input().split())
gx -= 1
gy -= 1
map = [list(input()) for i in range(H)]
cost_map = [[10**5]*W for i in range(H)]
d = deque()
cost_map[sx][sy] = 0
d.append([sx, sy])
while d:
    cx, cy = d.pop()
    if cx==gx and cy==gy:
        break
    ccost = cost_map[cx][cy]
    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and ccost < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost
                d.append([nx, ny])
    dxy = [[-2, -2],[-2, -1],[-2, 0],[-2, 1],[-2, 2],
           [-1, -2],[-1, -1],[-1, 1],[-1, 2],
           [0, -2],[0, 2],
           [1, -2],[1, -1],[1, 1],[1, 2],
           [2, -2],[2, -1],[2, 0],[2, 1],[2, 2]]
    for dx, dy in dxy:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and (ccost + 1) < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost + 1
                d.appendleft([nx, ny])
if cost_map[gx][gy] == 10**5:
    print("-1")
else:
    print(int(cost_map[gx][gy]))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

map_ = []
for hi in range(h):
    s = input()
    line = [None if s[wi] == "." else "#" for wi in range(w)]
    map_.append(line)        

#print(map_)

def umeru(x, y, cur_cost, cur_kabe):
    map_[y][x] = cur_cost
    global cur_kabes
    tonaris = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]

    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] is None:
                map_[ny][nx] = cur_cost
                umeru(nx, ny, cur_cost, cur_kabe)
            elif map_[ny][nx] == cur_kabe:
                #print((x, y), (nx, ny))
                #map_[ny][nx] -= 1
                map_[ny][nx] = "$"
                cur_kabes.append([nx, ny])

    tonaris = [[nx, ny] for nx in [x-2, x-1, x, x+1, x+2] for ny in [y-2, y-1, y, y+1, y+2]]
    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] == cur_kabe:
                map_[ny][nx] = "$"
                cur_kabes.append([nx, ny])

def find_ins(x, y):
    tonaris = [[nx, ny] for nx in [x-1, x, x+1] for ny in [y-1, y, y+1]]
    ins = []
    
    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] is None:
                ins.append([nx, ny])
    return ins


                
                
ins = [[cw, ch]]
cur_cost = 0
cur_kabe = "#"
while True:
    cur_kabes = []
    for inw, inh in ins:
        umeru(inw, inh, cur_cost, cur_kabe)

    ins = []
    for x, y in cur_kabes:
        ins += find_ins(x, y)

    if len(ins) == 0:
        break
        
    cur_cost += 1
    #cur_kabe -= 1

if False:
    for m in map_:
        line = []
        for c in m:
            if c is None:
                c = "."
            elif isinstance(c, int):
                c = str(c)
            line.append(c)
        print("".join(line))

out = map_[dh][dw]
if out is None:
    out = -1
assert out >= -1
print(out)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W = MI()
sh,sw = MI()
gh,gw = MI()
S = [['#']*(W+1)] + [['#'] + LS2() for i in range(H)]
directions = [(-1,0),(1,0),(0,-1),(0,1)]

from collections import deque
from copy import deepcopy

r = deque([(gh,gw)])
ans = [[-1]*(W+1) for _ in range(H+1)]
ans[gh][gw] = 0
for i in range(H*W):
    q = deepcopy(r)
    r = deque([])  # 魔法使用
    if len(q) == 0:
        break
    while q:
        nh,nw = q.pop()
        if not (1 <= nh <= H and 1 <= nw <= W):
            continue
        ans[nh][nw] = i


        for j in range(-2,3):
            for k in range(-2,3):
                if j == 0 and k == 0:
                    continue
                if 1 <= nh+j <= H and 1 <= nw+k <= W:
                    if ans[nh+j][nw+k] == -1 and S[nh+j][nw+k] != '#':
                        r.appendleft((nh+j,nw+k))

        for dh,dw in directions:
            if not (1 <= nh+dh <= H and 1 <= nw+dw <= W):
                continue
            elif S[nh+dh][nw+dw] == '#':
                continue
            elif ans[nh+dh][nw+dw] != -1:
                continue
            else:
                ans[nh+dh][nw+dw] = i
                q.appendleft((nh+dw,nw+dw))
    for _ in range(len(r)):
        h,w = r.pop()
        if ans[h][w] == -1:
            r.appendleft((h,w))
print(ans[sh][sw])

Submission status: Wrong Answer

Solution code:
import heapq
class solve:
    def __init__(self):
        self.H, self.W = map(int, input().split())
        self.Ch, self.Cw = map(int, input().split())
        self.Dh, self.Dw = map(int, input().split())
        maze = []
        for i in range(self.H):
            maze.append(list(input()))
        ad = [[[] for j in range(self.W)] for i in range(self.H)]
        for i in range(0, self.H):
            for j in range(0, self.W):
                if maze[i][j] == ".":
                    for s in range(i-2, i+2):
                        for t in range(j-2, j+2):
                            if 0 <= s < self.H and 0 <= t < self.W:
                                if maze[s][t] != "#":
                                    if not (s == i and t == j):
                                        if abs(s-i) == 1 and abs(j-t) == 1:
                                            ad[i][j] = ad[i][j] + [[(s,t), 0]]
                                        else:
                                            ad[i][j] = ad[i][j] + [[(s,t), 1]]
        self.list = [[] for i in range(self.H*self.W+1)]
        for i in range(self.H):
            for j in range(self.W):
                for k in range(len(ad[i][j])):
                    s, t = ad[i][j][k][0]
                    self.list[self.W*i+j].append([self.W*s+t, ad[i][j][k][1]])
    def sol(self):
        frm = self.W * (self.Ch-1) + (self.Cw-1)
        d = [float('inf') for i in range(len(self.list))]
        d[frm] = 0
        prev = [None for i in range(len(self.list))]
        pq = []
        heapq.heappush(pq, [0, frm])
        while len(pq) > 0:
            weight, u = heapq.heappop(pq)
            for v, weight in self.list[u]:
                if d[v] > d[u] + weight:
                    d[v] = d[u] + weight
                    heapq.heappush(pq, [d[v], v])
                    prev[v] = u
        return d[self.W * (self.Dh-1) + (self.Dw-1)]

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from itertools import combinations

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
    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
                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

    CC_S = CC[Ch][Cw]
    CC_G = CC[Dh][Dw]

    G = [[False] * CC_i for _ in range(CC_i)]
    for h in range(2, H):
        for w in range(2, W):
            CC_list = []
            for i in (0, 1, 2):
                for j in (0, 1, 2):
                    y, x = h + i, w + j
                    CC_to = CC[y][x]
                    if CC_to == -1: continue
                    CC_list.append(CC_to)
            if len(CC_list) >= 2:
                for a, b in combinations(CC_list, r=2):
                    G[a][b] = G[b][a] = True

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

def main():
    li = [["" for i in range(w)]for j in range(h)]
    vi = [[False for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

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

    mx = []
    my = []

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            mx.append(i)
            my.append(j)

    lin = [[inf for i in range(w)]for j in range(h)]
    lin[ch][cw] = 0#ここをスタートの座標に変えること
    que.append((ch,cw))#ここもスタートの座標に変えること

    while que:
        k = que.popleft()

        x = k[0]
        y = k[1]

        for i,j in zip(dx,dy):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]:
                    if vi[nx][ny] == False:
                        que.append((nx,ny))
                    vi[nx][ny] = True
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        # 魔法の力をもってすれば行ける
        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    if vi[nx][ny] == False:
                        que.append((nx,ny))
                    vi[nx][ny] = True
                    lin[nx][ny] = lin[x][y]+1

    if lin[dh][dw] == inf:
        print(-1)
    else:
        print(lin[dh][dw])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import random

print(random.randint(1,10))

Submission status: Wrong Answer

Solution code:
# 2020/08/22
# AtCoder Beginner Contest 176 - D

# Input
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
sl = list()
sl.append(['#'] * (w+2))
for i in range(h):
    s = list('#' + input())
    s.append('#')
    sl.append(s)
sl.append(['#'] * (w+2))

wcnt = 0
findflg = False
posq = list()
tl = [[0] * (w+2) for i in range(h+2)]
tl[ch][cw] = 1
posq.append([ch, cw])
passq = list()

loopmax = h  * w

while(True):
    while(len(posq) > 0):
        th, tw = posq.pop()
        if th == dh and tw == dw:
            findflg = True
            break
            
        passq.append([th, tw])
    
        if sl[th-1][tw] == '.' and tl[th-1][tw] == 0:
            posq.append([th-1, tw])
            tl[th-1][tw] = 1
        elif sl[th][tw-1] == '.' and tl[th][tw-1] == 0:
            posq.append([th, tw-1])
            tl[th][tw-1] = 1
        elif sl[th+1][tw] == '.' and tl[th+1][tw] == 0:
            posq.append([th+1, tw])
            tl[th+1][tw] = 1
        elif sl[th][tw+1] == '.' and tl[th][tw+1] == 0:
            posq.append([th, tw+1])
            tl[th][tw+1] = 1

    if findflg == True:
        break

    while(len(passq) > 0):
        ph, pw = passq.pop()
        
        for i in range(ph-2, ph+3):
            for j in range(pw-2, pw+3):
                if i > 0 and i <= h and j > 0 and j <= w:
                    if sl[i][j] == '.' and tl[i][j] == 0:
                        posq.append([i, j])
                        tl[i][j] = 1
    wcnt = wcnt + 1
    if len(posq) == 0:
        break

# Output
if findflg == True:
    ans = wcnt
else:
    ans = -1
    
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int,input().split())
sx, sy = map(int,input().split())
gx, gy = map(int,input().split())
S = [input() for i in range(h)]

sx-=1
sy-=1
gx-=1
gy-=1

A = [[-1,0],[1,0],[0,-1],[0,1]]
B = []
for i in range(-2,3):
    for j in range(-2,3):
        if i!= 0 or j!=0:
            B.append([i,j])
print(B)

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

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

for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            for a in A:
                ai = i+a[0]
                aj = j+a[1]
                if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                    M[i*w+j].append([ai*w+aj, 0])
            for b in B:
                bi = i+b[0]
                bj = j+b[1]
                if 0 <= bi < h and 0 <= bj < w and S[bi][bj] == ".":
                    M[i*w+j].append([bi*w+bj,1])


# for i in range(len(C)):

#     M[C[i][0]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
#     M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

n = h*w

import heapq

D = [float("inf")] * n  # 頂点0からの距離
P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
D[sx*w+sy] = 0
V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
Q = []  # 優先度付きキュー
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            # print(v)
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, [alt, v])
# print(D)
ans = D[gx*w+gy]
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import time
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush
    s = time.time()
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    S = [['#'] * (W + 4)]
    tmp = ['#'] * (W + 4)
    S.append(tmp)

    for _ in range(H):
        tmp = ['#', '#'] + list(input()) + ['#']
        S.append(tmp)

    tmp = ['#'] * (W + 4)
    S.append(tmp)
    S.append(tmp)
    # print (*S, sep = '\n')

    INF = 10 ** 9

    G = [[INF] * (W + 4) for _ in range(H + 4)] 

    move1 = ((1, 0), (-1, 0), (0, 1), (0, -1))

    pque = [(0, Ch + 1, Cw + 1)]
    G[Ch + 1][Cw + 1] = 0

    while pque:
        t = time.time()
        if (t - s) > 1.5:
            print (2)
            exit()
        xy = heappop(pque)
        tmp, x, y = xy[0], xy[1], xy[2]
        # print (tmp, x, y)
        if G[x][y] < tmp: #すでに小さい
            continue

        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                if dx == 0 and dy == 0:
                    continue
                if S[nx][ny] == '.': #道の時
                    if (dx, dy) in move1:
                        if G[nx][ny] > tmp:
                            G[nx][ny] = tmp
                            heappush(pque, (tmp, nx, ny))
                    else:
                        if G[nx][ny] > tmp + 1:
                            G[nx][ny] = tmp + 1
                            heappush(pque, (tmp + 1, nx, ny))

    # print (*G, sep = '\n')

    if G[Dh + 1][Dw + 1] == INF:
        print (-1)
    else:
        print (G[Dh + 1][Dw + 1])

if __name__ == '__main__':
    main()