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:
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 ** 7

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) or s[i][j + dj] == "@":
                if dj == 1:
                    break
                else:
                    graph[to_ind(i, j)].append(to_ind(i, j + dj - 1))
                    graph[to_ind(i, j + dj - 1)].append(to_ind(i, j))
                    break
        else:
            graph[to_ind(i, j)].append(to_ind(i, j + k))
            graph[to_ind(i, j + k)].append(to_ind(i, j))

        for di in range(1, k + 1):
            if not(0 <= i + di < h) or s[i + di][j] == "@":
                if di == 1:
                    break
                else:
                    graph[to_ind(i, j)].append(to_ind(i + di - 1, j))
                    graph[to_ind(i + di - 1, j)].append(to_ind(i, j))
                    break
        else:
            graph[to_ind(i, j)].append(to_ind(i + k, j))
            graph[to_ind(i + k, 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), -1)])
l, r, u, d = 0, 1, 2, 3

while q:
    v, dire = q.popleft()
    i, j = divmod(v, w)

    if dire == l:
        if not(0 <= j - 1 < w):
            continue
        nxt_v = v - 1
        if visited[v] < visited[nxt_v]:
            visited[nxt_v] = visited[v]
            q.appendleft((nxt_v, l))
    elif dire == r:
        if not(0 <= j + 1 < w):
            continue
        nxt_v = v + 1
        if visited[v] < visited[nxt_v]:
            visited[nxt_v] = visited[v]
            q.appendleft((nxt_v, r))
    elif dire == u:
        if not(0 <= i - 1 < h):
            continue
        nxt_v = v - w
        if visited[v] < visited[nxt_v]:
            visited[nxt_v] = visited[v]
            q.appendleft((nxt_v, u))
    elif dire == d:
        if not(0 <= i + 1 < h):
            continue
        nxt_v = v + w
        if visited[v] < visited[nxt_v]:
            visited[nxt_v] = visited[v]
            q.appendleft((nxt_v, d))

    for nxt_v in graph[v]:
        if visited[nxt_v] <= visited[v] + 1:
            continue
        visited[nxt_v] = visited[v] + 1
        nxt_i, nxt_j = divmod(nxt_v, w)
        if nxt_i == i and nxt_j < j:
            q.append((nxt_v, r))
        if nxt_i == i and nxt_j > j:
            q.append((nxt_v, l))
        if nxt_i < i and nxt_j == j:
            q.append((nxt_v, d))
        if nxt_i > i and nxt_j == j:
            q.append((nxt_v, u))

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
from functools import lru_cache
h,w,k = map(int,input().split())
k = min(k,500)
sy,sx,gy,gx = map(int,input().split())
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx,-1))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6+1):
    next = deque()
    while now:
        y,x,status = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        if status != 0 or (y>0 and map[y-1][x] != "@"):
            for i in range(1,k+1):
                if y-i < 0 or map[y-i][x] == "@":
                    break
                else:
                    if gone[y-i][x] == 0:
                        gone[y-i][x] = 1
                        next.append((y-i,x,0))
        if status != 1 or (y<h-1 and map[y+1][x] != "@"):
            for i in range(1,k+1):
                if y +i >= h or map[y+i][x] == "@":
                    break
                else:
                    if gone[y + i][x] == 0:
                        gone[y + i][x] = 1
                        next.append((y+i,x,1))
        if status != 2 or (x>0 and map[y][x-1] != "@"):
            for i in range(1,k+1):
                if x - i < 0 or map[y][x-i] == "@":
                    break
                else:
                    if gone[y][x-i] == 0:
                        gone[y][x-i] = 1
                        next.append((y,x-i,2))
        if status != 3 or (x<w-1 and map[y][x+1] != "@"):
            for i in range(1, k + 1):
                if x+i >= w or map[y][x+i] == "@":
                    break
                else:
                    if gone[y][x+i] == 0:
                        gone[y][x+i] = 1
                        next.append((y,x+i,3))
    if next == deque():
        print(-1)
        exit()
    now = next

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]!=INF):
                break
            costgrid[nx][ny]=min(costgrid[nx][ny],cost+1)
            heapq.heappush(q,(cost+1,nx,ny))
            if nx==gx and ny==gy:
                ans=min(costgrid[nx][ny],ans)
                q=[]

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

Submission status: Wrong Answer

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

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

c = []
for i in range(h):
    c.append(input().rstrip("\n"))

dist = [[10 ** 9 for i in range(w)] for j in range(h)]

def bfs(cx, cy, x, y, cost, cnt):
    stack = deque([[cx, cy, x, y, cost, cnt]])
    while stack:
        cx, cy, x, y, cost, cnt = stack.popleft()
        if dist[x][y] > cost:
            dist[x][y] = cost
            for vx, vy in ((0,1), (0,-1), (-1,0), (1,0)):
                nx, ny = x + vx, y + vy
                if 0 <= nx and nx < h and 0 <= ny and ny < w:
                    if nx == cx and ny == cy:
                        continue
                    if c[nx][ny] == "@":
                        continue
                    if x - cx == vx and y - cy == vy and cnt < k-1:
                        stack.append([x, y, nx, ny, cost, cnt+1])
                    else:
                        stack.append([x, y, nx, ny, cost+1, 0])

bfs(-2, -2, x1-1, y1-1, 0, 0)
# print(dist)

ans = dist[x2-1][y2-1]

if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from functools import lru_cache
h,w,k = map(int,input().split())
k = min(k,10**2)
sy,sx,gy,gx = map(int,input().split())
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx,-1))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6+1):
    next = deque()
    while now:
        y,x,status = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        if status != 0 or (y>0 and map[y-1][x] != "@"):
            for i in range(1,k+1):
                if y-i < 0 or map[y-i][x] == "@":
                    break
                else:
                    if gone[y-i][x] == 0:
                        gone[y-i][x] = 1
                        next.append((y-i,x,0))
        if status != 1 or (y<h-1 and map[y+1][x] != "@"):
            for i in range(1,k+1):
                if y +i >= h or map[y+i][x] == "@":
                    break
                else:
                    if gone[y + i][x] == 0:
                        gone[y + i][x] = 1
                        next.append((y+i,x,1))
        if status != 2 or (x>0 and map[y][x-1] != "@"):
            for i in range(1,k+1):
                if x - i < 0 or map[y][x-i] == "@":
                    break
                else:
                    if gone[y][x-i] == 0:
                        gone[y][x-i] = 1
                        next.append((y,x-i,2))
        if status != 3 or (x<w-1 and map[y][x+1] != "@"):
            for i in range(1, k + 1):
                if x+i >= w or map[y][x+i] == "@":
                    break
                else:
                    if gone[y][x+i] == 0:
                        gone[y][x+i] = 1
                        next.append((y,x+i,3))
    if next == deque():
        print(-1)
        exit()
    now = next

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
                      
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

def dfs(x,y,kk,d,a):
  #print(kk,d)
  if c[x][y] == '.':
    c[x][y] = a
  else:
    c[x][y] = min(c[x][y],a)
  for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
    if 0 <= x+dx < h and 0 <= y+dy < w and (c[x+dx][y+dy] == '.' or (c[x+dx][y+dy] != '@' and c[x+dx][y+dy] > a)):
      if kk == -1:
        kk = k-1
        a = 1
      elif kk == 0 or d != (dx,dy):
        kk = k
        a += 1
      else:
        kk -= 1
      dfs(x+dx,y+dy,kk,(dx,dy),a)

q = [(x1-1,y1-1,-1,(),0)]
while(q):
  qq = []
  for x,y,kk,d,a in q:
    #print(x,y,c[x][y])
    if c[x][y] == '.':
      c[x][y] = a
    else:
      c[x][y] = min(c[x][y],a)
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
      if 0 <= x+dx < h and 0 <= y+dy < w and c[x+dx][y+dy] == '.':
        if kk == -1:
          kk = k-1
          a = 1
        elif kk == 0 or d != (dx,dy):
          kk = k-1
          a += 1
        else:
          kk -= 1
        qq.append((x+dx,y+dy,kk,(dx,dy),a))
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)

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 = [[-1]*W for i in range(H)]
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 dist[x][y] >= 0:
    continue
  dist[x][y] = 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 dist[xx][yy] >= 0:
        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:
# F - Pond Skater
from collections import deque
INF = 10**10
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = [[] for _ in range(H+1)]
d = [[-1]*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    c[i] = '.' + input()
d[x1][y1] = 0
que = deque([[x1,y1]])
ans = -1
judge = 1
while len(que)>0:
    x,y = que.popleft()
    for k in range(1,INF):
        i = x-k
        if judge==0 or i<1 or c[i][y]!='.':
            break
        if d[i][y]<0:
            d[i][y] = d[x][y]+(k-1)//K+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
    for k in range(1,INF):
        i = x+k
        if judge==0 or i>H or c[i][y]!='.':
            break
        if d[i][y]<0:
            d[i][y] = d[x][y]+(k-1)//K+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
    for k in range(1,INF):
        j = y-k
        if judge==0 or j<1 or c[x][j]!='.':
            break
        if d[x][j]<0:
            d[x][j] = d[x][y]+(k-1)//K+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
    for k in range(1,INF):
        j = y+k
        if judge==0 or j>W or c[x][j]!='.':
            break
        if d[x][j]<0:
            d[x][j] = d[x][y]+(k-1)//K+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
print(ans)

Submission status: Wrong Answer

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

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


#11-


h,w,k = list(map(int, input().split()))

y1,x1,y2,x2 = list(map(int, input().split()))
x1-=1
y1-=1
x2-=1
y2-=1

mapa = []
visited = [[[0,0] for j in range(w)] for i in range(h)]
visited[y1][x1] = [1,1]

for i in range(h):
    mapa.append( input() )

#
queue = [[y1,x1,0]]
done = 0

while(True):
    if(len(queue)==done):
        break
    now = queue[done]
    # move-y
    for i in range(1,min(k+1,h-now[0])):
        seey,seex = now[0]+i,now[1]
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][0]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][0]=1
        else:
            break
    for i in range(1,min(k+1,now[0]+1)):
        seey,seex = now[0]-i,now[1]
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][0]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][0]=1
        else:
            break
    # move-x
    for i in range(1,min(k+1,w-now[1])):
        seey,seex = now[0],now[1]+i
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][1]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][1]=1
        else:
            break
    for i in range(1,min(k+1,now[1]+1)):
        seey,seex = now[0],now[1]-i
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][1]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][1]=1
        else:
            break
    done+=1

print(-1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

dd = [(1,0),(-1,0),(0,1),(0,-1)]
f = [1,0,3,2,None]
def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    D = [(k,0),(-k,0),(0,k),(0,-k)]
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x,-1,0)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    ri = [[0]*w for i in range(h)]
    le = [[0]*w for i in range(h)]
    do = [[0]*w for i in range(h)]
    up = [[0]*w for i in range(h)]

    for i in range(h):
        ri[i][-1] = 0
        for j in range(w-1)[::-1]:
            if c[i][j+1] == "@":
                ri[i][j] = 0
            else:
                l = ri[i][j+1]
                if l < k:
                    ri[i][j] = l+1
                else:
                    ri[i][j] = k
    for i in range(h):
        le[i][0] = 0
        for j in range(1,w):
            if c[i][j-1] == "@":
                le[i][j] = 0
            else:
                l = le[i][j-1]
                if l < k:
                    le[i][j] = l+1
                else:
                    le[i][j] = k

    for j in range(w):
        do[-1][j] = 0
        for i in range(h-1)[::-1]:
            if c[i+1][j] == "@":
                do[i][j] = 0
            else:
                l = do[i+1][j]
                if l < k:
                    do[i][j] = l+1
                else:
                    do[i][j] = k
    for j in range(w):
        up[0][j] = 0
        for i in range(1,h):
            if c[i-1][j] == "@":
                up[i][j] = 0
            else:
                l = up[i-1][j]
                if l < k:
                    up[i][j] = l+1
                else:
                    up[i][j] = k
    while q:
        y,x,p,l = q.popleft()
        nd = d[y][x] + 1
        for i in range(4):
            if f[i] == p:
                continue
            if i == 0:
                dy,dx = -up[y][x],0
            elif i == 1:
                dy,dx = do[y][x],0
            elif i == 2:
                dy,dx = 0,-le[y][x]
            else:
                dy,dx = 0,ri[y][x]
            ny,nx = y+dy,x+dx
            if (y,x) == (ny,nx):
                continue
            if nd < d[ny][nx]:
                diff = abs(ny-y)+abs(nx-x)
                d[ny][nx] = nd
                q.append((ny,nx,i,diff))
        if p >= 0 and l > 1:
            dy,dx = dd[p]
            ny,nx = y+dy,x+dx
            nd = d[y][x]
            if nd < d[ny][nx]:
                d[ny][nx] = nd
                q.appendleft((ny,nx,p,l-1))
    ans = d[s][t]
    if ans < float("inf"):
        print(ans)
    else:
        print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

dd = [(1,0),(-1,0),(0,1),(0,-1)]
f = [1,0,3,2]
def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    D = [(k,0),(-k,0),(0,k),(0,-k)]
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x,-1,0)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    ri = [[0]*w for i in range(h)]
    le = [[0]*w for i in range(h)]
    do = [[0]*w for i in range(h)]
    up = [[0]*w for i in range(h)]

    for i in range(h):
        ri[i][-1] = 0
        for j in range(w-1)[::-1]:
            if c[i][j+1] == "@":
                ri[i][j] = 0
            else:
                l = ri[i][j+1]
                if l < k:
                    ri[i][j] = l+1
                else:
                    ri[i][j] = k
    for i in range(h):
        le[i][0] = 0
        for j in range(1,w):
            if c[i][j-1] == "@":
                le[i][j] = 0
            else:
                l = le[i][j-1]
                if l < k:
                    le[i][j] = l+1
                else:
                    le[i][j] = k

    for j in range(w):
        do[-1][j] = 0
        for i in range(h-1)[::-1]:
            if c[i+1][j] == "@":
                do[i][j] = 0
            else:
                l = do[i+1][j]
                if l < k:
                    do[i][j] = l+1
                else:
                    do[i][j] = k
    for j in range(w):
        up[0][j] = 0
        for i in range(1,h):
            if c[i-1][j] == "@":
                up[i][j] = 0
            else:
                l = up[i-1][j]
                if l < k:
                    up[i][j] = l+1
                else:
                    up[i][j] = k
    while q:
        y,x,p,l = q.popleft()
        nd = d[y][x] + 1
        for i in range(4):
            if f[i] == p:
                continue
            if i == 0:
                dy,dx = -up[y][x],0
            elif i == 1:
                dy,dx = do[y][x],0
            elif i == 2:
                dy,dx = 0,-le[y][x]
            else:
                dy,dx = 0,ri[y][x]
            ny,nx = y+dy,x+dx
            if (y,x) == (ny,nx):
                continue
            if nd < d[ny][nx]:
                diff = abs(ny-y)+abs(nx-x)
                d[ny][nx] = nd
                q.append((ny,nx,i,diff))
        if p >= 0 and l > 1:
            dy,dx = dd[p]
            ny,nx = y+dy,x+dx
            nd = d[y][x]
            if nd < d[ny][nx]:
                d[ny][nx] = nd
                q.appendleft((ny,nx,p,l-1))
    ans = d[s][t]
    if ans < float("inf"):
        print(ans)
    else:
        print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
h,w,k=map(int,input().split())
r=[1, 0, 0, -1] 
c=[0, -1, 1, 0] 
x1,y1,x2,y2=map(int,input().split())
vis=[[False for i in range(w)] for j in range(h)]
arr=[]
for i in range(h):
    ff=list(input())
    arr.append(ff)
f=0
q=deque()
q.append([x1-1,y1-1,0])
vis[x1-1][y1-1]=True
while(len(q)>0):
    curr=q.popleft()
    if curr[0]==x2-1 and curr[1]==y2-1:
        f=curr[2]+2
        break
    for i in range(4):
        row=curr[0]+r[i]
        col=curr[1]+c[i]
        if row<=h-1 and row>=0 and col>=0 and col<=w-1 and arr[row][col]=='.' and not vis[row][col]:
                vis[row][col]=True
                b=[row,col,curr[2]+1]
                q.append(b)
if f==0:
    print(-1)
else:
    if f%2==1:
        print(math.ceil(f/k))
    else:print((f//k)-1)

Submission status: Wrong Answer

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

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

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

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

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