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


def solvemaze(y, x, num):
    maps.append([])
    dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
    maze[y][x] = num
    que = deque()
    que.append((y, x))
    while que:
        y_, x_ = que.popleft()
        maps[num].append((y_, x_))
        for i in range(4):
            y2 = y_ + dy[i]
            x2 = x_ + dx[i]
            if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] == '.':
                maze[y2][x2] = num
                que.append((y2, x2))

def makeroute(s_maps, num):
    res = []
    for y, x in s_maps:
        for i in range(-2, 3):
            for j in range(-2, 3):
                y2 = y + i
                x2 = x + j
                if 0 <= y2 < h and 0 <= x2 < w and not maze[y2][x2] in (num,'#') and not maze[y2][x2] in res:
                    res.append(maze[y2][x2])
    
    return res
    

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[x for x in input()] for _ in range(h)]
maps = []

num = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            solvemaze(i, j, num)
            num += 1

E = [[] for _ in range(num)]
for i in range(num):
    E[i] = makeroute(maps[i], i)

s = maze[Ch-1][Cw-1]
g = maze[Dh-1][Dw-1]
used = [False] * num
used[s] = True
que = deque()
que.append((0, s))
cost = [float('inf')] * num
cost[s] = 0
while que:
    c, v = que.popleft()
    for e in E[v]:
        if not used[e]:
            que.append((c+1, e))
            cost[e] = c+1
            used[e] = True
if not used[g]:
    print(-1)
else:
    print(cost[g])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
    s.extend(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft


while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh * w + nw] == '.':
            stack_append([nh, nw, cnt])
    for nh in range(curh-2, curh+3):
        if nh >= 0 and nh < h:
            for nw in range(curw-2,curw+3):
                if nw >= 0 and nw < w and s[nh * w + nw] == '.':
                     stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys


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


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
data=[[0]*W for i in range(H)]
for i in range(H):
    S =input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0    


def trans(h, w):
    return W*(h) + w


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

G = [[] for i in range(H*W)]
for i in range(H):
    for j in range(W):
        if data[i][j] == 1:
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                    u, v = trans(i, j), trans(dx+i, dy+j)
                    G[u].append((v, 0))
                    G[v].append((u, 0))
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 1))
                        G[v].append((u, 1))

D = [10**10 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

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

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#":
            edges[cnt].add((i, j))

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

invalid_pos = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) in  invalid_pos: continue
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num and mapped[x][y] not in g[num]:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))
    if isFind:
        break

if not isFind:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from collections import defaultdict, deque


def A(n, x, t):
  return ceil(n / x) * t


def B(n_str):
  s = 0
  for c in n_str:
    s += int(c)
  if s % 9 == 0:
    return 'Yes'
  return 'No'


def C(n, a):
  ans = 0
  for i in range(1, n):
    if a[i - 1] > a[i]:
      ans += a[i - 1] - a[i]
      a[i] = a[i - 1]
  return ans


def D(h, w, ch, cw, dh, dw, g):

  def _dfs(i, j, mark):
    if i < 0 or i >= h + 4 or j < 0 or j >= w + 4:
      return False
    if g[i][j] != '.':
      return False

    g[i][j] = str(mark)
    _dfs(i - 1, j, mark)
    _dfs(i + 1, j, mark)
    _dfs(i, j - 1, mark)
    _dfs(i, j + 1, mark)

    return True

  # for i in range(h + 4):
  #   print(''.join(g[i]))

  # print()

  cnt_mark = 0
  for i in range(2, h + 2):
    for j in range(2, w + 2):
      ret = _dfs(i, j, cnt_mark)
      if ret:
        cnt_mark += 1

  start_mark = int(g[ch + 1][cw + 1])
  end_mark = int(g[dh + 1][dw + 1])

  # for i in range(h + 4):
  #   print(''.join(g[i]))

  # print()

  def _find_adj(i, j):
    for k in range(i - 2, i + 3):
      for l in range(j - 2, j + 3):
        if g[k][l] != '#' and g[k][l] != g[i][j]:
          return int(g[k][l])

  adj_list = defaultdict(set)
  for i in range(2, h + 2):
    for j in range(2, w + 2):
      if g[i][j] != '#':
        adj = _find_adj(i, j)
        if adj:
          adj_list[int(g[i][j])].add(adj)
          adj_list[adj].add(int(g[i][j]))


  def _bfs(start, end, adj_list):
    # print(start, end, adj_list)
    d = deque([start])
    level = 0
    while len(d) > 0:
      # print(level, d)
      cur = d.popleft()
      if cur == end:
        return level
      if len(d) == 0:
        level += 1
      d.extend(adj_list[cur])
    return -1

  return _bfs(start_mark, end_mark, adj_list)


def main():
  # n, x, t = map(int, input().split())
  # print(A(n, x, t))
  # n_str = input()
  # print(B(n_str))
  # n = int(input())
  # a = list(map(int, input().split()))
  # print(C(n, a))

  h, w = list(map(int, input().split()))
  ch, cw = list(map(int, input().split()))
  dh, dw = list(map(int, input().split()))
  g = []
  g.append(['#'] * (w + 4))
  g.append(['#'] * (w + 4))
  for i in range(h):
    g.append(['#', '#'] + list(input()) + ['#', '#'])
  g.append(['#'] * (w + 4))
  g.append(['#'] * (w + 4))
  print(D(h, w, ch, cw, dh, dw, g))


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
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())
S = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    for h,w in now:      
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:

import collections

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze = [list(input()) for i in range(h)]

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

field = [[False for i in range(w)] for j in range(h)]
field[sy][sx] = True
dx = [1,0,-1,0]
dy = [0,1,0,-1]

q = collections.deque()
q2 = collections.deque()
q.append((sy,sx))
q2.append((sy,sx))
ans = 10**9
count = 0
maze[sy][sx] = 0

def f(count):
    while q:
        s = q.popleft()
        y,x = s[0],s[1]
        count = maze[y][x]
        for i in range(4):
            newy = y + dy[i]
            newx = x + dx[i]
            if 0<=newy<h and 0<=newx<w:
                if maze[newy][newx] == ".":
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                elif maze[newy][newx] != "#" and field[newy][newx] == False:
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                field[newy][newx] = True
        for ddy in range(-2,3):
            for ddx in range(-2,3):
                newy = y+ddy
                newx = x+ddx
                if  0<=newy<h and 0<=newx<w:
                    if maze[newy][newx] == "." and field[newy][newx] == False:
                        maze[newy][newx] = count+1
                        q.append((newy,newx))

f(count)
if maze[gy][gx] != ".":
    print(maze[gy][gx])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections

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

Chw = list(map(int, input().split()))
Dhw = list(map(int, input().split()))

Ss = []
for _ in range(H):
    tmp = input()
    Ss.append(list(tmp))

mazeArray = np.zeros((H+6, W+6), dtype = 'int64')

for i in range(H+6):
    for j in range(W+6):
        if(i < 3 or i > H+2):
            mazeArray[i][j] = -1
        
        elif(j < 3 or j > W+2):
            mazeArray[i][j] = -1
        
        else:
            if(Ss[i - 3][j-3] == "#"):
                mazeArray[i][j] = -1
            else:
                mazeArray[i][j] = 100000

#前準備完了

H_que = collections.deque()
W_que = collections.deque()

H_que.append(Chw[0])
W_que.append(Chw[1])

mazeArray[Chw[0]+2][Chw[1]+2] = 0

#print(mazeArray)

for _ in range(5*10**6):
    H_iti = H_que.popleft() + 2
    W_iti = W_que.popleft() + 2

    #上移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti - 1][W_iti]):
        mazeArray[H_iti - 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 3)
        W_que.append(W_iti - 2)

    elif(mazeArray[H_iti - 1][W_iti] == -1):
        for i in range(H_iti-2, H_iti):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)
                
    #下移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti + 1][W_iti]):
        mazeArray[H_iti + 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 1)
        W_que.append(W_iti - 2)
        
    elif(mazeArray[H_iti+1][W_iti] == -1):
        for i in range(H_iti+1, H_iti+3):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #左移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti - 1]):
        mazeArray[H_iti][W_iti - 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 3)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti -2, W_iti):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #右移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti + 1]):
        mazeArray[H_iti][W_iti + 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 1)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti +1, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #移動Bパターン


    if(len(H_que) == 0):
        break

#print(mazeArray)

if(mazeArray[Dhw[0]+2][Dhw[1]+2] == 100000):
    print(-1)

else:
    print(mazeArray[Dhw[0]+2][Dhw[1]+2])

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

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)


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:
import numpy as np
from collections import deque
from itertools import combinations 
import sys

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

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

def DFS(que):
    while que:
        X, Y = que.popleft()
        seen[X][Y] = 1
        D = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dx, dy in D:
            if 0<= X + dx < H and 0 <= Y + dy < W:
                if M[X + dx][Y + dy] == "." and seen[X + dx][Y + dy] == 0:
                    que.append((X + dx, Y + dy))

ans = 0 
while que:
    x, y = que[-1]
    DFS(que)
    if seen[Dh-1][Dw-1]!=0:
        print(ans)
        sys.exit()
    for i in range(H):
        for j in range(W):
            if seen[i][j]==1:
                seen[i][j]=2
                for dx in range(-2, 3):
                    for dy in range(-2, 3):
                        if 0<= i + dx < H and 0 <= j + dy < W:
                            if M[i+dx][j+dy] == '.' and seen[i+dx][j+dy] == 0:
                                que.append((i+dx, j+dy))
    ans += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))
import collections
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	count = 0
	for v in [(u[0]-1,u[1]-1), (u[0]-1,u[1]), (u[0]-1,u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	for v in [(u[0],u[1]-1), (u[0],u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	for v in [(u[0]+1,u[1]-1), (u[0]+1,u[1]), (u[0]+1,u[1]+1)]:
		if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '#': count +=1
	if count == 0:
		return []

	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0] + i,u[1] + j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				if v != u: ret.append(v)
	return ret
def f(s,t,mat):
	if all(['#' not in l for l in mat]):
		return 0

	heap = [(0,s)]
	r = {} 
	while(heap):
		d,u = heapq.heappop(heap)
		if u in r and d > r[u]: continue
		r[u] = min(r[u] if u in r else +float('inf'), d)
		if u == t:
			return d

		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d:
					heapq.heappush(heap,(d,v))
					r[v] = d
		for v in neighbors(u,mat):
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d + 1:
					heapq.heappush(heap,(d+1,v))
					r[v] = d + 1
	return -1

def g(s,t,mat):
	q = collections.deque([s])
	vis = set()
	while(q):
		u = q.popleft()
		vis.add(u)
		if u == t:
			return True
		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < len(mat) and 0 <= v[1] < len(mat[0]) and mat[v[0]][v[1]] == '.' and v not in vis:
				vis.add(v)
				q.append(v)

	return False



if False:# g(s,t,mat):
	print 0
else:
	print f(s,t,mat)

Submission status: Time Limit Exceeded

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

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

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

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

    if dp[goal[0]][goal[1]] == float('inf'):
        print('-1')
    else:
        print(dp[goal[0]][goal[1]])


abc176d_wizard_in_maze()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = read().split()
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1), \
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -1), (2, -2), \
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -1), (-2, -2), \
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        flag = False
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] != '#':
                    if dist[nh][nw] > dist[h][w]:
                        dist[nh][nw] = dist[h][w]
                        Q.append((nh,nw))
                else:
                    flag = True
        if flag:
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh][nw] > dist[h][w] + 1:
                        dist[nh][nw] = dist[h][w] + 1
                        Q.append((nh,nw))

    if dist[gh][gw]==INF:
        print(-1)
    else:
        print(dist[gh][gw])




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
sh,sw = map(int, input().split())
gh,gw = map(int, input().split())
ab = [list(input()) for _ in range(h)]

import math
from collections import deque

for y in range(h):
    for x in range(w):
        if ab[y][x]=='.':
            ab[y][x]=math.inf

ab[sh-1][sw-1]=0
que=deque([[sh-1,sw-1]])
while que:
    y,x=que.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        nexty,nextx=y+i,x+j
        if nexty >= 0 and nexty <h and nextx >= 0 and nextx <w:
            dist=ab[nexty][nextx]
            if dist!='#' :
                if dist>ab[y][x]:
                    ab[nexty][nextx]=ab[y][x]
                    que.append([nexty,nextx])
    for i,j in [(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)]:
        nexty,nextx=y+i,x+j
        if nexty >= 0 and nexty <h and nextx >= 0 and nextx <w:
            dist=ab[nexty][nextx]
            if dist!='#':
                if dist>ab[y][x]+1:
                    ab[nexty][nextx]=ab[y][x]+1
                    que.append([nexty,nextx])

if ab[gh-1][gw-1] ==math.inf:
    print(-1)
else:
    print(ab[gh-1][gw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

h,w=NM()
sh,sw=NM()
sh-=1
sw-=1
gh,gw=NM()
gh-=1
gw-=1
l=[[j for j in input()] for i in range(h)]
from heapq import *
def dijkstra(s,n,g):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d[g]
edge=[[] for i in range(h*w)]

def v(i,j):
    return (j*h+i)
def f(i,j,x,y):
    if x>=h or y>=w or x<0 or y<0:
        return 0
    if l[x][y]==".":
        edge[v(i,j)].append((v(x,y),1))
        edge[v(x,y)].append((v(i,j),1))
        return 1
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            continue
        if i<h-1:
            if l[i+1][j]==".":
                edge[v(i,j)].append((v(i+1,j),0))
                edge[v(i+1,j)].append((v(i,j),0))
            else:
                f(i,j,i+2,j)
                f(i,j,i+1,j+1)
                
                
        if j<w-1:
            if l[i][j+1]==".":
                edge[v(i,j)].append((v(i,j+1),0))
                edge[v(i,j+1)].append((v(i,j),0))
            else:
                f(i,j,i,j+2)
                f(i,j,i-1,j+1)
        
        f(i,j,i+2,j+2)
        f(i,j,i+1,j+2)
        f(i,j,i+2,j+1)

        f(i,j,i-2,j+1)
        f(i,j,i-2,j+2)
        f(i,j,i-1,j+2)


d=dijkstra(v(sh,sw),h*w,v(gh,gw))
if d==float("inf"):
    print(-1)
else:
    print(d)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

import heapq
seen = set()
queue = [(0, CH-1, CW-1)]

while queue:
    move, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.':
            heapq.heappush(queue, (move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.':
                heapq.heappush(queue, (move+1, new_row, new_col))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
    s.extend(input().rstrip('\n'))

d = [10 ** 18 for j in range(h*w)]

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft


while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh * w + nw] == '.':
            stack_append([nh, nw, cnt])
    for nh in range(curh-2, curh+3):
        if nh >= 0 and nh < h:
            for nw in range(curw-2,curw+3):
                if nw >= 0 and nw < w and s[nh * w + nw] == '.':
                     stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == 10 ** 18:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().strip().split())
Ch, Cw = map(int, input().strip().split())
Dh, Dw = map(int, input().strip().split())
Ch += 1
Cw += 1
Dh += 1
Dw += 1

moves=[]
for i in range(H+4):
    moves.append([1000000]*(W+4))

for i in range(2,H+2):
    s = input().strip()
    for j in range(W):
        if s[j] == '#':
            moves[i][j+2] = -1

for i in range(H+4):
    for j in range(W+4):
        if i<=1 or i>=H+2 or j<=1 or j>=W+2:
            moves[i][j]=-1


moves[Ch][Cw]=0
sources_0 = [[-1,0],[1,0],[0,-1],[0,1]]
sources_1 = [[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2]]
sources_1 += [[-2,-1],[-1,-1],[0,-1],[1,-1],[2,-1]]
sources_1 += [[-2,0],[-1,0],[1,0],[2,0]]
sources_1 += [[-2,1],[-1,1],[0,1],[1,1],[2,1]]
sources_1 += [[-2,2],[-1,2],[0,2],[1,2],[2,2]]

n = 0
while (n <= H*W):
    n += 1
    for i in range(2,H+2):
        for j in range(2,W+2):
            if moves[i][j] <= 0:
                continue
            for src in sources_0:
                src_move = moves[i+src[0]][j+src[1]]
                if src_move >= 0 and src_move < moves[i][j]:
                    moves[i][j] = src_move
            for src in sources_1:
                src_move = moves[i+src[0]][j+src[1]]
                if src_move >= 0 and src_move + 1 < moves[i][j]:
                    moves[i][j] = src_move + 1

if moves[Dh][Dw] == 1000000:
    print(-1)
else:
    print(moves[Dh][Dw])