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:
import sys
import heapq
from collections import deque
sys.setrecursionlimit(10 ** 8)

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

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

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


def bfs(x1, y1, d):
    q = deque()
    # heapq.heapify(q)
    # heapq.heappush(q, (d, (x1, y1)))
    q.append((d, (x1, y1)))

    while q:
        # d, u = heapq.heappop(q)
        d, u = q.popleft()
        x1 = u[0]
        y1 = u[1]

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            k = 1
            while k <= K:
                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] != float('inf'):
                    break

                # heapq.heappush(q, (d + 1, (x2, y2)))
                q.append((d + 1, (x2, y2)))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    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:
                    continue
                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:
def LI():return list(map(int,input().split()))
INF=float("inf")
from collections import deque
def main():
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=list(list(input()) for _ in range(h))
    dist=[[INF]*(w) for _ in range(h)]
    q=deque([])
    q.append((x1,y1))
    dist[x1][y1]=0
    while q:
        x,y=q.popleft()
        for vx,vy in ([0,1],[0,-1],[1,0],[-1,0]):
            flg=True
            for kk in range(1,k+1):
                if not flg:
                    break
                nx=x+kk*vx
                ny=y+kk*vy
                if not(0<=nx<h) or not(0<=ny<w):
                    break
                if maze[nx][ny]=="@":
                    flg=False
                    break
                if dist[nx][ny]<=dist[x][y]:
                    break
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
    ans=dist[x2][y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = [(0, x1 - 1, y1 - 1)]
while q :
  ccost, cx, cy = heappop(q)
  if ccost > dist[cx][cy] :
    continue
  for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
    for i in range(1, K + 1) :
      nx, ny = dx * i + cx, dy * i + cy
      ncost = ccost + 1
      if not (0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost <= dist[nx][ny]) :
        break
      if ncost <= dist[nx][ny] :
        heappush(q, (ncost, nx, ny))
        dist[nx][ny] = ncost

if dist[x2 - 1][y2 - 1] == float('inf') :
  print(-1)
else :
  print(dist[x2 - 1][y2 - 1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    q = deque()
    s = (XY1XY2[0]-1)*W + XY1XY2[1]-1
    go = (XY1XY2[2]-1)*W + XY1XY2[3]-1
    q.append(s)
    d = {s: 0}
    while q:
        u = q.popleft()
        i = u // W
        j = u % W
        e = list()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                n = (i-k)*W + j
                if n not in d:
                    e.append(n)
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                n = (i+k)*W + j
                if n not in d:
                    e.append(n)
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                n = i*W + j-k
                if n not in d:
                    e.append(n)
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                n = i*W + j+k
                if n not in d:
                    e.append(n)
            else:
                break
        for v in e:
            q.append(v)
            d[v] = d[u] + 1
            if v == go:
                return d[v]

    return -1


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))

    # H = 1000
    # W = 1000
    # K = 1000
    # XY1XY2 = [1, 1, H, W]
    # C = ['.' * W] * H
    # print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**18 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1,0,1))
while q:
  px,py,direc,dis = q.popleft()
  for j in range(1 if direc != "U" else dis,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= dp[px][py]:
      break
    dp[px+j][py] = dp[px][py]+1
    q.append((px+j,py,"U",k-j+1))
  for j in range(1 if direc != "D" else dis,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= dp[px][py]:
      break
    dp[px-j][py] = dp[px][py]+1
    q.append((px-j,py,"D",k-j+1))
  for j in range(1 if direc != "L" else dis,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= dp[px][py]:
      break 
    dp[px][py+j] = dp[px][py]+1
    q.append((px,py+j,"L",k-j+1))
  for j in range(1 if direc != "R" else dis,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= dp[px][py]:
      break
    dp[px][py-j] = dp[px][py]+1
    q.append((px,py-j,"R",k-j+1))
if dp[gx-1][gy-1] == 10**18:
  print(-1)
else:
  print(dp[gx-1][gy-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = [(0, x1 - 1, y1 - 1)]
while q :
  ccost, cx, cy = heappop(q)
  if ccost > dist[cx][cy] :
    continue
  for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
    for i in range(1, K + 1) :
      nx, ny = dx * i + cx, dy * i + cy
      ncost = ccost + 1
      if not (0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost <= dist[nx][ny]) :
        break
      heappush(q, (ncost, nx, ny))
      dist[nx][ny] = ncost

if dist[x2 - 1][y2 - 1] == float('inf') :
  print(-1)
else :
  print(dist[x2 - 1][y2 - 1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    q = deque()
    s = (XY1XY2[0]-1)*W + XY1XY2[1]-1
    go = (XY1XY2[2]-1)*W + XY1XY2[3]-1
    q.append(s)
    d = {s: 0}
    while q:
        u = q.popleft()
        i = u // W
        j = u % W
        e = list()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                e.append((i-k)*W + j)
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                e.append((i+k)*W + j)
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                e.append(i*W + j-k)
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                e.append(i*W + j+k)
            else:
                break
        for v in e:
            if v not in d:
                q.append(v)
                d[v] = d[u] + 1
                if v == go:
                    return d[v]

    return -1 if go not in d else d[go]


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))

    # H = 1000
    # W = 1000
    # K = 1000
    # XY1XY2 = [1, 1, H, W]
    # C = ['.' * W] * H
    # print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
sys.setrecursionlimit(10 ** 8)

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

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

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


def bfs(x1, y1, d):
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (d, (x1, y1)))

    while q:
        d, u = heapq.heappop(q)
        x1 = u[0]
        y1 = u[1]

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            k = 1
            while k <= K:
                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] != float('inf'):
                    break

                heapq.heappush(q, (d + 1, (x2, y2)))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=[]
heapq.heappush(q,(0,sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
while len(q)!=0:
  c,x,y=heapq.heappop(q)
  cost[y][x]=min(cost[y][x],c)
  for i in range(1,k+1):
    if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
      heapq.heappush(q,(c+1,x+i,y))
    else:
      break
  for i in range(1,k+1):
    if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
      heapq.heappush(q,(c+1,x-i,y))
    else:
      break
  for i in range(1,k+1):
    if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
      heapq.heappush(q,(c+1,x,y+i))
    else:
      break
  for i in range(1,k+1):
    if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
      heapq.heappush(q,(c+1,x,y-i))
    else:
      break
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
from functools import lru_cache

directions = [ (-1,0),(1,0),(0,-1),(0,1) ]
    
@lru_cache
def solve():
    H, W, K = map(int, input().split(" "))
    i1, j1, i2, j2 = map(lambda x: int(x)-1, input().split(" "))
    board = []
    for _ in range(H):
        board.append( list(input()))
    visited = [ [float('inf')]*W for _ in range(H) ]

    q = Queue()
    visited[i1][j1] = 0
    q.put( (i1, j1) )

    while not q.empty():
        i, j  = q.get()
        
        for di, dj in directions:
            for k in range(1, K+1):
                ni = di*k+i
                nj = dj*k+j
                if ni < 0 or ni >= H : 
                    break 
                if nj < 0 or nj >= W :
                    break
                if board[ni][nj] == '@' :
                    break
                if visited[ni][nj] < visited[i][j] + 1 : 
                    break 
                elif visited[ni][nj] == visited[i][j] + 1 :
                    continue 
                visited[ni][nj] = visited[i][j] + 1
                q.put( (ni, nj) )

    res = visited[i2][j2]
    return res if res != float('inf') else -1

print(solve())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    q = deque()
    s = (XY1XY2[0]-1)*W + XY1XY2[1]-1
    go = (XY1XY2[2]-1)*W + XY1XY2[3]-1
    q.append(s)
    d = {s: 0}
    while q:
        u = q.popleft()
        i = u // W
        j = u % W
        e = set()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                e.add((i-k)*W + j)
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                e.add((i+k)*W + j)
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                e.add(i*W + j-k)
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                e.add(i*W + j+k)
            else:
                break
        for v in e:
            if v not in d:
                q.append(v)
                d[v] = d[u] + 1

    return -1 if go not in d else d[go]


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

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())
c = []
for _ in range(h):
    c.append(input())
q = deque([(x1-1, y1-1)])
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
dist = [[100000]*w for _ in range(h)]
dist[y1-1][x1-1] = 0
while q:
    x, y = q.popleft()
    for ddx, ddy in dxdy:
        for i in range(1, k+1):
            dx = ddx*i
            dy = ddy*i
            if not (0<=x+dx<w and 0<=y+dy<h):
                break
            if c[y+dy][x+dx]=='@' or dist[y+dy][x+dx]<=dist[y][x]:
                break
            if x+dx==x2-1 and y+dy==y2-1:
                print(dist[y][x]+1)
                exit(0)
            dist[y+dy][x+dx] = dist[y][x]+1
            q.append((x+dx, y+dy))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import os
import heapq

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
sx, sy, gx, gy = list(map(int, sys.stdin.buffer.readline().split()))
C = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]

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

u_hist = [[(INF, INF, INF)] * W for _ in range(H)]
d_hist = [[(INF, INF, INF)] * W for _ in range(H)]
l_hist = [[(INF, INF, INF)] * W for _ in range(H)]
r_hist = [[(INF, INF, INF)] * W for _ in range(H)]
u_hist[sx][sy] = (0, 0, 0)
d_hist[sx][sy] = (0, 0, 0)
l_hist[sx][sy] = (0, 0, 0)
r_hist[sx][sy] = (0, 0, 0)
hist = (u_hist, d_hist, l_hist, r_hist)
D = ((0, 1), (1, 0), (0, -1), (-1, 0))

ans = INF
heap = [(0, 0, 0, sx, sy, 0), (0, 0, 0, sx, sy, 1), (0, 0, 0, sx, sy, 2), (0, 0, 0, sx, sy, 3)]
ac = 0
while heap:
    p, s, cnt, x, y, d = heapq.heappop(heap)
    # p = s + cnt / K
    if (p, s, cnt) > hist[d][x][y]:
        continue
    if x == gx and y == gy:
        ans = min(ans, s + (cnt + K - 1) // K)
        ac  += 1
    if ac  >= 4:
        break
    for i in range(4):
        nd = (d + i) % 4
        dx, dy = D[nd]
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if C[nx][ny] == '@':
            continue
        if nd == d:
            np = s + (cnt + 1) / K
            if hist[nd][nx][ny] < (np, s, cnt + 1):
                continue
            hist[nd][nx][ny] = (np, s, cnt + 1)
            heapq.heappush(heap, (np, s, cnt + 1, nx, ny, nd))
        else:
            ns = s + (cnt + K - 1) // K
            ncnt = 1
            np = ns + 1 / K
            if hist[nd][nx][ny] < (np, ns, ncnt):
                continue
            hist[nd][nx][ny] = (np, ns, ncnt)
            heapq.heappush(heap, (np, ns, ncnt, nx, ny, nd))

if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append((sx,sy))
  while d:
    x,y=d.popleft()
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append((x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    q = deque()
    s = (XY1XY2[0]-1, XY1XY2[1]-1)
    go = (XY1XY2[2]-1, XY1XY2[3]-1)
    q.append(s)
    d = {s: 0}
    while q:
        u = q.popleft()
        i, j = u
        e = set()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                e.add((i-k, j))
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                e.add((i+k, j))
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                e.add((i, j-k))
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                e.add((i, j+k))
            else:
                break
        for v in e:
            if v not in d:
                q.append(v)
                d[v] = d[u] + 1

    return -1 if go not in d else d[go]


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
from functools import lru_cache

directions = [ (-1,0),(1,0),(0,-1),(0,1) ]
    
@lru_cache
def solve():
    H, W, K = map(int, input().split(" "))
    i1, j1, i2, j2 = map(lambda x: int(x)-1, input().split(" "))
    board = []
    for _ in range(H):
        board.append( list(input()))
    visited = [ [-1]*W for _ in range(H) ]

    q = Queue()
    visited[i1][j1] = 0
    q.put( (i1, j1) )

    while not q.empty():
        i, j  = q.get()
        
        for di, dj in directions:
            for k in range(1, K+1):
                ni = di*k+i
                nj = dj*k+j
                if ni < 0 or ni >= H or nj < 0 or nj >= W or board[ni][nj] == '@' :
                    break 

                if visited[ni][nj] == -1 or visited[ni][nj] > visited[i][j] + 1 :
                    visited[ni][nj] = visited[i][j] + 1
                    q.put( (ni, nj) )

    return visited[i2][j2]  

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(1,k+1):
    if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
      cost[y][x+i]=c+1
      q.append((x+i,y))
    else:
      break
  for i in range(1,k+1):
    if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
      cost[y][x-i]=c+1
      q.append((x-i,y))
    else:
      break
  for i in range(1,k+1):
    if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
      cost[y+i][x]=c+1
      q.append((x,y+i))
    else:
      break
  for i in range(1,k+1):
    if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
      cost[y-i][x]=c+1
      q.append((x,y-i))
    else:
      break
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1:
                if cord[y][x+i] == '.':
                    l.append((x+i,y))
                elif cord[y][x+i] == '@':
                    f1 = False
            if f2:
                if cord[y][x-i] == '.':
                    l.append((x-i,y))
                elif cord[y][x-i] == '@':
                    f2 = False
            if f3:
                if cord[y+i][x] == '.':
                    l.append((x,y+i))
                elif cord[y+i][x] == '@':
                    f3 = False
            if f4:
                if cord[y-i][x] == '.':
                    l.append((x,y-i))
                elif cord[y-i][x] == '@':
                    f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = '#'
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
print(bfs(xg,yg))

Submission status: Time Limit Exceeded

Solution code:
#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.' or field[tx][ty] ==moves:
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)