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:
import numpy as np
from collections import deque

H, W, K = list(map(int,input().split()))
x1, y1, x2, y2 = list(map(int, input().split()))
c = [['@' for _ in range(W+2)] for _ in range(H+2)]
for i in range(1,H+1):
    c[i] = ['@'] + list(input()) + ['@']

queue = deque()
queue.append([(x1,y1)])
step = 0
flag = False
while queue:
    currents = queue.popleft()
    if currents == []:
        break
    nexts = []
    for (current_x, current_y) in currents:
        if (current_x, current_y) == (x2, y2):
            flag = True
            break
        c[current_x][current_y] = '@'
        for (d_x, d_y) in [(0,1),(0,-1),(-1,0),(1,0)]:
            c_x, c_y = current_x, current_y
            s = 0
            while s <= K:
                if c[c_x + d_x][c_y + d_y] != '@' and s < K:
                    c_x += d_x
                    c_y += d_y
                    c[c_x][c_y] = '@'
                    nexts.append((c_x,c_y))
                    s += 1
                else:
                    # if s >= 1:
                    #     nexts.append((c_x,c_y))
                    break
    if flag:
        break
    queue.append(nexts)
    step += 1
if flag:
    print(step)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

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

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

# def dfs(x, y, prev_k=-1, dist=0):
#     for k in range(4):
#         nx = x + dx[k]
#         ny = y + dy[k]
#         if 0 <= nx < h and 0 <= ny < w and pond[nx][ny] != "@":
#             if k == prev_k:
#                 dist = dfs()

dist = [[10 ** 8] * w for _ in range(h)]
dist[x1][y1] = 0
q = deque([(x1, y1, -1, 0)])
while q:
    x, y, prev_k, cnt = q.popleft()
    cnt += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < h and 0 <= ny < w and pond[nx][ny] != "@":
            cost = 0
            cnt2 = cnt
            if k != prev_k or cnt2 > K:
                cost = 1
                cnt2 = 1
            if dist[x][y] + cost <= dist[nx][ny]:
                dist[nx][ny] = dist[x][y] + cost
                q.append((nx, ny, k, cnt2))
if dist[x2][y2] == 10 ** 8:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
X=[int(i) for i in input().split()]
C=[]
for i in range(h):
    C.append(list(input()))

que=[(X[0]-1,X[1]-1,0)]
now=0

while now<len(que):
    nx,ny,sc=que[now][0],que[now][1],que[now][2]
    if nx==X[2]-1 and ny==X[3]-1:
        print(sc)
    
    for i in range(k,0,-1):
        if nx+i<h and C[nx+i][ny]==".":
            C[nx+i][ny]="x"
            que.append((nx+i,ny,sc+1))
        else:
            break
        
    for i in range(k,0,-1):
        if nx-i>=0 and C[nx-i][ny]==".":
            C[nx-i][ny]="x"
            que.append((nx-i,ny,sc+1))
        else:
            break
    
    for i in range(k,0,-1):
        if ny+i<w and C[nx][ny+i]==".":
            C[nx][ny+i]="x"
            que.append((nx,ny+i,sc+1))
        else:
            break
    
    for i in range(k,0,-1):
        if ny-i>=0 and C[nx][ny-i]==".":
            C[nx][ny-i]="x"
            que.append((nx,ny-i,sc+1))
        else:
            break
    
    
    now+=1
else:
    print(-1)

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:
  temp = []
  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
        temp.append((y,x))
        flag[y][x][0] = 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
        temp.append((y,x))
        flag[y][x][1] = 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
        temp.append((y,x))
        flag[y][x][2] = 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
        temp.append((y,x))
        flag[y][x][3] = count
      if data[y][x] != ".":
        break
    else:
      break
  if d[y2-1][x2-1]!=INF:
    print(d[y2-1][x2-1])
    exit()
  for t in temp[::-1]:
    q.append(t)
else:
  print(-1)

Submission status: Wrong Answer

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

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

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

from collections import deque

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

            else:
                break

print(d[x2][y2])

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = []
    heappush(que,(0,(x,y)))
    d[x][y] = 0
    while que:
        [num,(qx,qy)] = heappop(que)
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    heappush(que,[abs(nx-gx)+abs(ny-gy),(nx,ny)])
                    if nx == gx and ny == gy:
                        print(d[gx][gy])
                        return
    print(d[gx][gy])


if __name__ == "__main__":
    main()

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] == "@":
      break
    if dp[px+j][py] == -1:
      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] == "@":
      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] == "@":
      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] == "@":
      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])

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import deque
H,W,K = map(int,input().split())
x,y,s,t = map(int,input().split())
M = [input() for _ in range(H)]

def dfs(x,y,s,t):
    que = deque()
    que.append([x,y,"",0,0])
    distance = [[-1 for i in range(W)] for j in range(H)]
    dxdy = [[1,0,"a"],[-1,0,"b"],[0,1,"c"],[0,-1,"d"]]##4方向
 
    distance[x][y] = 0
 
    while que:
        x,y,houkou,onaji,cnt = que.popleft()
        ##print(houkou,onaji,cnt)
        if x == s and y == t:
            return cnt
        flag = True
        for i,j,p in dxdy:
            dx = x + i
            dy = y + j
            if 0 <= dx <= H-1 and 0 <= dy <= W-1 and M[dx][dy] == ".":
                if p == houkou:
                    if onaji <= K-1:
                        que.append([dx,dy,p,onaji+1,cnt])
                    else:
                        que.append([dx,dy,p,0,cnt+1])
                else:
                    que.append([dx,dy,p,0,cnt+1])
        
    return -1


d = dfs(x-1,y-1,s-1,t-1)
print(d)

Submission status: Wrong Answer

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1 and cord[y][x+i] == '.':
                l.append((x+i,y))
            else:
                f1 = False
            if f2 and cord[y][x-i] == '.':
                l.append((x-i,y))
            else:
                f2 = False
            if f3 and cord[y+i][x] == '.':
                l.append((x,y+i))
            else:
                f3 = False
            if f4 and cord[y-i][x] == '.':
                l.append((x,y-i))
            else:
                f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = '#'
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
#        print(ans)
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
print(bfs(xg,yg))

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
P = [input() for _ in range(H)]

queue = deque([[xs, ys]])
visited = [[-1 for i in range(W+1)]for j in range(H+1)]
visited[xs][ys] = 0
while queue:
    x, y = queue.popleft()
    step = 1
    while True:
        new_y, new_x = y+step, x
        if new_y > W:
            break
        elif P[new_x-1][new_y-1] == '@':
            break
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y] = visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
    step = 1
    while True:
        new_y, new_x = y-step, x
        if new_y < 1:
            break
        elif P[new_x-1][new_y-1] == '@':
            break   
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y] = visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
    step = 1
    while True:
        new_y, new_x = y, x+step
        if new_x > H:
            break
        elif P[new_x-1][new_y-1] == '@':
            break
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y]= visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
    step = 1
    while True:
        new_y, new_x= y, x-step
        if new_x < 0:
            break
        elif P[new_x-1][new_y-1] == '@':
            break
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y] = visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break

print(visited[xg][yg]+1)

Submission status: Wrong Answer

Solution code:
import heapq

h, w, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [input() for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

def is_in_range(x, y):
    return 0 <= x < h and 0 <= y < w

def calc_cost(x, y):
    return 0 if gy == y and gx == x else (1 if gy == y or gx == x else 2)

pq = [(0, 0, (sx, sy))]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
visited[sx][sy] = True
heapq.heapify(pq)

def search():
    while len(pq) != 0:
        _, cost, (cx, cy) = heapq.heappop(pq)
        # print(cost, (cx, cy))
        for dx, dy in d:
            for kk in range(1, k + 1):
                nx, ny = cx + dx * kk, cy + dy * kk
                if not is_in_range(nx, ny) or c[nx][ny] == '@' or visited[nx][ny]:
                    break
                # if c[nx][ny] == '@':
                #     break
                # # print((nx, ny))
                # if not visited[nx][ny]:
                visited[nx][ny] = True
                if c[nx][ny] == '.':
                    if ny == gy and nx == gx:
                        return cost + 1
                    heapq.heappush(pq, (calc_cost(nx, ny) + cost + 1, cost + 1, (nx, ny)))

    return -1

print(search())

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]=min(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]=min(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]=min(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]=min(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:
####################################################################
import sys
def p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
H,W,K = map(int, input().split())		# 5 7 2

x1,y1,x2,y2 = map(int, input().split())		# 5 7 2

x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1

M = list( list(input()) for _ in range(H) )
#=> [['.', '.', '.', '.'], ['.', 'S', 'S', '.'], ['.', '.', 'S', '.'], ['.', '.', '.', '.']]

INF = 10**12

for h in range(H):
  for w in range(W):
    c = M[h][w]
    if c == ".": M[h][w] = INF
    if c == "@": M[h][w] = -1

# dXY=[]
# for i in range(1,K+1):
#   dXY.append(( i, 0))
#   dXY.append((-i, 0))
#   dXY.append(( 0, i))
#   dXY.append(( 0,-i))
dXY=[ [0,1], [0,-1], [1,0], [-1,0] ]

from collections import deque
Q = deque()
Q.append( [x1,y1] )
M[x1][y1]=0

while Q:
  x,y = Q.popleft()
  # p("x,y = ", x,y)
  if x==x2 and y==y2: break
  for dx, dy in dXY:

    for k in range(K):
      if dx > 0: dx += k
      if dx < 0: dx -= k
      if dy > 0: dy += k
      if dy < 0: dy -= k
      h = x + dx
      w = y + dy
      if h<0 or H<=h or w<0 or W<=w: continue
      # p("h,w,x,y = ", h,w,x,y)
      # p( "M[h][w]", M[h][w])
      # p( "M[x][y]", M[x][y])
      if M[h][w] == -1: break
      if M[x][y]+1 < M[h][w]:
        M[h][w] = M[x][y]+1
        Q.append( [h,w] )

ans = M[x2][y2]
if ans == INF: ans = -1
print(ans)

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 ** 18 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]])
    stack_append = stack.append
    stack_popleft = stack.popleft
    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 ** 18:
    print(-1)
else:
    print(ans)

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]<=cost+1):
                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:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        oy,ox = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = oy,ox
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0:
                    break
                dist[y][x] = dist[oy][ox] + 1
                q.append((y,x))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()

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:
    if judge==0:
        break
    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 numpy as np
from collections import deque

H, W, K = list(map(int,input().split()))
x1, y1, x2, y2 = list(map(int, input().split()))
c = [['@' for _ in range(W+2)] for _ in range(H+2)]
for i in range(1,H+1):
    c[i] = ['@'] + list(input()) + ['@']

queue = deque()
queue.append([(x1,y1)])
step = 0
flag = False
while queue:
    currents = queue.popleft()
    if currents == []:
        break
    nexts = []
    for (current_x, current_y) in currents:
        if (current_x, current_y) == (x2, y2):
            flag = True
            break
        c[current_x][current_y] = '@'
        for (d_x, d_y) in [(0,1),(0,-1),(-1,0),(1,0)]:
            c_x, c_y = current_x, current_y
            s = 0
            while s <= K:
                if c[c_x + d_x][c_y + d_y] != '@' and s < K:
                    c_x += d_x
                    c_y += d_y
                    c[c_x][c_y] = '@'
                    nexts.append((c_x,c_y))
                    s += 1
                else:
                    if s >= 1:
                        nexts.append((c_x,c_y))
                    break
    if flag:
        break
    queue.append(nexts)
    step += 1
if flag:
    print(step)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
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):
    sub=input().rstrip()
    c.append(sub)
check=[[-1]*w for i in range(h)]
cd=[]
for i in range(h):
    sub=[[False]*4 for j in range(w)]
    cd.append(sub)
from collections import deque
q=[(x1-1,y1-1,0)]
q=deque(q)
d=[(1,0),(-1,0),(0,1),(0,-1)]
check[x1-1][y1-1]=0
while len(q)>0:
    now=q.popleft()
    x=now[0]
    y=now[1]
    for i in range(4):
        cd[x][y][i]=True
        for j in range(1,k+1):
            xn=x+d[i][0]*j
            yn=y+d[i][1]*j
            if 0<=xn<=h-1 and 0<=yn<=w-1:
                if c[xn][yn]=='@':
                    break
                if cd[xn][yn][i]:
                    break
                if check[xn][yn]==-1:
                    check[xn][yn]=now[2]+1
                    q.append((xn,yn,now[2]+1))
                cd[xn][yn][i]=True
            else:
                break
print(check[x2-1][y2-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def dijkstra(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, s)]
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        nc = cost + 1
        for d, ax in MOVE:
            for u in range(v + d, v + d * (k + 1), d):
                if field[u] == '@':
                    break
                if ans[u][ax] <= nc:
                    break
                ans[u][ax] = nc
                heappush(q, (nc, u))
        # print(*((i, divmod(u, w2)) for i, u in q))
        # for i in range(h2):
        #     print(ans[i * w2:(i + 1) * w2])
        # print()
    return -1


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

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@' + row + '@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(dijkstra(field, s, t, k))