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
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

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

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

inf = 10**10
cost = [[inf] * w for _ in range(h)]
cost[ch][cw]=0
hq = [(0,ch,cw)]

while(hq):
    ci,xi,yi = heappop(hq)
    if(cost[xi][yi] > ci):
        continue

    for dx in range(-2,3):
        xj = xi+dx
        if(xj<0)|(xj>=h):
            continue
        for dy in range(-2,3):
            yj = yi+dy
            # print(xi,yi,xj,yj)
            if(yj<0)|(yj>=w):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                if(cost[xj][yj] > ci):
                    cost[xj][yj] = ci
                    heappush(hq,(ci,xj,yj))
            else:
                if(cost[xj][yj] > ci+1):
                    cost[xj][yj] = ci+1
                    heappush(hq,(ci+1,xj,yj))

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

Submission status: Time Limit Exceeded

Solution code:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
cand=set([])
for i in range(h):
    for j in range(w):
        if grid[i][j]!=0:
            continue
        else:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                    elif 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==-1:
                        cand.add((nowi, nowj))

start=grid[ch][cw]-1
end=grid[dh][dw]-1

if start==end:
    print(0)
    exit()

es=[set([]) for _ in range(col)]
visited=[-1]*col
for i,j in cand:
    now=grid[i][j]
    if now!=-1: 
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x,y) in dif:
                    continue
                if 0<=i+x<h and 0<=j+y<w:
                    nex=grid[i+x][j+y]
                    if nex!=-1 and now!=nex:
                        es[now-1].add(nex-1)
stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    v=visited[now]
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=v+1
            stack.append(e)
#print(grid)
print(visited[end])

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
c_h,c_w = map(int,input().split())
d_h,d_w = map(int,input().split())
s_list = [[c for c in input()] for _ in range(h)]

move_pattern = [[-1,0],[1,0],[0,-1],[0,1]]
around_area = [[i-2,j-2] for i in range(5) for j in range(5)]
kakutei_set = set([(c_h-1,c_w-1)])
temp_dic = {}
temp_dic[0] = set([(c_h-1,c_w-1)])
temp_num = 0
while True:
    cur_list = list(temp_dic[temp_num])
    for i,j in cur_list:
        for x,y in move_pattern:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="#":
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                cur_list.append((i+y,j+x))
                temp_dic[temp_num].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_dic[temp_num+1] = set()
    for i,j in temp_dic[temp_num]:
        for x,y in around_area:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="#":
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                temp_dic[temp_num+1].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_num += 1
    if len(temp_dic[temp_num])==0:
        break
if (d_h-1,d_w-1) not in kakutei_set:
    print(-1)
else:
    for key,value in temp_dic.items():
        if (d_h-1,d_w-1) in value:
            print(key)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

def main():
  walks=[(-1,0),(1,0),(0,-1),(0,1)]
  warps=[(-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)]
  h,w=map(int,input().split())
  ch,cw=map(int,input().split())
  dh,dw=map(int,input().split())

  inf=10*7

  que=[(0,ch,cw)]
  
  maze=[list(input()) for _ in range(h)]
  visited=set()
  while len(que)>0:
    wt,eh,ew=heappop(que)
    #print(que)
    if (eh,ew)==(dh,dw):
      return wt
    if (eh,ew) in visited:
      continue
    visited.add((eh,ew))
    for walkh,walkw in walks:
      th=eh+walkh
      tw=ew+walkw
      if (th,tw)==(dh,dw):
        return wt
      if th<1 or th>h or tw<1 or tw>w:
        continue
      #print(th,tw,eh,ew,wt,maze[th-1][tw-1])
      if maze[th-1][tw-1]=='.':
        heappush(que,(wt,th,tw))
    for warph,warpw in warps:
      th=eh+warph
      tw=ew+warpw
      if th<1 or th>h or tw<1 or tw>w:
        continue
      #print(th,tw,eh,ew,wt,maze[th-1][tw-1],'x')
      if maze[th-1][tw-1]=='.':
        heappush(que,(wt+1,th,tw))
  return -1

print(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,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2)
    dyw = (-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2)

    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
        if visited[ey][ex] == 0:
            cnt += 1
            flg = False
            for i in range(h):
                for j in range(w):
                    if visited[i][j] == 1:
                        for k in range(25):
                            nx = j + dyw[k]
                            ny = i + dxw[k]
                            if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                                flg = True
                                que.append((nx,ny))
            if flg == False:
                print(-1)
                exit()

        else:
            print(cnt)
            exit()

if __name__=="__main__":
    main()

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 = [start]

    while len(q) != 0:
        v = q.pop()
        x, y = v[0], v[1]
        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([x + dx, y + dy])

        for dx in [-2, 1, 0, 1, 2]:
            for dy in [-2, 1, 0, 1, 2]:
                if 0 <= x + dx < h and 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([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:
from collections import deque

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]
    
    dp[ch-1][cw-1] = 0
    
    q = deque([[0, ch-1, cw-1]])
    
    while q:
        cost, px, py = q.pop()
        for xi, yj in zip(dx, dy):
            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
                q.appendleft([cost, x, y])
        cost += 1
        for di in range(-2, 3):
            x = px + di
            if x >= h or x < 0:
                continue
            sx = s[x]
            dpx = dp[x]
            for dj in range(-2, 3):
                y = py + dj
                if y >= w or y < 0 or sx[y] == "#":
                    continue
                if dpx[y] > cost:
                    dpx[y] = cost
                    q.appendleft([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 sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R,C = NMI()
    sy, sx = NMI()
    gy, gx = NMI()
    board = [list(input()) for _ in range(R)]

    #座標を0始まりにする
    sx -= 1
    sy -= 1
    gx -= 1
    gy -= 1

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

    #すべての点をINFで初期化
    INF = 10**7
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成、スタート地点を入れる
    que = deque([])
    que.append((sy,sx))

    #スタート地点の距離は0
    distance[sy][sx] = 0
    
    #テレポート移動のベクトル
    tx = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
    ty = [-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1, 0, 1, 2]
    
    #テレポート手前の地点を保存するqueを作成
    teleque = deque([])
    

    while len(que) != 0 or len(teleque) != 0:
        

        #queが空になるまでループ
        while len(que) != 0:

            #取り出してきた状態がゴールなら探索をやめる
            pop = que.popleft()
            if pop[0]==gy and pop[1]==gx:
                print(distance[gy][gx])
                sys.exit()

            #移動4方向をループ
            for i in range(len(dx)):
                #移動した後の点をny,nxとする
                ny = pop[0]+dy[i]
                nx = pop[1]+dx[i]


                #nyが0以上R未満   nxが0以上C未満     まだ訪れたことがない
                if 0<= ny < R and 0 <= nx < C and distance[ny][nx] == INF:

                    if board[ny][nx]!='#':
                        #つまり壁ではなく移動可能でまだ行ったことがなければqueの左へ入れる
                        que.appendleft((ny,nx))
                        distance[ny][nx] = distance[pop[0]][pop[1]]


                    else:
                        teleque.append((pop[0],pop[1]))
                        #つまり壁だった場合、壁をテレポートでよけて進めるかどうか。進めれて、まだ行ったことがなければqueの右へ入れる

        while len(teleque) != 0:
            telepop = teleque.popleft()
            if telepop[0]==gy and telepop[1]==gx:
                print(distance[gy][gx]+1)
                sys.exit()


                #テレポートのループ
            for j in range(len(tx)):
                teley = telepop[0]+ty[j]
                telex = telepop[1]+tx[j]
                #print(teley,telex)
                #nyが0以上R未満   nxが0以上C未満     まだ訪れたことがない
                if 0<= teley < R and 0 <= telex < C and distance[teley][telex] == INF:
                    if board[teley][telex]!='#': #テレポート先が壁でないならqueの右へ入れる
                        que.append((teley,telex))
                        distance[teley][telex] = distance[pop[0]][pop[1]]+1 #テレポート使用回数を1回加算

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        # print(warp)
        d = deque()
        self.set(start[1], start[0], 0)
        d.append((0, cx, cy))
        while d:
            cc, cx, cy = d.popleft()
            if self.get(cx, cy) < cc:
                continue
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    d.append((cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    d.append((cc + 1, nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return





def solve():
    h, w = getList()
    start = getList()
    goal = getList()
    G = TwoDimGrid(h, w)
    G.search(start, goal)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

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()) #ゴール
#Ch-=1; Cw-=1; Dh-=1; Dw-=1
S=[]
S.append('#'*(W+2))
for i in range(H):
    S.append('#'+input()+'#')
S.append('#'*(W+2))

H+=2; W+=2
ans=0


done=[[0 for i in range(W)] for j in range(H)]
kin4=([1,0],[-1,0],[0,1],[0,-1])
kin8=([1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1])
MAP=S

def dfs(y,x,n):
    if MAP[y][x]=='#' or done[y][x]:
        return
    else:
        done[y][x]=n
        for i,j in kin4:
            if not(y+i<0 or y+i>H-1 or x+j<0 or x+j>W-1):
                dfs(y+i,x+j,n)

def search(M,D):
    b,a=-1,-1
    for i in range(H):
        for j in range(W):
            if D[i][j]==False and M[i][j]=='.':
                b,a=i,j
                return [b,a]
    return [b,a]


cnt=1
while True:
    #print(cnt)
    s=search(MAP,done)
    Y,X=s[0],s[1]
    #print(s)
    if Y==-1 and X==-1:
        break
    dfs(Y,X,cnt)
    #print(done)
    cnt+=1

#print(done)

N=cnt-1

graph=[[0 for i in range(N+1)] for j in range(N+1)]

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

for i in range(H):
    for j in range(W):
        c=done[i][j]
        if c==0:
            continue
        for h in range(25):
            if 0<=i+dx[h]<H and 0<=j+dy[h]<W:
                c2=done[i+dx[h]][j+dy[h]]
                if c!=c2 and c2!=0:
                    graph[c][c2]=1
                    graph[c2][c]=1

#print(graph)       

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n
    used=[False]*n
    d[s]=0
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1):
               v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
               break
        used[v]=True
               
        for j in range(n):
               d[j]=min(d[j],d[v]+cost[v][j])
    return d

cost = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
w=0
for i in range(N+1):
    for j in range(N+1):
        if graph[i][j]:
            cost[i][j]=1
            w+=1
start=done[Ch][Cw]
goal=done[Dh][Dw]

ds=dijkstra(start,N+1,w,cost)
#print(ds)
#print(ds[goal])

if ds[goal]>10000:
    print(-1)
else:
    print(ds[goal])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
C_L = [int(_)-1 for _ in input().split()]
D_L = [int(_)-1 for _ in input().split()]
S_L = [[x for x in input()] for y in range(H)]


ans = 0
c_l = [[float("Inf")] * W for _ in range(H)]


def dfs(x, y, c):
    if not(0 <= x < W) or not(0 <= y < H) or S_L[y][x] == "#":
        return
    if c_l[y][x] > c:
        c_l[y][x] = c

        # no magic
        dfs(x+1, y, c)
        dfs(x-1, y, c)
        dfs(x, y+1, c)
        dfs(x, y-1, c)

        # use magic
        for _x in range(-2, 3):
            for _y in range(-2, 3):
                if (_x == -1 and _y == 0) or (_x == 1 and _y == 0) or (_x == 0 and _y == -1)or (_x == 0 and _y == 1) or (_x == 0 and _y == 0):
                    continue
                dfs(x+_x, y+_y, c+1)


dfs(C_L[1], C_L[0], 0)

if c_l[D_L[0]][D_L[1]] == float("Inf"):
    print("-1")
else:
    print(c_l[D_L[0]][D_L[1]])

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
import heapq

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**20

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

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

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

mx = []
my = []

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

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

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]

    se = set()

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

    que += se

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0
#niko(x,y,ans[y][x]+1)とする。
def niko(x,y,k,ans):
  for i in range(x-2,x+2):
    for j in range(y-2,y+2):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>k or ans[j][i]==-1):
          ans[j][i]=k
  return ans
ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

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,0]]
while len(pos)>0:
  x, y, depth, 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,depth+1,hop])
    flag = 1
  if maze[x+1][y] <2:
    pos.append([x+1,y,depth+1,hop])
    flag = 1
  if maze[x][y-1] <2:
    pos.append([x,y-1,depth+1,hop])
    flag = 1
  if maze[x][y+1] <2:
    pos.append([x,y+1,depth+1,hop])
    flag = 1
    
  if flag == 0:
    try:
      if maze[x-2][y] <2:
        flag =1
        pos.append([x-2,y,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y+1] <2:
        flag =1
        pos.append([x-2,y+1,depth+1,hop+1])
    except:
      pass
        
    try: 
      if maze[x-2][y+2] <2:
        flag =1
        pos.append([x-2,y+2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-1] <2:
        flag =1
        pos.append([x-2,y-1,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-2] <2:
        flag =1
        pos.append([x-2,y-2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y] <2:
        flag =1
        pos.append([x+2,y,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-1] <2:
        flag=1
        pos.append([x+2,y-1,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-2] <2:
        flag=1
        pos.append([x+2,y-2,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y+1] <2:
        flag=1
        pos.append([x+2,y+1,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y+2] <2:
        flag=1
        pos.append([x+2,y+2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x][y-2] <2:
        flag=1
        pos.append([x,y-2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y-2] <2:
        flag=1
        pos.append([x+1,y-2,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x-1][y-2] <2:
        flag=1
        pos.append([x-1,y-2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x][y+2] <2:
        flag=1
        pos.append([x,y+2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y+2] <2:
        flag=1
        pos.append([x+1,y+2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y+2] <2:
        flag=1
        pos.append([x-1,y+2,depth+1,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y-1] <2:
        flag=1
        pos.append([x-1,y-1,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x-1][y+1] <2:
        flag=1
        pos.append([x-1,y+1,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x+1][y-1] <2:
        flag=1
        pos.append([x+1,y-1,depth+1,hop+1])
    except:
      pass
    try:
      if maze[x+1][y+1] <2:
        flag=1
        pos.append([x+1,y+1,depth+1,hop+1])
    except:
      pass
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic1 = [[1, 1], [1, -1], [2, 2], [2, 1], [2, 0], [2, -1], [2, -1]]
magic2 = [[-1, 1], [-1, -1], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -1]]
magic3 = [[1, 1], [-1, 1], [2, 2], [1, 2], [0, 2], [-1, 2], [-2, 2]]
magic4 = [[1, -1], [-1, -1], [2, -2], [1, -2], [0, -2], [-1, -2], [-2, -2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    if check[pos[0]][pos[1]] < dd:
        continue
    flg = [False, False, False, False]
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            if dy == 1:
                flg[0] = True
            elif dy == -1:
                flg[1] = True
            elif dx == 1:
                flg[2] = True
            else:
                flg[3] = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg[0]:
        for dy, dx in magic1:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[1]:
        for dy, dx in magic2:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[2]:
        for dy, dx in magic3:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[3]:
        for dy, dx in magic4:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

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