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: Wrong Answer

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,0,0,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-flag[y][x][0]
  y -= flag[y][x][0]
  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] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][0] = count
        flag[y][x][1] = K-count
      if data[y][x] != ".":
        break
    else:
      break
  #下
  y,x = y0,x0
  count = K-flag[y][x][1]
  y += flag[y][x][1]
  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][1] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][1] = count
        flag[y][x][0] = K-count
      if data[y][x] != ".":
        break
    else:
      break
  #右
  y,x = y0,x0
  count = K-flag[y][x][2]
  x += flag[y][x][2]
  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][2] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][2] = count
        flag[y][x][3] = K-count
      if data[y][x] != ".":
        break
    else:
      break
  #左
  y,x = y0,x0
  count = K-flag[y][x][3]
  x -= flag[y][x][3]
  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][3] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][3] = count
        flag[y][x][2] = K-count
      if data[y][x] != ".":
        break
    else:
      break
  if d[y2-1][x2-1]!=INF:
    print(d[y2-1][x2-1])
    exit()
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from sys import exit
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
grid=[list(map(lambda x:x=='.',list(input()))) for i in range(h)]
t=[[0]*w for i in range(h)]
t[x1-1][y1-1]=1
t[x2-1][y2-1]=-1
axis=[[1,0],[0,1],[-1,0],[0,-1]]
while True:
  flg_ng=True
  t_tmp=deepcopy(t)
  for x in range(h):
    for y in range(w):
      if t_tmp[x][y]==0: continue
      step=(1 if t_tmp[x][y]>0 else -1)
      for i in range(4):
      	for d in range(1,k+1):
          if not(0<=x+axis[i][0]*d<len(grid)) or not(0<=y+axis[i][1]*d<len(grid[0])): break
          if not grid[x+axis[i][0]*d][y+axis[i][1]*d]: break
          if(t_tmp[x+axis[i][0]*d][y+axis[i][1]*d]==0):
            flg_ng=False
            t[x+axis[i][0]*d][y+axis[i][1]*d]=t_tmp[x][y]+step
          elif(step*t_tmp[x+axis[i][0]*d][y+axis[i][1]*d]<0):
            print(abs(t_tmp[x][y])+abs(t_tmp[x+axis[i][0]*d][y+axis[i][1]*d])-1)
            exit()
  if flg_ng:
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2
s, t = x1 * W + y1, x2 * W + y2

def BFS(i0=0):
    Q = deque([(i0, 3)])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x, t = Q.popleft()
        if t & 1:
            for d in (1, -1):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if D[y] >= 0: break
                    D[y] = D[x] + 1
                    Q.append((y, 2))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
        if t & 2:
            for d in (W, -W):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if D[y] >= 0: break
                    D[y] = D[x] + 1
                    Q.append((y, 1))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
                        
    return D

print(BFS(s)[t])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[10**10]*(w+2) for i in range(h+2)]
V[sy][sx]=0
D=[[[0,0] for j in range(w+2)] for i in range(h+2)]
D[sy][sx]=[1,1]
X=deque([])
Y=deque([])
i=1
while G[sy-i][sx]==".":
  Y.append(sy-i)
  X.append(sx)
  V[sy-i][sx]=1
  D[sy-i][sx][0]=1
  if i==k:
    D[sy-i][sx][0]=0
    break
  i=i+1
i=1
while G[sy+i][sx]==".":
  Y.append(sy+i)
  X.append(sx)
  V[sy+i][sx]=1
  D[sy+i][sx][0]=1
  if i==k:
    D[sy+i][sx][0]=0
    break
  i=i+1

i=1
while G[sy][sx-i]==".":
  Y.append(sy)
  X.append(sx-i)
  V[sy][sx-i]=1
  D[sy][sx-i][1]=1
  if i==k:
    D[sy][sx-i][1]=0
    break
  i=i+1
i=1
while G[sy][sx+i]==".":
  Y.append(sy)
  X.append(sx+i)
  V[sy][sx+i]=1
  D[sy][sx+i][1]=1
  if i==k:
    D[sy][sx-i][1]=0
    break
  i=i+1

while len(X)>0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  if D[y][x]==[1,1]:
    continue
  if D[y][x][1]==0:
    i=1
    D[y][x][1]=1
    while G[y][x-i]==".":
      D[y][x-i][1]=1
      if D[y][x-i][0]==0:
        Y.append(y)
        X.append(x-i)
      V[y][x-i]=min(V[y][x-i],V[y][x]+1)
      if i==k:
        D[y][x-i][1]=0
        break
      i=i+1
    i=1
    while G[y][x+i]==".":
      D[y][x+i][1]=1
      if D[y][x+i][0]==0:
        Y.append(y)
        X.append(x+i)
      V[y][x+i]=min(V[y][x+i],V[y][x]+1)
      if i==k:
        D[y][x+i][1]=0
        break
      i=i+1
  if D[y][x][0]==0:
    i=1
    D[y][x][0]=1
    while G[y-i][x]==".":
      D[y-i][x][0]=1
      if D[y-i][x][1]==0:
        Y.append(y-i)
        X.append(x)
      V[y-i][x]=min(V[y-i][x],V[y][x]+1)
      if i==k:
        D[y-i][x][0]=0
        break
      i=i+1
    i=1
    while G[y+i][x]==".":
      D[y+i][x][0]=1
      if D[y+i][x][1]==0:
        Y.append(y+i)
        X.append(x)
      V[y+i][x]=min(V[y+i][x],V[y][x]+1)
      if i==k:
        D[y+1][x][0]=0
        break
      i=i+1
if V[gy][gx]==10**10:
  print(-1)
else:
  print(V[gy][gx])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[10**10]*(w+2) for i in range(h+2)]
V[sy][sx]=0
D=[[[0,0] for j in range(w+2)] for i in range(h+2)]
D[sy][sx]=[1,1]
X=deque([])
Y=deque([])
i=1
while G[sy-i][sx]==".":
  Y.append(sy-i)
  X.append(sx)
  V[sy-i][sx]=1
  D[sy-i][sx][0]=1
  if i==k:
    D[sy-i][sx][0]=0
    break
  i=i+1
i=1
while G[sy+i][sx]==".":
  Y.append(sy+i)
  X.append(sx)
  V[sy+i][sx]=1
  D[sy+i][sx][0]=1
  if i==k:
    D[sy+i][sx][0]=0
    break
  i=i+1

i=1
while G[sy][sx-i]==".":
  Y.append(sy)
  X.append(sx-i)
  V[sy][sx-i]=1
  D[sy][sx-i][1]=1
  if i==k:
    D[sy][sx-i][1]=0
    break
  i=i+1
i=1
while G[sy][sx+i]==".":
  Y.append(sy)
  X.append(sx+i)
  V[sy][sx+i]=1
  D[sy][sx+i][1]=1
  if i==k:
    D[sy][sx-i][1]=0
    break
  i=i+1

while len(X)>0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  if D[y][x]==[0,0]:
    X.append(x)
    Y.append(y)
  if D[y][x]==[1,1]:
    continue
  if D[y][x][1]==0:
    i=1
    D[y][x][1]=1
    while G[y][x-i]==".":
      D[y][x-i][1]=1
      if D[y][x-i][0]==0:
        Y.append(y)
        X.append(x-i)
      V[y][x-i]=min(V[y][x-i],V[y][x]+1)
      if i==k:
        D[y][x-i][1]=0
        break
      i=i+1
    i=1
    while G[y][x+i]==".":
      D[y][x+i][1]=1
      if D[y][x+i][0]==0:
        Y.append(y)
        X.append(x+i)
      V[y][x+i]=min(V[y][x+i],V[y][x]+1)
      if i==k:
        D[y][x+i][1]=0
        break
      i=i+1
  if D[y][x][0]==0:
    i=1
    D[y][x][0]=1
    while G[y-i][x]==".":
      D[y-i][x][0]=1
      if D[y-i][x][1]==0:
        Y.append(y-i)
        X.append(x)
      V[y-i][x]=min(V[y-i][x],V[y][x]+1)
      if i==k:
        D[y-i][x][0]=0
        break
      i=i+1
    i=1
    while G[y+i][x]==".":
      D[y+i][x][0]=1
      if D[y+i][x][1]==0:
        Y.append(y+i)
        X.append(x)
      V[y+i][x]=min(V[y+i][x],V[y][x]+1)
      if i==k:
        D[y+1][x][0]=0
        break
      i=i+1
if V[gy][gx]==10**10:
  print(-1)
else:
  print(V[gy][gx])

Submission status: Wrong Answer

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) in dist:
    continue
  dist[(x, y, v)] = cost
  if (x, y) == (x2, y2):
    print(cost)
    quit()
  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) in dist:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, v])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[10**10]*(w+2) for i in range(h+2)]
V[sy][sx]=0
D=[[[0,0] for j in range(w+2)] for i in range(h+2)]
D[sy][sx]=[1,1]
X=deque([])
Y=deque([])
i=1
while G[sy-i][sx]==".":
  Y.append(sy-i)
  X.append(sx)
  V[sy-i][sx]=1
  D[sy-i][sx][0]=1
  if i==k:
    D[sy-i][sx][0]=0
    break
  i=i+1
i=1
while G[sy+i][sx]==".":
  Y.append(sy+i)
  X.append(sx)
  V[sy+i][sx]=1
  D[sy+i][sx][0]=1
  if i==k:
    D[sy+i][sx][0]=0
    break
  i=i+1

i=1
while G[sy][sx-i]==".":
  Y.append(sy)
  X.append(sx-i)
  V[sy][sx-i]=1
  D[sy][sx-i][1]=1
  if i==k:
    D[sy][sx-i][1]=0
    break
  i=i+1
i=1
while G[sy][sx+i]==".":
  Y.append(sy)
  X.append(sx+i)
  V[sy][sx+i]=1
  D[sy][sx+i][1]=1
  if i==k:
    D[sy][sx-i][1]=0
    break
  i=i+1

while len(X)>0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  if D[y][x]==[0,0]:
    X.append(x)
    Y.append(y)
  if D[y][x]==[1,1]:
    continue
  if D[y][x][1]==0:
    i=1
    D[y][x]=[1,1]
    while G[y][x-i]==".":
      D[y][x-i][1]=1
      if D[y][x-i][0]==0:
        Y.append(y)
        X.append(x-i)
      V[y][x-i]=min(V[y][x-i],V[y][x]+1)
      if i==k:
        D[y][x-i][1]=0
        break
      i=i+1
    i=1
    while G[y][x+i]==".":
      D[y][x+i][1]=1
      if D[y][x+i][0]==0:
        Y.append(y)
        X.append(x+i)
      V[y][x+i]=min(V[y][x+i],V[y][x]+1)
      if i==k:
        D[y][x+i][1]=0
        break
      i=i+1
  if D[y][x][0]==0:
    i=1
    D[y][x]=[1,1]
    while G[y-i][x]==".":
      D[y-i][x][0]=1
      if D[y-i][x][1]==0:
        Y.append(y-i)
        X.append(x)
      V[y-i][x]=min(V[y-i][x],V[y][x]+1)
      if i==k:
        D[y-i][x][0]=0
        break
      i=i+1
    i=1
    while G[y+i][x]==".":
      D[y+i][x][0]=1
      if D[y+i][x][1]==0:
        Y.append(y+i)
        X.append(x)
      V[y+i][x]=min(V[y+i][x],V[y][x]+1)
      if i==k:
        D[y+1][x][0]=0
        break
      i=i+1
if V[gy][gx]==10**10:
  print(-1)
else:
  print(V[gy][gx])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import sqrt
from heapq import heappush, heappop
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    M, N, K = it()
    x1, y1, x2, y2 = it()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    grid = [list(input().strip()) for _ in range(M)]

    ans = INF
    pq = [(0, 0, 0, x1, y1)]
    while pq:
        moves, accum, direc, x, y = heappop(pq)
        assert accum < K
        if x == x2 and y == y2:
            ans = min(ans, moves if accum == 0 else moves + 1)
            continue
        if grid[x][y] == '@':
            continue
        if moves > ans:
            break
        grid[x][y] = '@'
        for x0, y0, d0 in ((x - 1, y, 1), (x + 1, y, 2), (x, y - 1, 3), (x, y + 1, 4)):
            if 0 <= x0 < M and 0 <= y0 < N and grid[x0][y0] != '@':
                new_moves = moves
                new_accum = accum
                if direc == d0 or direc == 0:
                    new_accum += 1
                    if new_accum == K:
                        new_moves += 1
                        new_accum = 0
                else:
                    if new_accum > 0:
                        new_moves += 1
                    new_accum = 1
                    if new_accum == K:
                        new_moves += 1
                    new_accum = 0
                heappush(pq, (new_moves, new_accum, d0, x0, y0))
    return -1 if ans == INF else ans

Submission status: Wrong Answer

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)
for _ in range(H):
	c += "@" + input() + "@"
c += "@" * (W+2)
#c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [INF for _ in range((W+2) * (H+2))]
dist[sh*(W+2)+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*(W+2)+jj] == "@" or dist[ii*(W+2)+jj] <= dist[i*(W+2)+j]:
				break
			if dist[ii*(W+2)+jj] > dist[i*(W+2)+j]:
				dist[ii*(W+2)+jj] = dist[i*(W+2)+j] + 1
				if ii == gh and jj == gw:
					print(dist)
					print(dist[ii*(W+2)+jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

Submission status: Wrong Answer

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


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

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

    return -1


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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import sqrt
from heapq import heappush, heappop
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    M, N, K = it()
    x1, y1, x2, y2 = it()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    grid = [list(input().strip()) for _ in range(M)]

    pq = [(0, 0, 0, 0, x1, y1)]
    while pq:
        _, moves, accum, direc, x, y = heappop(pq)
        if x == x2 and y == y2:
            return moves if accum == 0 else moves + 1
        if grid[x][y] == '@':
            continue
        grid[x][y] = '@'
        for x0, y0, d0 in ((x - 1, y, 1), (x + 1, y, 2), (x, y - 1, 3), (x, y + 1, 4)):
            if 0 <= x0 < M and 0 <= y0 < N and grid[x0][y0] != '@':
                new_moves = moves
                new_accum = accum
                if direc == d0 or direc == 0:
                    new_accum += 1
                    if new_accum == K:
                        new_moves += 1
                        new_accum = 0
                else:
                    if new_accum > 0:
                        new_moves += 1
                    new_accum = 1
                heappush(pq, (new_moves + int(new_accum > 0), new_moves, new_accum, d0, x0, y0))
    return -1
    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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

Solution code:
def LI():return list(map(int,input().split()))
INF=float("inf")
from collections import deque
def main():
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=list(list(input()) for _ in range(h))
    dist=[[INF]*(w) for _ in range(h)]
    q=deque([])
    q.append((x1,y1))
    dist[x1][y1]=0
    while q:
        x,y=q.popleft()
        for vx,vy in ([0,1],[0,-1],[1,0],[-1,0]):
            for kk in range(1,k+1):
                nx=x+kk*vx
                ny=y+kk*vy
                if not(0<=nx<h) or not(0<=ny<w):
                    break
                if maze[nx][ny]=="@":
                    break
                if dist[nx][ny]!=INF:
                    break
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
            
    # for j in dist:print(*j)
    ans=dist[x2][y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import sqrt
from heapq import heappush, heappop
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    M, N, K = it()
    x1, y1, x2, y2 = it()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    grid = [list(input().strip()) for _ in range(M)]

    pq = [(0, 0, 0, x1, y1)]
    while pq:
        moves, accum, direc, x, y = heappop(pq)
        if x == x2 and y == y2:
            return moves if accum == 0 else moves + 1
        if grid[x][y] == '@':
            continue
        grid[x][y] = '@'
        for x0, y0, d0 in ((x - 1, y, 1), (x + 1, y, 2), (x, y - 1, 3), (x, y + 1, 4)):
            if 0 <= x0 < M and 0 <= y0 < N and grid[x0][y0] != '@':
                new_moves = moves
                new_accum = accum
                if direc == d0 or direc == 0:
                    new_accum += 1
                    if new_accum == K:
                        new_moves += 1
                        new_accum = 0
                else:
                    if new_accum > 0:
                        new_moves += 1
                    new_accum = 1
                heappush(pq, (new_moves, new_accum, d0, x0, y0))
    return -1
    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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)
for _ in range(H):
	c += "@" + input() + "@"
c += "@" * (W+2)
#c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [INF for _ in range((W+2) * (H+2))]
dist[sh*(W+2)+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*(W+2)+jj] == "." and dist[ii*(W+2)+jj] > dist[i*(W+2)+j] + 1:
				dist[ii*(W+2)+jj] = dist[i*(W+2)+j] + 1
				if ii == gh and jj == gw:
					print(dist[ii*(W+2)+jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from sys import exit
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
grid=[list(map(lambda x:x=='.',list(input()))) for i in range(h)]
t=[[0]*w for i in range(h)]
t[x1-1][y1-1]=1
t[x2-1][y2-1]=-1
axis=[[1,0],[0,1],[-1,0],[0,-1]]
while True:
  flg_ng=True
  t_tmp=deepcopy(t)
  for x in range(h):
    for y in range(w):
      if t_tmp[x][y]==0: continue
      step=(1 if t_tmp[x][y]>0 else -1)
      for i in range(4):
      	for d in range(1,k+1):
          if not(0<=x+axis[i][0]*d<len(grid)) or not(0<=y+axis[i][1]*d<len(grid[0])): break
          if not grid[x+axis[i][0]*d][y+axis[i][1]*d]: break
          if(t_tmp[x+axis[i][0]*d][y+axis[i][1]*d]==0):
            flg_ng=False
            t[x+axis[i][0]*d][y+axis[i][1]*d]=t_tmp[x][y]+step
          elif(step*t_tmp[x+axis[i][0]*d][y+axis[i][1]*d]<0):
            print(t_tmp)
            print(abs(t_tmp[x][y])+abs(t_tmp[x+axis[i][0]*d][y+axis[i][1]*d])-1)
            exit()
  if flg_ng:
    print(-1)
    exit()

Submission status: Wrong Answer

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