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

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

s=[]
for i in range(h):
    sub=input().rstrip()
    s.append(sub)

group=[[-1]*w for i in range(h)]

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

d=[(1,0),(-1,0),(0,1),(0,-1)]

index=0
for i in range(h):
    for j in range(w):
        if not check[i][j] and s[i][j]=='.':
            stack=[(i,j)]
            while len(stack)>0:
                now=stack.pop()
                group[now[0]][now[1]]=index
                check[now[0]][now[1]]=True
                for k in d:
                    x=now[0]+k[0]
                    y=now[1]+k[1]
                    if 0<=x<=h-1 and 0<=y<=w-1:
                        if not check[x][y] and s[x][y]=='.':
                            stack.append((x,y))
            index+=1

G=[set() for i in range(index)]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            now=group[i][j]
            for x in range(-2,3):
                for y in range(-2,3):
                    xt=i+x
                    yt=j+y
                    if 0<=xt<=h-1 and 0<=yt<=w-1:
                        if s[xt][yt]=='.':
                            if group[xt][yt]!=now and not group[xt][yt] in G[now]:
                                G[now].add(group[xt][yt])

s=group[ch-1][cw-1]
g=group[dh-1][dw-1]
from collections import deque
q=[(s,0)]
q=deque(q)
check=[-1]*index
while len(q)>0:
    now=q.popleft()
    check[now[0]]=now[1]
    for i in G[now[0]]:
        if check[i]==-1:
            q.append((i,now[1]+1))
print(check[g])

Submission status: Wrong Answer

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

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

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


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


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

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

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

    g = defaultdict(set)

    @functools.lru_cache(maxsize=None)
    def dfs(x,y,cur_label):
        for dx,dy in diffs:
            xx, yy = x+dx, y+dy
            if labels[xx][yy]:
                continue
            if grid[xx][yy] == 0:
                continue
            labels[xx][yy] = cur_label
            dfs(xx,yy,cur_label)

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


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

    connections = defaultdict(set)

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

    console("connections", connections)

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

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

    console("G", G)

    _, result = dijkstra(G, start)
    
    if result[end] > 10**4:
        return -1
    return result[end]



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

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

for case_num in [1]:
    # read line as a string
    # strr = input()

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

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

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

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

    # Codeforces - no case number required
    print(res)

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())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
d={s:0}
while q:
    y,x=q.popleft()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
            elif d[(ny,nx)]>d[(y,x)]:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
    for dy,dx in [(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(-1,-1),(1,-1),(2,-1),(-2,0),(2,0),(-2,1),(-1,1),(1,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d and (ny-1,nx) not in d and (ny,nx-1) not in d and (ny+1,nx) not in d and (ny+1,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
if g in d:
    print(d[g])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1


max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(dist, start, goal):
    H,W = len(dist),len(dist[0])

    q = [start]
    dist[start[0]][start[1]] = 0
    cnt = 0
    while q:
        nq = []
        while q:
            x,y = q.pop()
            if (x,y) == goal:
                return cnt
            if dist[x][y] < cnt:
                continue
            for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
                nx,ny = x+dx,y+dy
                if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt:
                    dist[nx][ny] = cnt
                    q.append((nx,ny))
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx,ny = x+dx,y+dy
                    if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt+1:
                        dist[nx][ny] = cnt+1
                        nq.append((nx,ny))
        q = nq
        cnt += 1
    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)-1,readline().split()))
    goal = tuple(map(lambda i:int(i)-1,readline().split()))

    dist = [[10**4 if c=='.' else 0 for c in t.decode()] for t in read().split()]

    print(solve(dist,start,goal))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = ['#'*(w+2)]
for _ in range(h):
  s.append('#' + input() + '#')
s.append('#'*(w+2))

from queue import Queue
q1 = Queue()
q2 = Queue()
q1.put(c)
now = c
count = [[-1 for j in range(w+2)] for i in range(h+2)]
num = 0
while not q1.empty() or not q2.empty():
  while not q1.empty():
    now = q1.get()
    for dxy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
          else:
            count[tar[0]][tar[1]] = -2
            q2.put(tar)
    for dxy in [[1, 1], [-1, -1], [-1, 1], [1, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '#':
            count[tar[0]][tar[1]] = -2
            q2.put(tar)
            
  num += 1
            
  while not q2.empty():
    now = q2.get()
    for dxy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
    for dxy in [[1, 1], [-1, -1], [-1, 1], [1, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q2.put(tar)
            
print(count[d[0]][d[1]])

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
atlas = list(input() for i in range(h))
ans = [[float('inf')]*w for i in range(h)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

ex = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
ey = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]

ans[sy-1][sx-1] = 0

for i in range(h):
  for j in range(w):
    for k in range(4):
      next_y, next_x = i+dy[k], j+dx[k]
      if (not 0 <= next_y < h) or (not 0 <= next_x < w):  
        continue 
      if atlas[next_y][next_x] == "#":
        continue
      ans[next_y][next_x] = min(ans[i][j], ans[next_y][next_x])
      
    for k in range(24):
      next_y, next_x = i+ey[k], j+ex[k]
      if (not 0 <= next_y < h) or (not 0 <= next_x < w):  
        continue 
      if atlas[next_y][next_x] == "#":
        continue
      ans[next_y][next_x] = min(ans[i][j]+1, ans[next_y][next_x])

print(ans[gy-1][gx-1])

Submission status: Wrong Answer

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    assert S[h][w]
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(H+4):
    for w in range(W+4):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
        nexts=set(_nexts)

if dist[goal]==10**10:
    print(-1)
else:
    print(dist[goal])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
Sh,Sw = map(int,input().split())
Sh -= 1
Sw -= 1
Gh,Gw = map(int,input().split())
Gh -= 1
Gw -= 1
S = [list(input()) for _ in range(H)]
D = [[-1 for _ in range(W)] for _ in range(H)]
D[Sh][Sw] = -1


walk = [(1,0),(-1,0),(0,1),(1,0)]
warp = [(x,y) for x in range(-2,3) for y in range(-2,3) if abs(x) + abs(y) > 1]

def validPosition(h,w):
	return 0 <= h and h < H and 0 <= w and w < W

search = [(0, Sh, Sw)]
while D[Gh][Gw] == -1:
	walked = []
	# walk
	while len(search) > 0:
		(d, h, w) = search.pop()
		if D[h][w] >= 0:
			continue
		D[h][w] = d
		walked.append((d,h,w))
		for (x,y) in walk:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and D[hh][ww] == -1 and S[hh][ww] == ".":
				search.append((d, hh, ww))
	# warp
	next_search=[]
	for (d,h,w) in walked:
		for (x,y) in warp:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and D[hh][ww] == -1 and S[hh][ww] == ".":
				next_search.append((d+1, hh, ww))
	if len(next_search) == 0:
		break
	search = next_search

print(D[Gh][Gw])

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("#"+input())
        
V=[[999999 for i in range(w+1)] for q in range(h+1)]

V[ch][cw]=0
que=[(ch,cw)]
head=0

    
def ex(nx,ny):
    return ((nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1))

def ex3(nx,ny):
    return ((nx+1,ny+1),(nx-1,ny-1),(nx-1,ny+1),(nx+1,ny-1))

def ex2(nx,ny):
    return ((nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1),(nx+1,ny+1),(nx-1,ny-1),(nx-1,ny+1),(nx+1,ny-1))

def calc(nx,ny):
    if S[nx][ny]==".":
        return 0
    else:
        return 1

while len(que)>head:
    now=que[head]
    head+=1
    if S[now[0]][now[1]]==".":
        for nex in ex(now[0],now[1]):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if V[now[0]][now[1]]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))
        for nex in ex3(now[0],now[1]):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if flg==0:
                    continue
                if V[now[0]][now[1]]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))
    else:
        for nex in ex2(now[0],now[1]):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)*1000000
                if V[now[0]][now[1]]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))

if V[dh][dw]==999999:
    print(-1)
else:
    print(V[dh][dw])

Submission status: Wrong Answer

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def valid(a, b):
    return 0 <= a < n and 0 <= b < m


n, m = sp()
sx, sy = sp()
ex, ey = sp()
sx -= 1
sy -= 1
ex -= 1
ey -= 1
mat = [list(data()) for i in range(n)]
answer = 10 ** 10
q = deque()
q.append([sx, sy, 0])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
vis = [[0] * m for _ in range(n)]
while q:
    sx, sy, jm = q.popleft()
    if sx == ex and sy == ey:
        answer = min(answer, jm)
        break
    cnt = 0
    for i in range(4):
        tx, ty = sx + x[i], sy + y[i]
        if valid(tx, ty) and mat[tx][ty] == ".":
            if tx == ex and ty == ey:
                answer = min(answer, jm)
                cnt += 1
            elif not vis[tx][ty]:
                cnt += 1
                q.append([tx, ty, jm])
                vis[tx][ty] = 1
    if cnt == 0:
        jm += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                if valid(sx + i, sy + j) and mat[sx + i][sy + j] == ".":
                    if sx + i == ex and sy + j == ey:
                        answer = min(answer, jm)
                    elif not vis[sx + i][sy + j]:
                        q.append([sx + i, sy + j, jm])
                        vis[sx + i][sy + j] = 1
if answer == 10 ** 10:
    print(-1)
    exit()
print(answer)

Submission status: Wrong Answer

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
done = [[False]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw,0))
done[ch][cw] = True
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury,magic = q.popleft()
	#can_vis.append((curx,cury))
	f = 0
	if curx == dh and cury == dw:
		ans = min(ans, magic)
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and not done[curx+dx][cury+dy]:
			done[curx+dx][cury+dy] = True
			q.append((curx+dx, cury+dy,magic))
			f = 1
	if f: continue
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and not done[curx+dx][cury+dy]:
				done[curx+dx][cury+dy] = True
				q.append((curx+dx, cury+dy,magic+1))


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

Submission status: Wrong Answer

Solution code:
from collections import deque

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 = [0]*H
hoge = 0
for i in range(H):
    S[i] = [-1]*W
    hoge = input()
    for j in range(W):
        if hoge[j] == ".":
            S[i][j] = 10000

AAA = (-2,-1,0,1,2)
DDD = [0]*25
dddd = 0
for dx in AAA:
    for dy in AAA:
        DDD[dddd] = (dx,dy,dx * dx + dy * dy)
        dddd += 1

D = deque()
D.append((CH,CW,0))
S[CH][CW] = 0
while len(D):
    X,Y,DD = D.pop()
    for dx,dy,a in DDD:
        XX = X + dx
        YY = Y + dy
        if a == 0 or not(0<=XX<H) or not(0<=YY<W) or S[XX][YY] == -1:
            continue
        elif a == 1 and S[XX][YY] > DD:
            D.append((XX,YY,DD))
            S[XX][YY] = DD
        elif S[XX][YY] > DD + 1:
            D.appendleft((XX,YY,DD+1))
            S[XX][YY] = DD + 1

print(-1 if S[DH][DW] == 10000 else S[DH][DW])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def solve():
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Sss = ['#'*(W+4)] + ['#'*(W+4)] + ['##'+input().rstrip()+'##' for _ in range(H)] + ['#'*(W+4)] + ['#'*(W+4)]

    Ch, Cw, Dh, Dw = Ch+1, Cw+1, Dh+1, Dw+1

    usedss = [[0]*(W+4) for _ in range(H+4)]
    for x in range(H+4):
        for y in range(W+4):
            if Sss[x][y] == '#':
                usedss[x][y] = 1

    ans = 0
    vs = set([(Ch, Cw)])
    vNews = set([(Ch, Cw)])
    usedss[Ch][Cw] = 1
    while True:
        while vs:
            v2s = set()
            for x, y in vs:
                for dx, dy in dxys:
                    x2, y2 = x+dx, y+dy
                    if usedss[x2][y2]: continue
                    v2s.add((x2, y2))
                    vNews.add((x2, y2))
                    usedss[x2][y2] = 1
            vs = v2s

        if usedss[Dh][Dw]:
            print(ans)
            break

        if not vNews:
            print(-1)
            break

        vs = set()
        for x, y in vNews:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    x2, y2 = x+dx, y+dy
                    if usedss[x2][y2]: continue
                    vs.add((x2, y2))
                    usedss[x2][y2] = 1

        ans += 1
        vNews = set()


solve()

Submission status: Wrong Answer

Solution code:
# D - Wizard in Maze
from collections import deque
import sys
INF = 10000000

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]
C = [[-1]*W for _ in range(H)]
R = [[INF]*W for _ in range(H)]
C[Ch-1][Cw-1] = 1
R[Ch-1][Cw-1] = 0
que = deque([(Ch,Cw)])
next_que = deque([])
tmp = 0

while True:
    while len(que)>0:
        i,j = que.popleft()
        if (i,j)==(Dh,Dw):
            print(R[i-1][j-1])
            sys.exit()
        for h in range(i-2,i+3):
            for w in range(j-2,j+3):
                if h<1 or H<h or w<1 or W<w or S[h-1][w-1]=='#' or (h,w)==(i,j):
                    continue
                if (h,w) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] and C[h-1][w-1]!=1:
                    C[h-1][w-1] = 1
                    R[h-1][w-1] = tmp
                    que.append((h,w))
                elif C[h-1][w-1]==-1:
                    C[h-1][w-1] = 0
                    R[h-1][w-1] = tmp+1
                    next_que.append((h,w))
    if len(next_que)==0:
        print(-1)
        sys.exit()
    que = next_que
    tmp += 1

Submission status: Wrong Answer

Solution code:
INF = 10**18

def main():

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch, cw = ch-1, cw-1
    dh, dw = dh-1, dw-1
    #M = [list(str(input())) for _ in range(h)]

    M = [str(input()) for _ in range(h)]
    #M = ['#'*w] + M + ['#'*w]
    #M = ['#'+c+'#' for c in M]

    from collections import deque
    q = deque()
    q.append((ch, cw))

    visit = [[-1]*w for _ in range(h)]
    visit[ch][cw] = 0
    C = [[INF]*w for _ in range(h)]
    C[ch][cw] = 0

    import itertools
    cnt = 0
    while q:
        y, x = q.popleft()
        #if y == dh and x == dw:
            #break
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                C[ny][nx] = min(C[y][x], C[ny][nx])
                if visit[ny][nx] == -1 and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]
                    #C[ny][nx] = min(C[y][x], C[ny][nx])
                    q.appendleft((ny, nx))
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0:
                    continue
                ny, nx = y+dy, x+dx
                if 0 <= ny < h and 0 <= nx < w:
                    C[ny][nx] = min(C[y][x]+1, C[ny][nx])
                    if visit[ny][nx] == -1 and M[ny][nx] != '#':
                        visit[ny][nx] = visit[y][x]
                        #C[ny][nx] = min(C[y][x]+1, C[ny][nx])
                        q.append((ny, nx))
    #print(visit)
    #print(C)
    if visit[dh][dw] == -1:
        print(-1)
    else:
        print(C[dh][dw])

if __name__ == '__main__':
    main()