Problem:


Score : 600 points

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2).
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
C = [None for i in range(H)]
for i in range(H):
    C[i] = input()
B = [[10**6 for i in range(W)] for j in range(H)]
B[x1-1][y1-1] = 0
A = [[x1-1,y1-1]]
while(A):
    a,b = A.pop(0)
    for i in range(a,min(a+1+K,H)):
        if C[i][b] == "@":
            break
        else:
            if B[i][b] > B[a][b]:
                B[i][b] = B[a][b] + 1
                A.append([i,b])
    for i in range(a,max(a-1-K,-1),-1):
        if C[i][b] == "@":
            break
        else:
            if B[i][b] > B[a][b]:
                B[i][b] = B[a][b] + 1
                A.append([i,b])
    for j in range(b,min(b+1+K,W)):
        if C[a][j] == "@":
            break
        else:
            if B[a][j] > B[a][b]:
                B[a][j] = B[a][b] + 1
                A.append([a,j])
    for j in range(b,max(b-1-K,-1),-1):
        if C[a][j] == "@":
            break
        else:
            if B[a][j] > B[a][b]:
                B[a][j] = B[a][b] + 1
                A.append([a,j])
if B[x2-1][y2-1] == 10**6:
    print(-1)
else:
    print(B[x2-1][y2-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          for l in range(1, K + 1):
            if p == 0:
              new_y, new_x = y + j * l, x + k * l #改行して条件文を続けるときにバックスラッシュ
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
              else:
                p = 1

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
r, c, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
C = [input() for _ in range(r)]

from collections import deque

q = deque()
D = [[0]*c for _ in range(r)]
ans = []
q.append((sx-1, sy-1))
D[sx-1][sy-1] = 1

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

# print(C)
# print(D)
while q:
    x, y = q.popleft()
    for dx, dy in dxy:
        for i in range(1, k+1):
            _x, _y = x + dx*i, y + dy*i
            # print(i, _x, _y)
            if 0<=_x<r and 0<=_y<c and D[_x][_y] in [0, D[x][y] + 1] and C[_x][_y] == '.':
                D[_x][_y] = D[x][y] + 1
                q.append((_x, _y))
                # print(_x, _y, D)
            else:
                break
# print(C)
# print(D)
print(D[gx-1][gy-1]-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,k=list(map(int,input().split()))
sx,sy,ex,ey=list(map(int,input().split()))
sx,sy,ex,ey=sx-1,sy-1,ex-1,ey-1
c=[]
for i in range(h):
  cc=[]
  for j in input():
    if j==".":
      cc.append(0)
    else:
      cc.append(1)
  c.append(cc)


l=[]
for i in range(h):
  l.append([0 for j in range(w)])

l[sx][sy]=1
def chp(x,y):
  if (x<0)or(x>=h)or(y<0)or(y>=w):
    return True
  else:
    return False

nc=[[sx,sy]]
dat=[[1,0],[-1,0],[0,1],[0,-1]]
f=0
cnt=0
while True:
  if len(nc)==0:
    break
  cnt+=1
  nnc=[]
  for i in nc:
    for j in dat:
      for g in range(1,k+1):
        cx,cy=i[0]+g*j[0],i[1]+g*j[1]
        if chp(cx,cy) or c[cx][cy]:
          break
        if l[cx][cy]==0:
          nnc.append([cx,cy])
          if cx==ex and cy==ey:
            f=1
            print(cnt)
            break
          l[cx][cy]=1
      if f:
        break
    if f:
      break
  if f:
    break
  nc=nnc
if f==0:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    l = []
    v = [[0] * W for _ in range(H)]
    v[x1-1][y1-1] = 1
    for _ in range(H):
        c = input()
        l.append(c)
    cur = [(x1-1, y1-1)]
    r = 0
    while cur:
        r += 1
        nex = []
        for x, y in cur:
            # north
            i = 1
            while x-i > -1 and i <= K:
                a, b = x-i, y
                if a == x2-1 and b == y2-1:
                    return r
                if l[x-i][y] == '.' and v[x-i][y] == 0:
                    v[x-i][y] = 1
                    nex.append((x-i, y))
                if l[x-i][y] == '@':
                    break
                i += 1
            # south
            i = 1
            while x+i < H and i <= K:
                a, b = x+i, y
                if a == x2-1 and b == y2-1:
                    return r
                if l[x+i][y] == '.' and v[x+i][y] == 0:
                    v[x+i][y] = 1
                    nex.append((x+i, y))
                if l[x+i][y] == '@':
                    break
                i += 1
            # west
            i = 1
            while y-i > -1 and i <= K:
                a, b = x, y-i
                if a == x2-1 and b == y2-1:
                    return r
                if l[x][y-i] == '.' and v[x][y-i] == 0:
                    v[x][y-i] = 1
                    nex.append((x, y-i))
                if l[x][y-i] == '@':
                    break
                i += 1
            # south
            i = 1
            while y+i < W and i <= K:
                a, b = x, y+i
                if a == x2-1 and b == y2-1:
                    return r
                if l[x][y+i] == '.' and v[x][y+i] == 0:
                    v[x][y+i] = 1
                    nex.append((x, y+i))
                if l[x][y+i] == '@':
                    break
                i += 1
        cur = nex
        if not cur:
            return -1
    return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          for l in range(1, K + 1):
            if p == 0:
              new_y, new_x = y + j * l, x + k * l #改行して条件文を続けるときにバックスラッシュ
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                else:
                  if visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])#新しい点を足す。


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = [input() for _ in range(h)]
x1,y1 = y1-1,x1-1
x2,y2 = y2-1,x2-1


q = deque([(x1,y1,0)])
dist = [[-1]*w for _ in range(h)]
while q:
    x,y,d = q.popleft()
    dist[y][x] = d
    if y == y2 and x == x2: break
    for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        newx = x+dx
        newy = y+dy
        count = 1
        while 0<=newx<w and 0<=newy<h and count<=k and c[newy][newx]==".":
            if dist[newy][newx] == -1:
                q.append((newx,newy,d+1))
            newx += dx
            newy += dy
            count += 1

print(dist[y2][x2])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import namedtuple, deque
Edge = namedtuple('Edge', 'to cost')
State = namedtuple('State', 'cost node')
Node = namedtuple('Node', 'x y d k')
D = tuple(zip((1, 0, -1, 0), (0, 1, 0, -1)))

def solve(H, W, K, sx, sy, ex, ey, C):
    #sx, sy, ex, ey = sx-1, sy-1, ex-1, ey-1
    # print(*C,sep="\n")
    q = deque([State(0, Node(sx, sy, -1, 0))])
    visited = set()
    while q:
        s = q.popleft()
        # print(s)
        node = s.node
        if node in visited:
            continue
        if node.x == ex and node.y == ey:
            return s.cost
        visited.add(node)
        for d, (dx, dy) in enumerate(D):
            next_node = Node(node.x+dx, node.y+dy, d,
                             1 if d != node.d else node.k % K + 1)
            if next_node in visited:
                continue
            if C[next_node.x][next_node.y] == "@":
                continue
            if d == node.d:
                if next_node.k != 1:
                    q.appendleft(State(s.cost, next_node))
                else:
                    q.append(State(s.cost+1, next_node))
            else:
                q.append(State(s.cost+1, next_node))
    return -1

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W, K = map(int, input().split())
    sx, sy, ex, ey = map(int, input().split())
    C = ["@" * (W+2)]
    C.extend(["@" + input() + "@" for _ in range(H)])
    C.append("@" * (W+2))
    print(solve(H, W, K, sx, sy, ex, ey, C))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

G = [['#'] * (W + 2)]
for _ in range(H):
    tmp = ['#'] + list(input()) + ['#']
    G.append(tmp)

G.append(['#'] * (W + 2))
INF = 10 ** 6+ 10
dp = [[INF] * (W + 2) for _ in range(H + 2)]

que = deque()
que_append = que.append
que_popleft = que.popleft

que_append((x1, y1))
dp[x1][y1] = 0
while que:
    xy = que_popleft()
    x = xy[0]
    y = xy[1]
    tmp = dp[x][y] + 1

    for k in range(1, K + 1):
        if G[x + k][y] == '.':
            if dp[x + k][y] > tmp:
                dp[x + k][y] = tmp
                que_append((x + k, y))
        else:
            break

    for k in range(1, K + 1):
        if G[x - k][y] == '.':
            if dp[x - k][y] > tmp:
                dp[x - k][y] = tmp
                que_append((x - k, y))
        else:
            break

    for k in range(1, K + 1):
        if G[x][y + k] == '.':
            if dp[x][y + k] > tmp:
                dp[x][y + k] = tmp
                que_append((x, y + k))
        else:
            break

    for k in range(1, K + 1):
        if G[x][y - k] == '.':
            if dp[x][y - k] > tmp:
                dp[x][y - k] = tmp
                que_append((x, y - k))
        else:
            break

if dp[x2][y2] != INF:
    print (dp[x2][y2])
else:
    print (-1)

# for tmp in dp:
#     print (tmp)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    A = LI()
    C = set()
    n = 10**6+1
    D = [False]*n
    ans = 0
    for a in A:
        if a in D:
            D[a] = False
            continue
        D[a] = True
        C.add(a)

    for a in C:
        for i in range(2,1+n//a):
            D[i*a] = False
    ans = sum(D)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue = deque()
            queue.append(s)
            distance[s[0]][s[1]] = 0
            while len(queue):
                y, x = queue.popleft()
                for i in range(4):
                    for k in range(1,K+1):
                        nx, ny = x + k*[1, 0, -1, 0][i], y + k*[0, 1, 0, -1][i]
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    #print(L)
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w, k = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())
x1 -= 1
x2 -= 1
y1 -= 1
y2 -= 1

c = []
for _ in range(h):
    c.append(list(input()))
check = [[False for _ in range(w)] for _ in range(h)]
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

queue = deque()
queue.append((x1, y1))
queue.append(0)
while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    ans += 1
    for dx, dy in directions:
        for i in range(1, k + 1):
            next_x = pos[0] + dx * i
            next_y = pos[1] + dy * i
            if next_x == -1 or next_x == w or next_y == -1 or next_y == h:
                break
            if check[next_y][next_x]:
                continue
            if c[next_y][next_x] == "@":
                break
            check[next_y][next_x] = True
            if next_y == y2 and next_x == x2:
                print(ans)
                exit()
            queue.append((next_x, next_y))
            queue.append(ans)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth,stw,glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(init):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        for d in direc:
            for sk in range(1,K+1):
                hs, ws = h + d[0]*sk, w + d[1]*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                    next_q.append([hs,ws])
                    Dist[hs][ws] = Dist[h][w] + 1
    return Dist

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q)
    print(ret[glh][glw])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W,K=map(int,input().split())
x,y,u,v=map(int,input().split())
C=[[]]
for _ in range(H):
    C.append("*"+input())

Q=deque([(x,y)])
S=set((x,y))
D={(x,y):0}

while Q:
    (p,q)=Q.popleft()

    N=[]
    for m in range(1,K+1):
        X=p-m
        if 1<=X<=H:
            if (C[X][q]=="."):
                if (X,q) not in S:
                    N.append((X,q))
                    S.add((X,q))
            else:
                break
        else:
            break

    for m in range(1,K+1):
        X=p+m
        if 1<=X<=H:
            if (C[X][q]=="."):
                if (X,q) not in S:
                    N.append((X,q))
                    S.add((X,q))
            else:
                break
        else:
            break

    for m in range(1,K+1):
        Y=q-m
        if 1<=Y<=W:
            if (C[p][Y]=="."):
                if (p,Y) not in S:
                    N.append((p,Y))
                    S.add((p,Y))
            else:
                break
        else:
            break

    for m in range(1,K+1):
        Y=q+m
        if 1<=Y<=W:
            if (C[p][Y]=="."):
                if (p,Y) not in S:
                    N.append((p,Y))
                    S.add((p,Y))
            else:
                break
        else:
            break

    d=D[(p,q)]
    for (s,t) in N:
        Q.append((s,t))
        D[(s,t)]=d+1

    if (u,v) in D:
        print(D[(u,v)])
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import queue

INF = 10 ** 9

H, W, K = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())

sentinels = [-1] * (W+2)
MAP = [sentinels]
for _ in range(H):
    MAP.append( [-1] + list(map(lambda c: INF if c == '.' else -1, input())) + [-1] )
MAP.append(sentinels)

q = queue.Queue()
q.put((sx, sy))
MAP[sx][sy] = 0
while not q.empty():
    x, y = q.get()
    for d in range(1, K+1):
        if MAP[x+d][y] > MAP[x][y] + 1:
            MAP[x+d][y] = MAP[x][y] + 1
            q.put((x+d, y))
        elif MAP[x+d][y] < MAP[x][y] + 1:
            break
    for d in range(1, K+1):
        if MAP[x-d][y] > MAP[x][y] + 1:
            MAP[x-d][y] = MAP[x][y] + 1
            q.put((x-d, y))
        elif MAP[x-d][y] < MAP[x][y] + 1:
            break
    for d in range(1, K+1):
        if MAP[x][y+d] > MAP[x][y] + 1:
            MAP[x][y+d] = MAP[x][y] + 1
            q.put((x, y+d))
        elif MAP[x][y+d] < MAP[x][y] + 1:
            break
    for d in range(1, K+1):
        if MAP[x][y-d] > MAP[x][y] + 1:
            MAP[x][y-d] = MAP[x][y] + 1
            q.put((x, y-d))
        elif MAP[x][y-d] < MAP[x][y] + 1:
            break

if MAP[gx][gy] == INF:
    print(-1)
else:
    print(MAP[gx][gy])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth,stw,glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(init):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        for d in direc:
            for sk in range(1,K+1):
                hs, ws = h + d[0]*sk, w + d[1]*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                    next_q.append([hs,ws])
                    Dist[hs][ws] = Dist[h][w] + 1
    return Dist

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q)
    print(ret[glh][glw])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

C = [input() for _ in [0]*H]

import heapq
hpop = heapq.heappop
hpush = heapq.heappush

d = [[-1]*W for _ in [0]*H]
hq = [(0,x1-1,y1-1)]
while hq:
    d0,x,y = hpop(hq)
    if d[x][y] != -1 : continue
    d[x][y] = d0
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        for k in range(1,K+1):
            if (not 0<=x+dx*k<H) or (not 0<=y+dy*k<W): break
            if d[x+dx*k][y+dy*k] != -1: break
            if C[x+dx*k][y+dy*k] == "@": break
            hpush(hq,(d0+1,x+dx*k,y+dy*k))

print(d[x2-1][y2-1])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush 
from collections import deque
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y, direction)
    inf = 1e18
    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(0, xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        cost, x, y = que.popleft()
        if cost > dist[x][y]:
            continue
        for v in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[v]
                ny += dy[v]
                if not field[nx][ny]:
                    break
                if dist[nx][ny]<=dist[x][y]:
                    break
                if dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    que.append((dist[nx][ny], nx, ny))

    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])

        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    for i in range(h):
        # False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    h += 2
    w += 2
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

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

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        m,x,y =  heapq.heappop(q)
        if d[x][y] < m: continue
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < m + 1: break
                if d[nx][ny] == m + 1: continue
                d[nx][ny] = m + 1
                q.append((m+1,nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        m,x,y =  heapq.heappop(q)
        if d[x][y] < m: continue
        d[x][y] = m
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < m + 1: break
                if d[nx][ny] == m + 1: continue
                d[nx][ny] = m + 1
                q.append((m+1,nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        n,x,y =  heapq.heappop(q)
        if d[x][y] < n: continue
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((d[nx][ny],nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()