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:
def main():
    import heapq


    def ok(i, j):
        return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

    H, W = map(int, input().split())
    C_h, C_w = map(int, input().split())
    C_h -= 1
    C_w -= 1
    D_h, D_w = map(int, input().split())
    D_h -= 1
    D_w -= 1
    S = [[None] * W for _ in range(H)]
    for i in range(H):
        for j, c in enumerate(input()):
            S[i][j] = c


    queue = [(0, (C_h, C_w))]
    dist = {(C_h, C_w): 0}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                heapq.heappush(queue, (score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                heapq.heappush(queue, (score, (i, j_next)))
                dist[i, j_next] = score

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if not ok(i_jump, j_jump):
                    continue
                if ((i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1):
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    dist[i_jump, j_jump] = score + 1
    else:
        print(-1)


main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import deque
import sys

H, W = (int(x) for x in input().split()) 
CH, CW = (int(x)-1 for x in input().split()) 
DH, DW = (int(x)-1 for x in input().split()) 

MAZE = []

for i in range(H):
    MAZE.append([-1 if x == '#' else -2  for x in input()])

que = deque()
que.append((CH, CW, 0))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

while len(que):
    cur_h, cur_w, cost = que[0]
    que.popleft()
    if MAZE[cur_h][cur_w] == -1:
        continue

    MAZE[cur_h][cur_w] = cost

    for h, w in can_walk:
        next_h = cur_h + h 
        next_w = cur_w + w 
        if next_h < 0 or next_w < 0 or next_h >= H or next_w >= W:
            continue
        if MAZE[next_h][next_w] <= cost and MAZE[next_h][next_w] != -2:
            continue
        que.append((next_h, next_w, cost))

    for h in (-2, -1, 0, 1, 2):
        for w in (-2, -1, 0, 1, 2):
            if (h, w) in can_walk :
                continue 

            next_h = cur_h + h 
            next_w = cur_w + w 
            if next_h < 0 or next_w < 0 or next_h >= H or next_w >= W:
                continue
            if MAZE[next_h][next_w] <= cost + 1 and MAZE[next_h][next_w] != -2:
                continue
            que.append((next_h, next_w, cost+1))

#for i in range(H):
#    print (MAZE[i])
ret = MAZE[DH][DW]
if ret < 0:
    print(-1)
else:
    print(ret)

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots():全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    ################


    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    for i in range(H):
        s=["#"]*2 + list(input()) + ["#"]*2
        S.append(s)
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,  -1,-1,-1,-1,   0,0,   1, 1,1,1,   2, 2,2,2,2]
    dy2=[-2,-1, 0, 1, 2,  -2,-1, 1, 2,  -2,2,  -2,-1,1,2,  -2,-1,0,1,2]
    
    uf=UnionFind((W+4)*(H+4))
    djk=Dijkstra((W+4)*(H+4))
    
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j]==".":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]==".":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        uf.union(fro,to)
                        djk.add(fro,to,0)
    
    roots=[[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if S[i][j]==".":
                now=i*(W+4)+j
                root=uf.find(now)
                roots[i][j]=root
                
                
    for i in range(2,H+2):
        for j in range(2,W+2):
            if S[i][j]==".":
                for k in range(20):
                    ii=i+dx2[k]
                    jj=j+dy2[k]
                    if S[ii][jj]==".":
                        if roots[i][j]!=roots[ii][jj]:
                            fro=i*(W+4)+j
                            to=ii*(W+4)+jj
                            djk.add(fro,to,1)
                            
    
    s=ch*(W+4)+cw
    g=dh*(W+4)+dw
    D=djk.shortest_path(s)
    ans=D[g]
    if ans>=10**6+5:
        ans=-1
    print(ans)                
    
    
                

main()

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


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 S[i][j] == ".":
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and S[dx+i][dy+j] == ".":
                    G[trans(i, j)].append((trans(dx+i, dy+j), 0))
                    G[trans(dx+i, dy+j)].append((trans(i, j), 0))
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if dx != 0 or dy != 0:
                        if S[i][j] == "." and 0 <= dx+i < H and 0 <= dy+j < W and S[dx+i][dy+j] == ".":
                            G[trans(i, j)].append((trans(dx+i, dy+j), 1))
                            G[trans(dx+i, dy+j)].append((trans(i, j), 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:
import sys
input = sys.stdin.readline

h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))

s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1

Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1

for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)

count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))

      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))

      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))

      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))

    Q = new_Q

  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
            part.append((x,y))         	
       
    ALL = list(set(part))
    Q = list(ALL)

    if (f1,f2) in ALL:
      print(count)
      break

    if len(ALL)==0:
      print(-1)
      break

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=[]

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)
while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=start[0][0]+hh
                    nny=start[0][1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
            del(start[0])
        ans+=1
    if len(start)==0:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy 
import sys
sys.setrecursionlimit(10**6+10)

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

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

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

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

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


i,j=ch,cw
cu=[[i,j]]
t[i][j]=0
next=[]
d=0
while len(cu)!=0:
    while len(cu)!=0:
        i,j=cu.pop()
        for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and (t[i+k][j+l]==INF or t[i+k][j+l]==d+1):
                t[i+k][j+l]=d
                cu.append([i+k,j+l])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]==INF:
                    t[i+k][j+l]=d+1
                    next.append([i+k,j+l])
                    # print(i+k,j+l)
    
    # print(next)
    cu=next
    next=[]
    d+=1
    # print(d)
if t[dh][dw]==INF:
    t[dh][dw]=-1

print(t[dh][dw])

# print(t)

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())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue = deque([[ch-1, cw-1]])
while queue:  
  x,y=queue.popleft()
  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]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=temp[x][y]:
      continue
    if (i==1 and j==0) or (i==-1 and j==0) or (i==0 and j==1) or (i==0 and j==-1):
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y])
    else:
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y]+1)
    if [xtemp,ytemp] not in queue:
      queue.append([xtemp,ytemp])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd,deque as dq
import sys
inf=10000000000
input=sys.stdin.readline
n,m=map(int,input().split())
cx,cy=map(int,input().split())
cx-=1
cy-=1
dx,dy=map(int,input().split())
dx-=1
dy-=1
ll=[]
for i in range(n):
    ll.append(input().split()[0])
q=dq([cx*m+cy])
dis=[inf]*(n*m+1)
xx=[0,-1,0,1]
yy=[1,0,-1,0]
des=dx*m+dy
d=dd(list)
for x in range(n):
    for y in range(m):
        for i in range(4):
            X=x+xx[i]
            Y=y+yy[i]
            if(X<n and X>=0 and Y<m and Y>=0 and ll[X][Y]=='.'):
                d[x*m+y].append((X*m+Y,0))
        X=x-2
        Y=y-2
        for i in range(5):
            for j in range(5):
                if(X+i>=0 and X+i<n and Y+j>=0 and Y+j<m and ll[X+i][Y+j]=='.'):
                    d[x*m+y].append(((X+i)*m+Y+j,1))
dis[q[0]]=0
lol=0
while q:
    curr=q.pop()
    #print(curr)
    if(curr==des):
        print(dis[curr])
        lol=1
        break
    for j in d[curr]:
        temp,val=j
        if(dis[temp]>dis[curr]+val):
            dis[temp]=dis[curr]+val
            if(val==0):
                q.append(temp)
            else:
                q.appendleft(temp)
if(lol==0):
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = [(0, 0, Si-1, Sj-1)]
heapify(que)
visited = set()

while que:
    count, priority, r, c = heappop(que)
    if not(0 <= r < H and 0 <= c < W):
        continue
    if (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        heappush(que, (count, priority+1, r+td, c+lr))
    for ud in range(-2, 3):
        for lr in range(-2, 3):
            heappush(que, (count+1, priority+1, r+ud, c+lr))
print('-1')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rxy = ((-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)) 
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
                continue
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        cost += 1
        for di, dj in rxy:
            x = px + di
            y = py + dj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        # for di in rx:
        #     x = px + di
        #     if x >= h or x < 0:
        #         continue
        #     sx = s[x]
        #     dpx = dp[x]
        #     for dj in ry:
        #         y = py + dj
        #         if y >= w or y < 0 or sx[y] == "#":
        #             continue
        #         if dpx[y] > cost:
        #             dpx[y] = cost
        #             heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    h,w = map(int, input().split())
    start = list(map(int, input().split()))
    qy, qx = start[0]-1,start[1]-1
    end = list(map(int, input().split()))
    ey, ex = end[0]-1, end[1]-1

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

    visited = [[0]*w for i in range(h)]
    dist = [[INF]*w for i in range(h)]

    que = deque([(qx,qy)])
    visited[qy][qx] = 1

    dx = (1, -1, 0, 0)
    dy = (0, 0, 1, -1)
    cnt = 0

    dxw = (-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,0,1,1,1,1,2,2,2,2,2)
    dyw = (-2,-1,0,1,2,-2,-1,1,2,-2,0,2,-2,-1,1,2,-2,-1,0,1,2)

    test = []

    while True:
        while len(que) > 0:
            x,y = que.popleft()
            visited[y][x] = 1
            if x==ex  and y== ey: # ゴールまで辿ったら
                break

            for k in range(4): # 上下左右4パターンの移動方法
                nx = x + dx[k]
                ny = y + dy[k]

                if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                    que.append((nx,ny))
                    visited[ny][nx] = 1
            for v in range(21):
                nx = x + dyw[v]
                ny = y + dxw[v]
                if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                    test.append((nx,ny))
        if visited[ey][ex] == 0:
            cnt += 1
            if len(test) > 0:
                for e in test:
                    que.append(e)
            else:
                print(-1)
                exit()

        else:
            print(cnt)
            exit()

if __name__=="__main__":
    main()

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())
maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

pos = [[ch,cw,0]]
while len(pos)>0:
  x, y, hop = pos.pop(0)
  #print(x,y,hop)
  if (x,y) == (dh,dw):
    print(hop)
    break
    
  maze[x][y] = 2
  
  flag = 0
  if maze[x-1][y] <2:
    pos.append([x-1,y,hop])
    flag = 1
  if maze[x+1][y] <2:
    pos.append([x+1,y,hop])
    flag = 1
  if maze[x][y-1] <2:
    pos.append([x,y-1,hop])
    flag = 1
  if maze[x][y+1] <2:
    pos.append([x,y+1,hop])
    flag = 1
    
  if flag == 0:
    try:
      if maze[x-2][y] <2:
        pos.append([x-2,y,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y+1] <2:
        pos.append([x-2,y+1,hop+1])
    except:
      pass
        
    try: 
      if maze[x-2][y+2] <2:
        pos.append([x-2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-1] <2:
        pos.append([x-2,y-1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-2] <2:
        pos.append([x-2,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y] <2:
        pos.append([x+2,y,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-1] <2:
        pos.append([x+2,y-1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-2] <2:
        pos.append([x+2,y-2,hop+1])
    except:
      pass
    try:
      if maze[x+2][y+1] <2:
        pos.append([x+2,y+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y+2] <2:
        pos.append([x+2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y-2] <2:
        pos.append([x,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y-2] <2:
        pos.append([x+1,y-2,hop+1])
    except:
      pass
    try:
      if maze[x-1][y-2] <2:
        pos.append([x-1,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y+2] <2:
        pos.append([x,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y+2] <2:
        pos.append([x+1,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y+2] <2:
        pos.append([x-1,y+2,hop+1])
    except:
      pass
    if maze[x-1][y-1] <2:
      pos.append([x-1,y-1,hop+1])
    if maze[x-1][y+1] <2:
      flag=1
      pos.append([x-1,y+1,hop+1])
    if maze[x+1][y-1] <2:
      flag=1
      pos.append([x+1,y-1,hop+1])
    if maze[x+1][y+1] <2:
      flag=1
      pos.append([x+1,y+1,hop+1])
    
else:
  print(-1)

Submission status: Time Limit Exceeded

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

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
import sys


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


def main():
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[float("inf")] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    stack = []
    warp_count[c_h][c_w] = 0
    stack.append((c_h, c_w, 0))

    while stack:
        _h, _w, warp = stack.pop()
        warp_count[_h][_w] = warp

        cnt = 0
        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                cnt += 1
                stack.append((_h + _a, _w + _b, warp))

        if cnt == 4:  # 4方向行けるときにワープは不要
            continue

        # warp
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x, y) in directions:
                    continue
                elif x == 0 and y == 0:
                    continue
                elif _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                    continue
                elif grid[_h + x][_w + y] == "#":
                    continue
                if warp_count[_h + x][_w + y] > warp + 1:
                    stack.append((_h + x, _w + y, warp + 1))

    if warp_count[d_h][d_w] == float("inf"):
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()

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

from collections import deque
#import sys
#sys.setrecursionlimit(10**7)

dist = [[100000000 for i in range(W)] for j in range(H)]
dist[Ch-1][Cw-1] = 0

que = deque()
que.append((Ch-1, Cw-1))

walk = [(-1,0), (1,0), (0,-1), (0,1)]
warp = []
for i in range(-2,3):
    for j in range(-2,3):
        if (i,j) in walk: continue
        warp.append((i,j))

while que:
    vh, vw = que.popleft()
    for step in walk:
        vh_next = vh+step[0]
        vw_next = vw+step[1]
        if 0 <= vh_next < H and 0 <= vw_next < W:
            if S[vh_next][vw_next] == '.' and dist[vh_next][vw_next] > dist[vh][vw]:
                dist[vh_next][vw_next] = dist[vh][vw]
                que.append((vh_next, vw_next))
    for warp_step in warp:
        vh_warp = vh+warp_step[0]
        vw_warp = vw+warp_step[1]
        if 0 <= vh_warp <H and 0 <= vw_warp < W and S[vh_warp][vw_warp] == '.' and dist[vh_warp][vw_warp] > dist[vh][vw]+1:
            dist[vh_warp][vw_warp] = dist[vh][vw]+1
            que.append((vh_warp, vw_warp))

#for d in dist:
#    print(d)

if dist[Dh-1][Dw-1] < 100000000:
    print(dist[Dh-1][Dw-1])
else:
    print(-1)