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 LI():return list(map(int,input().split()))
def MI():return map(int,open(0).read().split())
def I():return int(input())
INF=float("inf")
# from pprint import*
from collections import deque
h,w,k=LI()
x1,y1,x2,y2=LI()
x1-=1
y1-=1
x2-=1
y2-=1
# line=[list("#"*(w+2))]
# maze=line+
maze=[list(input()) for _ in range(h)]
# +line
# pprint(maze)
dist=[[INF]*(w) for _ in range(h)]

q=deque([])


# exit()
q.append((x1,y1))
dist[x1][y1]=0
while q:
    (xn,yn)=q.popleft()
    # print(xn)
    # exit()
    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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
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)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

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:
import sys
input = sys.stdin.readline
from collections import deque

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

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
MAP[x1-1][y1-1]=0

while Q:
    x,y,c=Q.pop()
    if MAP[x][y]<c:
        continue

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft((x+i,y,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft((x-i,y,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft((x,y+i,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft((x,y-i,MAP[x][y]+1))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
c=[input() for _ in range(h)]
"""
ha=[]
for i in range(h):
  for j in range(w):
    if c[i][j]=='@':
      ha.append([i,j])
"""
from collections import deque
seen=[[0]*w for _ in range(h)]
todo=deque([[0,x1,y1]])
seen[x1][x2]=1
while todo:
  t,x,y=todo.popleft()

  if x==x2 and y==y2:
    print(t)
    exit(0)
  if x>0:
    for xi in range(x-1,max(x-k,0)-1,-1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if x<h-1:
    for xi in range(x+1,min(x+k,h-1)+1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if y>0:
    for yi in range(y-1,max(y-k,0)-1,-1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
  if y<w-1:
    for yi in range(y+1,min(y+k,w-1)+1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

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

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

T=0

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

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

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

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

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

    d=D[(p,q)]
    T=set()
    for (s,t) in N:
        if (s,t) not in S:
            T.add((s,t))
            Q.append((s,t))
            D[(s,t)]=d+1
            if (s,t)==(u,v):
                print(d+1)
                sys.exit()
    S|=T
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = iter(sys.stdin.readlines()).__next__

R, C, K = [int(x) for x in input().split()]
X1, Y1, X2, Y2 = [int(x) - 1 for x in input().split()]  # 0 indexed

grid = [input().rstrip() for r in range(R)]

source = (X1, Y1)
q = deque([source])
dist = {source: 0}


def getNbr(node):
    r, c = node
    ret = []
    for dr, dc in [(0, 0), (-1, 0), (0, -1), (0, 1), (1, 0)]:
        for k in range(1, K + 1):
            nr = r + dr * k
            nc = c + dc * k
            if not (0 <= nr < R and 0 <= nc < C):
                break
            if grid[nr][nc] == "@":
                break
            ret.append((nr, nc))
    return ret


while q:
    node = q.popleft()
    d = dist[node]
    for nbr in getNbr(node):
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = d + 1


if False:
    for row in grid:
        print(row)
    print()
    for r in range(R):
        for c in range(C):
            print(dist.get((r, c), "?"), end=" ")
        print()


if (X2, Y2) in dist:
    print(dist[(X2, Y2)])
else:
    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])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from numba import njit

input = stdin.readline


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

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

from collections import deque

d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((x1,y1))
d[x1][y1]=0
while queue:
    y,x=queue.popleft()
    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        cnt_k=0
        while cnt_k<k:
            if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
                break
            if c[new_y][new_x]=='.' and (d[new_y][new_x]==-1 or d[new_y][new_x]==d[y][x]+1):
                d[new_y][new_x]=d[y][x]+1
                queue.append((new_y, new_x))
                new_y=new_y+d_y
                new_x=new_x+d_x
                cnt_k+=1
            else:
                break

print(d[x2][y2])

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]: continue
      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]: continue
      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]: continue
      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]: continue
      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:
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] == -1 or visited[ni][nj] > visited[i][j] + 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:
from collections import deque
import sys

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

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

T=0

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

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

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

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

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

    d=D[(p,q)]
    for (s,t) in N:
        Q.append((s,t))
        D[(s,t)]=d+1
        if (s,t)==(u,v):
            print(D[(u,v)])
            sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
arr = [[-1] * w for _ in range(h)]
for i in range(h):
  a = input()
  for j, v in enumerate(a):
    if v == '@':
      arr[i][j] = -2
arr[x1-1][y1-1] = 0
q = collections.deque([(x1-1,y1-1)])
while q:
  x, y = q.popleft()
  step = arr[x][y]
  if x == x2-1 and y == y2-1:
    print(step)
    break
  for d in ((0, 1), (1, 0), (0, -1), (-1, 0)):
    for p in range(1, k+1):
      nx, ny = x + p * d[0], y + p * d[1]
      if not 0 <= nx < h or not 0 <= ny < w or arr[nx][ny] not in (-1, step+1):
        break
      arr[nx][ny] = step + 1
      q.append((nx, ny))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
h, w, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
m = [['@'] * (w+2) for i in range(h+2)]
for j in range(h):
    m[j+1][1:w+1] = list(input()) #適宜変える

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

d = [[-1 for k in range(w+2)] for j in range(h+2)]
s = [x1, y1]
todo = [s]
d[s[0]][s[1]] = 0
while(todo != []): #BFS d:sからの距離
    v = todo.pop(0)
    for k in range(4):
        for l in range(1, K+1):
            if m[v[0]+l*dx[k]][v[1]+l*dy[k]] != '@' and d[v[0]+l*dx[k]][v[1]+l*dy[k]] == -1:
                d[v[0]+l*dx[k]][v[1]+l*dy[k]] = d[v[0]][v[1]]+1
                todo.append([v[0]+l*dx[k], v[1]+l*dy[k]])
            elif m[v[0]+l*dx[k]][v[1]+l*dy[k]] == '@':
                break

print(d[x2][y2])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
INF = 10 ** 6 + 1
H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
D = [[INF for i in range(W)] for j in range(H)]
D[x1-1][y1-1] = 0
tx = [1,0,-1,0]
ty = [0,1,0,-1]

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

while not q.empty():
    x, y, k = q.get()
    if x == x2 - 1 and y == y2 - 1:
        break
    for i in range(4):
        nx = x
        ny = y
        for _ in range(K):
            nx += tx[i]
            ny += ty[i]
            if (not (0 <= nx <= H-1 and 0 <= ny <= W-1)) or MAP[nx][ny] == '@' or D[nx][ny] < k + 1:
                break
            D[nx][ny] = k + 1
            q.put([nx, ny, k+1])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
sy, sx, gy, gx = LI()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
grid = SRL(h)

def solve():
    grid[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for l in range(1, k + 1):
                ny = cy + i * l
                nx = cx + j * l
                if 0 <= ny < h and 0 <= nx < w:
                    if grid[ny][nx] == "@":
                        break
                    elif grid[ny][nx] == '.' or grid[cy][cx] + 1 <= grid[ny][nx]:
                        grid[ny][nx] = grid[cy][cx] + 1
                        que += [(ny, nx)]
                    else:
                        break
                else:
                    break
    return grid[gy][gx]

ans = solve()
if ans == ".":
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
S = [input() for _ in range(H)]
from collections import deque

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]
        # 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+1
                    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+1
                    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+1
                    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+1
                    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])

Submission status: Time Limit Exceeded

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


def to_ind(i, j):
    return i * w + j

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 9

graph = [[] for i in range(h * w)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "@":
            continue
        for dj in range(1, k + 1):
            if not(0 <= j + dj < w):
                break
            if s[i][j + dj] == "@":
                break
            graph[to_ind(i, j)].append(to_ind(i, j + dj))
            graph[to_ind(i, j + dj)].append(to_ind(i, j))
        for di in range(1, k + 1):
            if not(0 <= i + di < h):
                break
            if s[i + di][j] == "@":
                break
            graph[to_ind(i, j)].append(to_ind(i + di, j))
            graph[to_ind(i + di, j)].append(to_ind(i, j))   

visited = [INF] * (h * w)
visited[to_ind(x1 - 1, y1 - 1)] = 0
q = deque([to_ind(x1 - 1, y1 - 1)])
while q:
    v = q.pop()
    for nxt_v in graph[v]:
        if visited[nxt_v] <= visited[v] + 1:
            continue
        visited[nxt_v] = visited[v] + 1
        q.append(nxt_v)

if visited[to_ind(x2 - 1, y2 - 1)] == INF:
    print(-1)
else:
    print(visited[to_ind(x2 - 1, y2 - 1)])

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

    return visited[i2][j2]

print(solve())