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:
def main():
    from collections import deque

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

    G = [['#'] * (W + 2)]
    G_append = G.append
    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
        # print ('x, y', x, y)
        if dp[x][y] == dp[x + 1][y] and dp[x][y] != INF:
            pass
        else:
            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
        if dp[x][y] == dp[x - 1][y] and dp[x][y] != INF:
            pass
        else:
            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
        if dp[x][y] == dp[x][y + 1] and dp[x][y] != INF:
            pass
        else:
            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[x][y] == dp[x][y - 1] and dp[x][y] != INF:
            pass
        else:
            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)

if __name__ == '__main__':
    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
    # print ('x, y', x, y)
    if dp[x][y] == dp[x + 1][y] and dp[x][y] != INF:
        pass
    else:
        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
    if dp[x][y] == dp[x - 1][y] and dp[x][y] != INF:
        pass
    else:
        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
    if dp[x][y] == dp[x][y + 1] and dp[x][y] != INF:
        pass
    else:
        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[x][y] == dp[x][y - 1] and dp[x][y] != INF:
        pass
    else:
        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:
from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = [((0, 0), x1-1, y1-1, i) for i in range(4)]
used = [[[False for l in range(4)] for i in range(w)] for j in range(h)]

for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)

while q:
    count, x, y, d = heappop(q)
    if used[x][y][d]:
        continue
    if x == x2 and y == y2:
        break
    used[x][y][d] = True

    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] <= nextcount:
                continue
            dp[x+dx][y+dy][dd] = nextcount
            heappush(q, (nextcount, x+dx, y+dy, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = [((0, 0), x1-1, y1-1, i) for i in range(4)]
used = [[[False for l in range(4)] for i in range(w)] for j in range(h)]

for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)

while q:
    count, x, y, d = heappop(q)
    if used[x][y][d]:
        continue
    used[x][y][d] = True

    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] < nextcount:
                continue
            dp[x+dx][y+dy][dd] = nextcount
            heappush(q, (nextcount, x+dx, y+dy, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = [((0, 0), x1-1, y1-1, i) for i in range(4)]
for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)

while q:
    count, x, y, d = heappop(q)
    if count != dp[x][y][d]:
        continue

    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] < nextcount:
                continue
            dp[x+dx][y+dy][dd] = nextcount
            heappush(q, (nextcount, x+dx, y+dy, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        oy,ox = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = oy,ox
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0 and dist[y][x] <= dist[oy][ox]:
                    break
                dist[y][x] = dist[oy][ox] + 1
                q.append((y,x))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = [((0, 0), x1-1, y1-1, i) for i in range(4)]
while q:
    count, x, y, d = heappop(q)
    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] > nextcount:
                dp[x+dx][y+dy][dd] = nextcount
                heappush(q, (nextcount, x+dx, y+dy, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx,-1)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        oy,ox,turn = q.popleft()
        for i,dy,dx in zip(range(4),Dy,Dx):
            if i == turn:
                continue
            y,x = oy,ox
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0 and dist[y][x] <= dist[oy][ox]:
                    break
                dist[y][x] = dist[oy][ox] + 1
                q.append((y,x,(i + 2)%4))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = [(si, sj)]
    while queue:
        i, j = queue.pop()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                if dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = [(si, sj)]
    while queue:
        i, j = queue.pop()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                dist[ni][nj] = dist[i][j] + 1
                queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()
        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                # M[x2][y2] = d + 1

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      #dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      #dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      #dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      #dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t] + 1: break
      #dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t] + 1: break
      #dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t] + 1: break
      #dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t] + 1: break
      #dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([x * W + y])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  t = Q.popleft()
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(dp[t])
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append(pp * W + q)
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append(pp * W + q)

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append(p * W + qq)

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append(p * W + qq)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

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

bfs(xs - 1, ys - 1, 0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        # M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([x * W + y])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  t = Q.popleft()
  p = t // W
  q = t % W
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append(pp * W + q)
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append(pp * W + q)

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append(p * W + qq)

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append(p * W + qq)
if dp[u * W + v] != inf: print(dp[u * W + v])
else: print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

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

bfs(xs - 1, ys - 1, 0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = [x * W + y]
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  t = Q.pop()
  p = t // W
  q = t % W
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append(pp * W + q)
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      dp[pp * W + q] = dp[t] + 1
      Q.append(pp * W + q)

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append(p * W + qq)

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      dp[p * W + qq] = dp[t] + 1
      Q.append(p * W + qq)
if dp[u * W + v] != inf: print(dp[u * W + v])
else: print(-1)