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: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0<=i+ii and i+ii<h and 0<=j+jj and \
                j+jj<w and s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            if 0<=i+ii and i+ii<h and 0<=j+jj and \
                j+jj<w and s[i+ii][j+jj]=="#":
                if not ((i,j) in wpg):
                    wpg.append((i,j))        
#                print(i,j,g[i][j])
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
#qq=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()
#                for hk,wk in gg[hj][wj]:
#                    if parent[hk][wk] !=-1:
#                        continue
#                    parent[hk][wk]=(hj,wj)
#                    dist[hk][wk]=dist[hj][wj]+10**7
#                    qq.append((hk,wk))
#                    if hk==dh and wk==dw:
#                        print(dist[dh][dw]//(10**7))   
#                        sys.exit()
#        print("q3:",q)
    
#    print("qq:",qq)
    while qq:
        hi,wi = qq.popleft()
#        if parent[hi][wi]!=0 and parent[hi][wi]!=-1:
#            continue
        for hj,wj in gg[hi][wi]:
#       q.append((hi,wi))
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

#    for hj,wj in gg[hi][wi]:
#        if parent[hj][wj] !=-1:
#            continue
#        else:
#            parent[hj][wj]=(hi,wi)
#            dist[hj][wj]=dist[hi][wi]+10**7
#            q.append((hj,wj))
#            if hj==dh and wj==dw:
#                print(dist[dh][dw]//(10**7))   
#                sys.exit()
#    print("q2:",q)
    if len(q)==0:
        break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    q = deque()
    q1 = deque()
    q.append([ch[0]-1, ch[1]-1, 0])
    
    ans = float('inf')
    
    while q:
        a0, a1, a2 = q.popleft()
        q1.append([a0, a1, a2])
        s[a0][a1] = '#'
        if a0 == dh[0]-1 and a1 == dh[1]-1:
            ans = a2
            break

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = a0+i, a1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] == '.' and ans > a2:
                    q.appendleft([x, y, a2])
        if len(q) == 0:
            while q1:
                a0, a1, a2 = q1.popleft()
                for i in range(-2, 3):
                    for j in range(-2, 3):
                        x, y = a0+i, a1+j
                        if 0 <= x < h and 0 <= y < w:
                            if s[x][y] == '.' and ans > a2:
                                q.append([x, y, a2+1])
    
    if ans == float('inf'):
        return(-1)
    else:
        return(ans)
print(num())

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
        for dh in range(-2, 3):
            for dw in range(-2, 3): # [dh,dw]:[-2,-2]~[2,2]
                if dh*dh + dw*dw > 1: dq.append((h + dh, w + dw, d+1))
                else: dq.appendleft((h + dh, w + dw, d))

print(dst[eh][ew])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    q = deque()
    q.append([ch[0]-1, ch[1]-1, 0])
    ans = float('inf')
    
    while q:
        a0, a1, a2 = q.popleft()
        s[a0][a1] = '#'
        if a0 == dh[0]-1 and a1 == dh[1]-1:
            ans = a2
            break

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1),
                     (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)):
            x, y = a0+i, a1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] == '.' and ans > a2:
                    if abs(i)+abs(j) <= 1:
                        q.appendleft([x, y, a2])
                    else:
                        q.append([x, y, a2+1])
    
    if ans == float('inf'):
        return(-1)
    else:
        return(ans)
print(num())

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
from collections import deque
from numba import jit

grid =  ''
grid +=  '#' * (W+4) * 2
for h in range(H):
  S = str(input())
  grid += '#' * 2 + S + '#' * 2
grid +=  '#' * (W+4) * 2

Dire = [W+4, -W-4, 1, -1]
WAAP_ = [
  -2*(W+4)-2,-2*(W+4)-1,-2*(W+4), -2*(W+4)+1, -2*(W+4)+2, 
  -1*(W+4)-2,-1*(W+4)-1,-1*(W+4), -1*(W+4)+1, -1*(W+4)+2, 
  -2, -1, 1, 2,
  1*(W+4)-2,1*(W+4)-1,1*(W+4), 1*(W+4)+1, 1*(W+4)+2, 
  2*(W+4)-2,2*(W+4)-1,2*(W+4), 2*(W+4)+1, 2*(W+4)+2, 
]
start = 2 * (W+4) + (Ch - 1) * (W+4) + 2 + (Cw - 1)
end = 2 * (W+4) + (Dh - 1) * (W+4) + 2 + (Dw - 1)

@jit
def WAAP(lst):
  res =  []
  for l in lst:
    for waap_ in  WAAP_:
      l_ = l+ waap_
      if grid[l_] == '.' and l_ not in res:
        res.append(l_)
  return res
        
        
    

def dfs(wwww, stack):
  fin =  []
  
  while True:
    if len(stack) == 0:
      for f in fin:
        grid[f] == '#'
      waap = WAAP(fin)
      return False, waap
      break
    q = stack.pop()
    fin.append(q)
    if q == end:
      return True, wwww
    else:
      for d in Dire:
        new_q = q + d
        if grid[new_q] == '.' and  new_q not in fin and new_q not in stack:
          stack.append(new_q)
          
          
          
          
def main():
  stack_ = deque([start])
  ans = 0
  while True:
    is_fin, res = dfs(ans, stack_)
    if is_fin:
      print(ans)
      break
    else:
      if len(res) == 0:
        print(-1)
        break
      stack_ = deque(res)
      ans += 1
      
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
ch = list(map(int, input().split()))
dh = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

q = deque()
q.append([ch[0]-1, ch[1]-1, 0])
ans = float('inf')

while q:
    a0, a1, a2 = q.popleft()
    s[a0][a1] = '#'
    if a0 == dh[0]-1 and a1 == dh[1]-1:
        ans = a2
        break

    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1),
                 (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)):
        x, y = a0+i, a1+j
        if 0 <= x < h and 0 <= y < w:
            if s[x][y] == '.' and ans > a2:
                if abs(i)+abs(j) <= 1:
                    q.appendleft([x, y, a2])
                else:
                    q.append([x, y, a2+1])

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

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())

sy, sx = map(int, input().split())
sy -= 1
sx -= 1
gy, gx = map(int, input().split())
gy -= 1
gx -= 1

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

from collections import deque
d = deque()

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

d.append([sy,sx,0])

while len(d) > 0:
    y,x,c = d.popleft()
    
    if visited[y][x] is True:
        continue
    
    if gy == y and gx == x:
        print(c)
        exit(0)

    dxy = [[1,0], [-1, 0], [0, 1], [0, -1]]
    for dx, dy in dxy:
        nx = dx + x
        ny = dy + y
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue
        if s[ny][nx] == "#":
            continue
        if visited[ny][nx] is True:
            continue
        d.appendleft([ny, nx, c])

    for dy in range(-2, 3):
        for dy in range(-2, 3):
            nx = dx + x
            ny = dy + y
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            if s[ny][nx] == "#":
                continue
            if visited[ny][nx] is True:
                continue
            d.append([ny, nx, c+1])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
ch = list(map(int, input().split()))
dh = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

q = deque()
q.append([ch[0]-1, ch[1]-1, 0])
ans = float('inf')

while len(q) != 0:
    a0, a1, a2 = q.popleft()
    s[a0][a1] = '#'
    if a0 == dh[0]-1 and a1 == dh[1]-1:
        ans = a2
        break

    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1),
                 (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)):
        x, y = a0+i, a1+j
        if 0 <= x < h and 0 <= y < w:
            if s[x][y] == '.':
                if abs(i)+abs(j) <= 1:
                    q.appendleft([x, y, a2])
                else:
                    q.append([x, y, a2+1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys

# D - Wizard in Maze
def get_index(s):
	return int(s) - 1


def search(h, w):
  global que
  
  if can_reach(h, w):
    que.append([h, w])


def can_reach(h, w):
	global H
	global W
	global maze
	
	if h < 0 or h >= H or w < 0 or w >= W:
		return False
	elif maze[h][w] == '#':
		return False
	else:
		return True
	

from collections import deque
import copy

H, W = map(int, input().split())
Ch, Cw = map(get_index, input().split())
Dh, Dw = map(get_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

costs = [[-1] * W for _ in range(H)]
que = deque()
que.append([Ch, Cw])

next_que = deque()
next_que.append([Ch, Cw])

# コスト(ワープ魔法を使った回数)
i = 0

while len(next_que) > 0:
  que = copy.deepcopy(next_que)
  next_que.clear()
  
  # コストiで到達可能なマスを列挙
  while len(que) > 0:
	  h, w = que.popleft()
	  costs[h][w] = i
	
	  next_que.append([h, w])
	
	  # 上下左右に隣接するマスを探索
	  search(h + 1, w)
	  search(h - 1, w)
	  search(h, w + 1)
	  search(h, w - 1)
	 
  i += 1

print(costs[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
ch = list(map(int, input().split()))
dh = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

q = deque()
q.append([ch[0]-1, ch[1]-1, 0])
ans = float('inf')

while len(q) != 0:
    a = q.popleft()
    s[a[0]][a[1]] = '#'
    if a[2] >= ans:
        continue
    if a[0] == dh[0]-1 and a[1] == dh[1]-1:
        ans = min(ans, a[2])
        break

    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1),
                 (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)):
        x, y = a[0]+i, a[1]+j
        if 0 <= x < h and 0 <= y < w:
            if s[x][y] == '.':
                if abs(i)+abs(j) <= 1:
                    q.appendleft([x, y, a[2]])
                else:
                    q.append([x, y, a[2]+1])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
ch = list(map(int, input().split()))
dh = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

q = deque()
q.append([ch[0]-1, ch[1]-1, 0])
ans = float('inf')

while len(q) != 0:
    a = q.popleft()
    s[a[0]][a[1]] = '#'
    if a[2] >= ans:
        continue
    if a[0] == dh[0]-1 and a[1] == dh[1]-1:
        ans = min(ans, a[2])

    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1),
                 (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)):
        x, y = a[0]+i, a[1]+j
        if 0 <= x < h and 0 <= y < w:
            if s[x][y] == '.':
                if abs(i)+abs(j) <= 1:
                    q.appendleft([x, y, a[2]])
                else:
                    q.append([x, y, a[2]+1])

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

Submission status: Time Limit Exceeded

Solution code:
import queue

def main():
    h,w = map(int,input().split())
    Ch,Cw = map(lambda x:int(x)+1,input().split())
    Dh, Dw = map(lambda x:int(x)+1,input().split())

    maze = []
    for i in range(2):
        maze.append(['#' for j in range(4+w)])
    for i in range(h):
        maze.append(['#' for j in range(2)]+list(input())+ ['#' for j in range(2)])
    for i in range(2):
        maze.append(['#' for j in range(4+w)])

    # for i in range(len(maze)):
    #     print(''.join(maze[i]))

    maze_separate = [[0 for i in range(len(maze[0]))] for j in range(len(maze))]
    number = 1
    for i in range(len(maze_separate)):
        for j in range(len(maze_separate[i])):
            if maze[i][j]=='.' and maze_separate[i][j]==0:
                maze_separate[i][j] = number
                number += 1
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    x,y = q.get()
                    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                        if maze[x+dx][y+dy] == '.' and maze_separate[x+dx][y+dy]==0:
                            maze_separate[x+dx][y+dy] = maze_separate[x][y]
                            q.put([x+dx,y+dy])

    # for i in range(len(maze_separate)):
    #     print(maze_separate[i])

    q = queue.Queue()
    q.put([Ch,Cw,0])
    while not q.empty():
        x,y,cnt = q.get()
        # print(x,y,cnt)
        if x==Dh and y == Dw:
            print(cnt)
            return 
        else:
            for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                if maze[x+dx][y+dy] == '.':
                   maze[x+dx][y+dy] = '#'
                   q.put([x+dx,y+dy,cnt]) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if maze[x+dx][y+dy] == '.' and maze_separate[x+dx][y+dy] != maze_separate[x][y]:
                        q.put([x+dx,y+dy,cnt+1]) 
    print(-1)
    

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W=map(int,input().split())
cx,cy=map(lambda x: int(x)+1,input().split())
dx,dy=map(lambda x: int(x)+1,input().split())
S=["#"*(W+4)]*2+["##"+input()+"##" for i in range(H)]+["#"*(W+4)]*2
l=[[-2]*(W+4) for i in range(H+4)]
for i in range(2,H+2):
    for j in range(2,W+2):
        if S[i][j]==".":
            l[i][j]=-1
l[cx][cy]=0
b=[(cx,cy)]
bb=[(cx,cy)]
t=0
while bb:
    while b:
        a=[]
        for i in b:
            if l[i[0]+1][i[1]]==-1:
                l[i[0]+1][i[1]]=t
                a.append((i[0]+1,i[1]))
            if l[i[0]-1][i[1]]==-1:
                l[i[0]-1][i[1]]=t
                a.append((i[0]-1,i[1]))
            if l[i[0]][i[1]+1]==-1:
                l[i[0]][i[1]+1]=t
                a.append((i[0],i[1]+1))
            if l[i[0]][i[1]-1]==-1:
                l[i[0]][i[1]-1]=t
                a.append((i[0],i[1]-1))
        bb+=a
        b=a
    aa=[]
    t+=1
    b=[]
    for i in bb:
        for j in range(-2,3):
            for k in range(-2,3):
                if l[i[0]+j][i[1]+k]==-1:
                    l[i[0]+j][i[1]+k]=t
                    aa.append((i[0]+j,i[1]+k))
                    b.append((i[0]+j,i[1]+k))
    if l[dx][dy]>=0:
        break
    bb=aa
print(l[dx][dy])

Submission status: Time Limit Exceeded

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

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        alt = d[i][j] 
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for k,l in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="." and d[i+a][j+b] > alt]:
            d[k][l] = alt
            Q.append((k,l))
        alt += 1
        for k,l in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="." and d[i+a][j+b] > alt]:
            d[k][l] = alt
            Q.appendleft((k,l))
    print(ans)



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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        alt = d[i][j] 
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for pos2 in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            if d[k][l] > alt:
                d[k][l] = alt
                Q.append((k,l))
        alt += 1
        for pos2 in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            if d[k][l] > alt:
                d[k][l] = alt
                Q.appendleft((k,l))
    print(ans)



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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for pos2 in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j] 
            if d[k][l] > alt:
                d[k][l] = alt
                Q.append((k,l))
        for pos2 in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j]+1
            if d[k][l] > alt:
                d[k][l] = alt
                Q.appendleft((k,l))
    print(ans)



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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#ABC176
#D - Wizard in Maze
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
x=0

for i in range(h):
  a.append(list(input()))

warp=0

while len(c)>0:
  ch,cw=c[0]
  c.pop(0)
  if ch==dh-1 and cw==dw-1:
    print(warp)
    x=1
    c=[]
  else:
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
      
    e=[[ch-1,cw],[ch+1,cw],[ch,cw-1],[ch,cw+1]]

    for i in e:
      ch1,cw1=i
      if i not in d and 0<=ch1<h and 0<=cw1<w:
        if a[ch1][cw1]==".":
          c.append(i)
          d.append(i)
    for i in range(5):
        ch0=ch-2+i
        if 0<=ch0<h:
            for j in range(5):
                cw0=cw-2+j
                if 0<=cw0<w:
                    f.append([ch0,cw0])
    if len(c)==0:
      warp=warp+1
      for i in f:
        ch1,cw1=i
        if i not in d:
          if a[ch1][cw1]==".":
            c.append(i)
            d.append(i)
      f=[]
if x!=1:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#ABC176
#D - Wizard in Maze
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
x=0

for i in range(h):
  a.append(list(input()))

warp=0

while len(c)>0:
  ch,cw=c[0]
  c.pop(0)
  if ch==dh-1 and cw==dw-1:
    print(warp)
    x=1
    c=[]
  else:
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
      
    e=[[ch-1,cw],[ch+1,cw],[ch,cw-1],[ch,cw+1]]

    for i in e:
      ch1,cw1=i
      if i not in d and 0<=ch1<h and 0<=cw1<w:
        if a[ch1][cw1]!="#":
          c.append(i)
          d.append(i)
    for i in range(5):
        ch0=ch-2+i
        if 0<=ch0<h:
            for j in range(5):
                cw0=cw-2+j
                if 0<=cw0<w:
                    f.append([ch0,cw0])
    if len(c)==0:
      warp=warp+1
      for i in f:
        ch1,cw1=i
        if i not in d:
          if a[ch1][cw1]==".":
            c.append(i)
            d.append(i)
      f=[]
if x!=1:
  print(-1)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())

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

visited = {}

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

queue = deque([(ch-1, cw-1, 0)])
ans = float("inf")

visited[(ch-1, cw-1)] = 0
while queue:
    y, x, cnt = queue.popleft()

    if y == dh-1 and x == dw-1:
        print(cnt)
        exit()

    for a, b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+a, x+b
        if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
            if (new_y, new_x) not in visited or visited[(new_y, new_x)] > cnt:
                queue.appendleft((new_y, new_x, cnt))
                visited[(new_y, new_x)] = cnt

    for a in range(-2, 3):
        for b in range(-2, 3):
            new_y, new_x = y + a, x + b
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
                if (new_y, new_x) not in visited or visited[(new_y, new_x)] > cnt + 1:
                    queue.append((new_y, new_x, cnt+1))
                    visited[(new_y, new_x)] = cnt+1

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

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())

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

visited = {}

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

queue = deque([(ch-1, cw-1, 0)])
ans = float("inf")

visited[(ch-1, cw-1)] = 0
while queue:
    y, x, cnt = queue.popleft()

    if y == dh-1 and x == dw-1:
        ans = min(ans, cnt)

    for a, b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+a, x+b
        if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
            if (new_y, new_x) not in visited or visited[(new_y, new_x)] > cnt:
                queue.append((new_y, new_x, cnt))
                visited[(new_y, new_x)] = cnt

    for a in range(-2, 3):
        for b in range(-2, 3):
            new_y, new_x = y + a, x + b
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
                if (new_y, new_x) not in visited or visited[(new_y, new_x)] > cnt + 1:
                    queue.append((new_y, new_x, cnt+1))
                    visited[(new_y, new_x)] = cnt+1

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

Submission status: Time Limit Exceeded

Solution code:
#ABC176
#D - Wizard in Maze
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
x=0

for i in range(h):
  a.append(list(input()))

warp=0

while len(c)>0:
  ch,cw=c[0]
  c.pop(0)
  if ch==dh-1 and cw==dw-1:
    print(warp)
    x=1
    c=[]
  else:
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
      
    e=[[ch-1,cw],[ch+1,cw],[ch,cw-1],[ch,cw+1]]

    for i in e:
      ch1,cw1=i
      if i not in d and 0<=ch1<h and 0<=cw1<w:
        if a[ch1][cw1]!="#":
          c.append(i)
          d.append(i)
    for i in range(5):
        ch0=ch-2+i
        for j in range(5):
          cw0=cw-2+j
          f.append([ch0,cw0])
    if len(c)==0:
      warp=warp+1
      for i in f:
        ch1,cw1=i
        if i not in d and 0<=ch1<h and 0<=cw1<w:
          if a[ch1][cw1]!="#":
            c.append(i)
            d.append(i)
      f=[]
if x!=1:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	rows, cols = rli()
	r0, c0 = rli(); r0 -= 1; c0 -= 1;
	r1, c1 = rli(); r1 -= 1; c1 -= 1;
	G = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "#": 
				row.append(1)
			else:
				row.append(0)
		G.append(row)

	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols	
	seen = defaultdict(lambda: False)
	Q = deque() #(num magics, r, c)
	Q.append((0, r0, c0))
	ans = INF
	while Q:
		magics, r, c = Q.pop()
		if seen[(r, c)]: continue
		seen[(r, c)] = True
		if r == r1 and c == c1:
			ans = magics 
			break
		for dr in range(-2, 3):
			for dc in range(-2, 3):
				nr, nc = r + dr, c + dc 
				if not inside(nr, nc) or seen[(nr, nc)] or G[nr][nc] == 1: continue
				if abs(dr) + abs(dc) > 1:
					Q.appendleft((magics+1, nr, nc))
				else:
					Q.append((magics, nr, nc))
	print(ans if ans < INF else -1)
	stdout.close()

if __name__ == "__main__":
	main()