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:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
d=[INF]*(W+2)*(H+2)
direction=[[0]*4 for _ in range((H+2)*(W+2))]
que.append(st)
d[st]=0
di=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    for k in range(4):
        nv=v+di[k]
        if c[nv]=='.':
            if direction[v][k]>0:
                if d[nv]>d[v]:
                    direction[nv]=[0]*4
                    direction[nv][k]=direction[v][k]-1
                    d[nv]=d[v]
                    que.append(nv)
                elif d[nv]==d[v]:
                    direction[nv][k]=direction[v][k]-1
            else:
                if d[nv]>d[v]+1:
                    direction[nv]=[0]*4
                    direction[nv][k]=K-1
                    d[nv]=d[v]+1
                    que.append(nv)
                elif d[nv]==d[v]+1:
                    direction[nv][k]=K-1
print(d[gl] if d[gl]!=INF else -1)

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,"n"))
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,d=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
      if d=="r":
        q.appendleft((x+i,y,"r"))
      else:
        q.append((x+i,y,"r"))
    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
      if d=="l":
        q.appendleft((x-i,y,"l"))
      else:
        q.append((x-i,y,"l"))
    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
      if d=="d":
        q.appendleft((x,y+i,"d"))
      else:
        q.append((x,y+i,"d"))
    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
      if d=="u":
        q.appendleft((x,y-i,"u"))
      else:
        q.append((x,y-i,"u"))
    else:
      break
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if pt > dijk[dr][x][y]:
    continue
    
  for dr2 in range(4):
    if dijk[dr2][x][y] > (pt-1)//k*k+k:
      dijk[dr2][x][y] = (pt-1)//k*k+k
      heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] > pt+1:
      dijk[dr][x-1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x-1,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] > pt+1:
      dijk[dr][x+1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x+1,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] > pt+1:
      dijk[dr][x][y-1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y-1])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] > pt+1:
      dijk[dr][x][y+1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y+1])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(int,input().split())
f = []
v = []
for y in range(h):
    f.append([-1 if i == "@" else 0 for i in input().strip()])
    v.append([0]*w)
q = []
q.append((x1-1,y1-1,1))
ans = 0

while len(q):
    x,y,s = q.pop(0)
    if (x,y) == (x2-1,y2-1):
        ans = s
        break
    for i in range(1,k+1):
        if x-i < 0:
            break
        if v[x-i][y] != 0:
            continue
        if f[x-i][y] == -1:
            break
        q.append((x-i,y,s+1))
        v[x-i][y] = s
    for i in range(1,k+1):
        if x+i > h-1:
            break
        if v[x+i][y] != 0:
            continue
        if f[x+i][y] == -1:
            break
        q.append((x+i,y,s+1))
        v[x+i][y] = s
    for i in range(1,k+1):
        if y-i < 0:
            break
        if v[x][y-i] != 0:
            continue
        if f[x][y-i] == -1:
            break
        q.append((x,y-i,s+1))
        v[x][y-i] = s
    for i in range(1,k+1):
        if y+i > w-1:
            break
        if v[x][y+i] != 0:
            continue
        if f[x][y+i] == -1:
            break
        q.append((x,y+i,s+1))
        v[x][y+i] = s

print(ans-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)]

dd = [i+1 for i in range(K)]

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
while q:
  y,x = q.popleft()
  for i in range(K):
    ny,nx = y+dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y-dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y,x+dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y,x-dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          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:
# -*- 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)]

dd = [i+1 for i in range(K)]

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
while q:
  y,x = q.popleft()
  for i in range(K):
    ny,nx = y+dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y-dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y,x+dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y,x-dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] >= d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          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 heapq import heappop, heappush

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

C = [input() for i in range(H)]
dist = {}
d = [[0, x1, y1, K, -1]]
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  cost, x, y, remain, v = heappop(d)
  if (x, y, v%2) in dist:
    continue
  dist[(x, y, v%2)] = cost
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and C[xx][yy] != '@':
      if (xx, yy, i%2) in dist:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, i])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

cands = [dist[(x2, y2, i)] for i in range(2) if (x2, y2, i) in dist]
if cands:
  print(min(cands))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if pt > dijk[dr][x][y]:
    continue
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] > pt+1:
      dijk[dr][x-1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] > pt+1:
      dijk[dr][x+1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] > pt+1:
      dijk[dr][x][y-1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] > pt+1:
      dijk[dr][x][y+1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

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)]

dd = [i+1 for i in range(K)]

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
while q:
  y,x = q.popleft()
  for i in range(K):
    ny,nx = y+dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
      else:
        break
  for i in range(K):
    ny,nx = y-dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
      else:
        break
  for i in range(K):
    ny,nx = y,x+dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
      else:
        break
  for i in range(K):
    ny,nx = y,x-dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
      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:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
c=['@'*(W+2) for _ in range(H+2)]
for column in range(1,H+1):
    c[column]='@'+input()+'@'
que=deque()
d=[[INF]*(W+2) for _ in range(H+2)]
v=[[[0]*4 for _ in range(W+2)] for _ in range(H+2)]
que.append((sy,sx))
d[sy][sx]=0
dy,dx=(1,0,-1,0),(0,1,0,-1)
while que:
    y,x=que.popleft()
    for k in range(4):
        ny,nx=y+dy[k],x+dx[k]
        if c[ny][nx]=='.':
            if v[y][x][k]>0:
                if d[ny][nx]>d[y][x]:
                    v[ny][nx]=[0]*4
                    v[ny][nx][k]=v[y][x][k]-1
                    d[ny][nx]=d[y][x]
                    que.append((ny,nx))
                elif d[ny][nx]==d[y][x]:
                    v[ny][nx][k]=v[y][x][k]-1
            else:
                if d[ny][nx]>d[y][x]+1:
                    v[ny][nx]=[0]*4
                    v[ny][nx][k]=K-1
                    d[ny][nx]=d[y][x]+1
                    que.append((ny,nx))
                elif d[ny][nx]==d[y][x]+1:
                    v[ny][nx][k]=K-1
print(d[gy][gx] if d[gy][gx]!=INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
# dist = [[None]*w for _ in range(h)]
dist = [None]*(w*h)
dist[x1*w+y1] = 0
# done = [[0]*w for _ in range(h)]
done = [0]*(w*h)
done[x1*w+y1] = 15

while q:
    d, x, y, t, td = hpp(q)
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if dist[nx*w+ny] is None or nd<dist[nx*w+ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx*w+ny] = nd
            done[nx*w+ny] = 1<<(i)
        elif nd==dist[nx*w+ny]and ((done[nx*w+ny]&1<<(i))==0):
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            done[nx*w+ny] |= 1<<(i)
            
if dist[x2*w+y2] is None:
    print(-1)
else:
    print(dist[x2*w+y2])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

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

    maze=[]
    for _ in range(h):
        maze.append(tuple(input()))

    #maze=[list(input()) for _ in range(h)]

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

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        dis[ny][nx]=dis[y][x]+1
                        d.append((nx,ny))
                        #pri(dis)
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[None]*w for _ in range(h)]
dist[x1][y1] = 0
done = [[0]*w for _ in range(h)]
done[x1][y1] = 15

while q:
    d, x, y, t, td = hpp(q)
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if dist[nx][ny] is None or nd<dist[nx][ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx][ny] = nd
            done[nx][ny] = 1<<(i)
        elif nd==dist[nx][ny]and ((done[nx][ny]&1<<(i))==0):
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            done[nx][ny] |= 1<<(i)
            
if dist[x2][y2] is None:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[None]*w for _ in range(h)]
dist[x1][y1] = 0
done = [[0]*w for _ in range(h)]
done[x1][y1] = 15

while q:
    d, x, y, t, td = hpp(q)
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if dist[nx][ny] is None or nd<dist[nx][ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx][ny] = nd
            done[nx][ny] = 1<<(i)
        elif nd==dist[nx][ny]and ((done[nx][ny]&1<<(i))==0):
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            done[nx][ny] |= 1<<(i)
            
if dist[x2][y2] is None:
    print(-1)
else:
    print(dist[x2][y2])