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
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    a, b, x, y = map(int, input().split())
    a -= 1
    b -= 1
    x -= 1
    y -= 1
    C = [input().strip("\n") for _ in range(H)]
    D = [[-1 for _ in range(W)] for h in range(H)]
    D[a][b] = 0
    q = []
    heapify(q)
    for h in range(a):
        #up
        if C[a-h-1][b] == "@": break
        else: heappush(q, (h // K + 1, a - h - 1, b, "ud"))
    for h in range(H-a-1):
        #down
        if C[a + h + 1][b] == "@": break
        else: heappush(q, (h // K + 1, a + h + 1, b, "ud"))
    for w in range(b):
        if C[a][b-w-1] == "@": break
        else: heappush(q, (w//K + 1, a, b-w-1, "lr"))
    for w in range(W - b - 1):
        if C[a][b+w+1] == "@": break
        else: heappush(q, (w//K + 1, a, b+w+1, "lr"))

    while q:
        d, h, w, direc = heappop(q)
        if D[h][w] == -1:
            D[h][w] = d
            if direc == "lr": #udのみ
                for dh in range(h):
                    if C[h-dh-1][w] == "@": break
                    else: heappush(q, (dh//K + d + 1, h-dh-1, w, "ud"))
                for dh in range(H-h-1):
                    if C[h+dh+1][w] == "@": break
                    else: heappush(q, (dh//K + d + 1, h+dh+1, w, "ud"))
            else:
                for dw in range(w):
                    if C[h][w-dw-1] == "@": break
                    else: heappush(q, (dw//K + d + 1, h, w-dw-1, "lr"))
                for dw in range(W-w-1):
                    if C[h][w+dw+1] == "@": break
                    else: heappush(q, (dw//K + d + 1, h, w+dw+1, "lr"))

    print(D[x][y])
    #print(D)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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) ]

    directions = [ (-1,0),(1,0),(0,-1),(0,1) ]
    q = deque()
    visited[i1][j1] = 0
    q.append( (i1, j1, 0) )
    while q:
        i, j, v  = q.popleft()
        if (i,j) ==(i2,j2) :
            return visited[i][j]
        if v > visited[i][j] :
            continue

        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] > visited[i][j] + 1 :
                    break 

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

    return visited[i2][j2]

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w, k = MAP()
sx, sy, gx, gy = MAP()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [STR() for _ in range(h)]
marked = [[inf for _ in range(w)] for _ in range(h)]
marked[sx][sy] = 0
que = deque([[sx, sy, -1, 0, 0]])
while que:
    x, y, l_mov, cnt, num = que.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if ny < 0 or w <= ny or nx < 0 or h <= nx:
            continue
        if c[nx][ny] == '@':
            continue
        n_num = num
        n_cnt = cnt
        if l_mov == i and cnt < k:
            n_cnt += 1
        else:
            n_num += 1
            n_cnt = 1
        if marked[nx][ny] >= n_num:
            marked[nx][ny] = n_num
            if nx == gx and ny == gy:
                continue
            que.append([nx, ny, i, n_cnt, n_num])
#for i in marked:
#    print(i)
ans = marked[gx][gy]
print(ans if ans != inf else -1)

Submission status: Time Limit Exceeded

Solution code:
def LI():return list(map(int,input().split()))

INF=float("inf")
# from pprint import*
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(input()) for _ in range(h)]
    dist=[[INF]*(w) for _ in range(h)]
    
    q=deque([])
    
    q.append((x1,y1))
    dist[x1][y1]=0
    while q:
        (xn,yn)=q.popleft()
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,-kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,+kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(-kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        
        
        
        
    # pprint(maze)
    # for j in dist:print(*j)
    ans=dist[x2][y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

Submission status: Time Limit Exceeded

Solution code:
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)

h,w,k = imap()
sx,sy,gx,gy = imap()
S,G = (sx,sy), (gx,gy)

grid = [[1]*(w+2)] + [[1]+[int(elm == "@") for elm in list(sinput())]+[1] for i in range(h)] + [[1]*(w+2)]

#print(np.array(grid))

q = col.deque([(sx,sy)])
dep = col.defaultdict(int)
dep[S] = 1
while q:
    now = q.popleft()
    if now == (gx,gy): break
    x,y = now[0],now[1]
    nexts = []
    for i in range(1,k+1):
        if grid[x+i][y]: break
        else: nexts.append((x+i, y))
    for i in range(1,k+1):
        if grid[x-i][y]: break
        else: nexts.append((x-i, y))
    for i in range(1,k+1):
        if grid[x][y+i]: break
        else: nexts.append((x, y+i))
    for i in range(1,k+1):
        if grid[x][y-i]: break
        else: nexts.append((x, y-i))
    for next in nexts:
        nx,ny = next[0],next[1]
        if grid[nx][ny] or dep[next]: continue # 壁か探索済ならスキップ
        else: dep[next] = dep[now] + 1; q.append(next)

ans = dep[G]-1 if dep[G] else -1
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))
  s=set()
  while d:
    x,y=d.popleft()
    if (x,y) in s:
      s.discard((x,y))
      continue
    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))
      if b[x-i][y]!=0:
        s.add((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))
      if b[x+i][y]!=0:
        s.add((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))
      if b[x][y-j]!=0:
        s.add((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))
      if b[x][y+j]!=0:
        s.add((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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) ]

    directions = [ (-1,0),(1,0),(0,-1),(0,1) ]
    q = deque()
    visited[i1][j1] = 0
    q.append( (i1, j1, 0) )
    while q:
        i, j, v  = q.popleft()
        if (i,j) ==(i2,j2) :
            continue
        if v > visited[i][j] :
            continue

        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] > visited[i][j] + 1 :
                    break 
                
                if visited[ni][nj] == -1 :
                    visited[ni][nj] = visited[i][j] + 1
                    q.append( (ni, nj, visited[ni][nj]) )

    return visited[i2][j2]

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[0]*W for _ in range(H)]

queue = deque([(y1-1, x1-1, 0)])
def bfs(queue):
    while queue:
        y, x, cnt = queue.popleft()
        if y==y2-1 and x==x2-1:
            return cnt
        if checked[y][x]==1:
            continue
        checked[y][x]=1
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if not checked[ny][nx]:
                    queue.append((ny, nx, cnt+1))
    return -1

print(bfs(queue))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w, k = MAP()
sx, sy, gx, gy = MAP()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [STR() for _ in range(h)]
marked = [[inf for _ in range(w)] for _ in range(h)]
marked[sx][sy] = 0
que = [[sx, sy, -1, 0, 0]]
while que:
    x, y, l_mov, cnt, num = que.pop()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if ny < 0 or w <= ny or nx < 0 or h <= nx:
            continue
        if c[nx][ny] == '@':
            continue
        n_num = num
        n_cnt = cnt
        if l_mov == i and cnt < k:
            n_cnt += 1
        else:
            n_num += 1
            n_cnt = 1
        if marked[nx][ny] >= n_num:
            marked[nx][ny] = n_num
            if nx == gx and ny == gy:
                continue
            que.append([nx, ny, i, n_cnt, n_num])
#for i in marked:
#    print(i)
ans = marked[gx][gy]
print(ans if ans != inf else -1)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = ["" for _ in range(h)]
for i in range(h):
  ci = str(input())
  c[i] = ci
d = [[float("inf") for _ in range(w)] for _ in range(h)]
q = queue.Queue()
q.put((sx,sy,0))
d[sx][sy] = 0
while not q.empty():
  nx,ny,p = q.get()
  for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
    ax = nx + i
    ay = ny + j
    kc = 1
    while  kc <= k and ax >=0 and ax < h and ay >=0 and ay < w and c[ax][ay]=="." and d[ax][ay] > p:
      if ax == gx and ay == gy:
        print(p+1)
        exit()
      if d[ax][ay] != p:
        d[ax][ay] = p+1
        q.put((ax,ay,p+1))
      kc += 1
      ax += i
      ay += j
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve(h,w,k,x1,y1,x2,y2,M):
    d=deque()
    goali=x2-1
    goalj=y2-1
    reached=[[False]*w for _ in range(h)]
    reached[x1-1][y1-1]=True
    d.append((x1-1,y1-1,0))
    while len(d)>0:
        curi,curj,curt=d.popleft()
        if curi==goali and curj==goalj:
            return curt
        i=1
        while curi+i<h and i<=k:
            if M[curi+i][curj]=='@':
                break
            if not reached[curi+i][curj]:
                reached[curi+i][curj]=True
                d.append((curi+i,curj,curt+1))
            i+=1
        i=-1
        while 0<=curi+i and i>=-k:
            if M[curi+i][curj]=='@':
                break
            if not reached[curi+i][curj]:
                reached[curi+i][curj]=True
                d.append((curi+i,curj,curt+1))
            i-=1
        j=1
        while curj+j<w and j<=k:
            if M[curi][curj+j]=='@':
                break
            if not reached[curi][curj+j]:
                reached[curi][curj+j]=True
                d.append((curi,curj+j,curt+1))
            j+=1
        j=-1
        while 0<=curj+j and j>=-k:
            if M[curi][curj+j]=='@':
                break
            if not reached[curi][curj+j]:
                reached[curi][curj+j]=True
                d.append((curi,curj+j,curt+1))
            j-=1
    return -1

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
M=[input() for _ in range(h)]
print(solve(h,w,k,x1,y1,x2,y2,M))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


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


def main():
    h, w, k = map(int, input().strip().split())
    x1, y1, x2, y2 = map(int, input().strip().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    m = []
    costs = [[None for j in range(w)] for i in range(h)]
    for _ in range(h):
        m.append(list(input().strip()))
    q = deque()
    q.append((x1, y1, 0))
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q:
        (x, y, cost) = q.popleft()
        if (x, y) == (x2, y2):
            print(cost)
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@':
                    break
                if costs[new_x][new_y] is None:
                    costs[new_x][new_y] = cost + 1
                    q.append((new_x, new_y, cost + 1))
    print("-1")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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))
s=set()
while d:
  x,y=d.popleft()
  if (x,y) in s:
    s.discard((x,y))
    continue
  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))
    if b[x-i][y]!=0:
      s.add((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))
    if b[x+i][y]!=0:
      s.add((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))
    if b[x][y-j]!=0:
      s.add((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))
    if b[x][y+j]!=0:
      s.add((x,y+j))
    b[x][y+j]=b[x][y]+1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def BFS(maze,h,w,s,g,k): 
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    (x,y) = s
    (gx,gy) = g
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or maze[nx][ny] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    return d[gx][gy]

def main():
    h,w,k = map(int,input().split())
    x1,y1,x2,y2 = map(int,input().split())
    x1 -= 1
    x2 -= 1
    y1 -= 1
    y2 -= 1
    c = [list(input()) for _ in range(h)]
    print(BFS(c,h,w,[x1,y1],[x2,y2],k))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue

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

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]


xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            
            if nx>=0 and nx<H and ny>=0 and ny<W and li[nx][ny]==".":
                if cnt[nx][ny]!=10**10:
                    continue
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()

Submission status: Time Limit Exceeded

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


def main():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    S = [""]*H
    for i in range(H):
        S[i] = input()

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

    # 深さ優先探索
    def bfs(x, y):
        stack = deque([[x, y]])
        cost[x][y] = 0
        while stack:
            x, y = stack[0]
            point = cost[x][y] + 1
            # up
            for i in range(1, K+1):
                if x-i >= 0:
                    if S[x-i][y] == "." and cost[x-i][y] == -1:
                        cost[x-i][y] = point
                        stack.append([x-i, y])
                    elif S[x-i][y] == "@":
                        break
                else:
                    break
            # down
            for i in range(1, K+1):
                if x+i < H:
                    if S[x+i][y] == "." and cost[x+i][y] == -1:
                        cost[x+i][y] = point
                        stack.append([x+i, y])
                    elif S[x+i][y] == "@":
                        break
                else:
                    break
            # left
            for i in range(1, K+1):
                if y-i >= 0:
                    if S[x][y-i] == "." and cost[x][y-i] == -1:
                        cost[x][y-i] = point
                        stack.append([x, y-i])
                    elif S[x][y-i] == "@":
                        break
                else:
                    break
            # right
            for i in range(1, K+1):
                if y+i < W:
                    if S[x][y+i] == "." and cost[x][y+i] == -1:
                        cost[x][y+i] = point
                        stack.append([x, y+i])
                    elif S[x][y+i] == "@":
                        break
                else:
                    break

            stack.popleft()        

    bfs(sx-1, sy-1)
    print(cost[gx-1][gy-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**7
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "." and dist[ii][jj] > dist[i][j]:
				dist[ii][jj] = dist[i][j] + 1
				if ii == gh and jj == gw:
					print(dist[ii][jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
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)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W,K = IL()
y1,x1,y2,x2 = IL()
data = SLs(H)
d = [[INF for i in range(W)] for j in range(H)]
flag = [[0 for i in range(W)] for j in range(H)]

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
while q:
  y,x = q.popleft()
  y0,x0 = y+0,x+0
  d0 = d[y0][x0]
  #上
  count = K
  while count:
    count -= 1
    y -= 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x] = 1
      if data[y][x] != ".":
        break
    else:
      break
  #下
  y,x = y0,x0
  count = K
  while count:
    count -= 1
    y += 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x] = 1
      if data[y][x] != ".":
        break
    else:
      break
  #右
  y,x = y0,x0
  count = K
  while count:
    count -= 1
    x += 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x] = 1
      if data[y][x] != ".":
        break
    else:
      break
  #左
  y,x = y0,x0
  count = K
  while count:
    count -= 1
    x -= 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x] = 1
      if data[y][x] != ".":
        break
    else:
      break
  if d[y2-1][x2-1]!=INF:
    print(d[y2-1][x2-1])
    exit()
else:
  print(-1)