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 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,"n"))
  checked=[[0]*w for _ in range(h)]
  checked[sy][sx]=1
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  while len(q)!=0:
    x,y,d=q.popleft()
    c=cost[y][x]
    for i in range(1,k+1):
      if x+i<w and 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)
        if d=="r":
          q.appendleft((x+i,y,"r"))
        else:
          q.append((x+i,y,"r"))
      else:
        break
    for i in range(1,k+1):
      if x-i>=0 and 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)        
        if d=="l":
          q.appendleft((x-i,y,"l"))
        else:
          q.append((x-i,y,"l"))
      else:
        break
    for i in range(1,k+1):
      if y+i<h and 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)        
        if d=="d":
          q.appendleft((x,y+i,"d"))
        else:
          q.append((x,y+i,"d"))
      else:
        break
    for i in range(1,k+1):
      if y-i>=0 and 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)        
        if d=="u":
          q.appendleft((x,y-i,"u"))
        else:
          q.append((x,y-i,"u"))
      else:
        break
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

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 for i in range(W)] for j in range(H)]

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

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
while q:
  y,x = q.popleft()
  for i in range(K):
    ny,nx = y+dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y-dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y,x+dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
  for i in range(K):
    ny,nx = y,x-dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
        else:
          break
      else:
        break
        
if d[y2-1][x2-1]!=INF:
  print(d[y2-1][x2-1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
y1,x1,gy,gx = map(int,input().split())
m = ["@"*(w+2)]+["@"+input()+"@" for i in range(h)]+["@"*(w+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq=deque([(y1,x1)])
ans = 0
temp = [[-1]*(w+2) for i in range(h+2)]
temp[y1][x1] = 0
cnt = 0
while dq:
    # cnt += 1
    # print(cnt)
    y,x = dq.popleft()
    # print(dq,y,x)
    for j in opt:
        y1 = y+j[0]
        x1 = x+j[1]
        if m[y1][x1] == "@":
            # print(y1,x1,"@@")
            continue
        if temp[y1][x1] == -1 or temp[y1][x1]-temp[y][x]>1:
            for i in range(k):
                if (temp[y1+i*j[0]][x1+i*j[1]] == -1 or temp[y1+i*j[0]][x1+i*j[1]]-temp[y][x]>0) and m[y1+i*j[0]][x1+i*j[1]] == ".":
                    if temp[y1+i*j[0]][x1+i*j[1]]-temp[y][x]==1:
                        continue
                    temp[y1+i*j[0]][x1+i*j[1]] = temp[y][x]+1
                    dq.append((y1+i*j[0],x1+i*j[1]))
                    # print(y1+i*j[0],x1+i*j[1],"a",k,m[y1+i*j[0]][x1+i*j[1]],temp[y1+i*j[0]][x1+i*j[1]])
                else:
                    # print(y1+i*j[0],x1+i*j[1],"b",k,m[y1+i*j[0]][x1+i*j[1]],temp[y1+i*j[0]][x1+i*j[1]])
                    break
# for i in temp:
#     print(i)
# print(temp)
print(temp[gy][gx])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def BFS(H, W, L, start, K):
	dist = [[INF for i in range(W + 2)] for j in range(H + 2)]
	sy, sx, h, w = start; dist[sy][sx] = 0
	Q = deque(); Q.append([sy, sx, h, w])
	while Q:
		y, x, h, w = Q.popleft()
		if L[y - 1][x] == ".":
			if h == 0:
				if dist[y - 1][x] >= dist[y][x] + 1:
					dist[y - 1][x] = dist[y][x] + 1
					Q.append([y - 1, x, K - 1, 0])
			else:
				if dist[y - 1][x] > dist[y][x]:
					dist[y - 1][x] = dist[y][x]
					Q.appendleft([y - 1, x, h - 1, 0])

		if L[y + 1][x] == ".":
			if h == 0:
				if dist[y + 1][x] >= dist[y][x] + 1:
					dist[y + 1][x] = dist[y][x] + 1
					Q.append([y + 1, x, K - 1, 0])
			else:
				if dist[y + 1][x] > dist[y][x]:
					dist[y + 1][x] = dist[y][x]
					Q.appendleft([y + 1, x, h - 1, 0])

		if L[y][x - 1] == ".":
			if w == 0:
				if dist[y][x - 1] >= dist[y][x] + 1:
					dist[y][x - 1] = dist[y][x] + 1
					Q.append([y, x - 1, 0, K - 1])
			else:
				if dist[y][x - 1] > dist[y][x]:
					dist[y][x - 1] = dist[y][x]
					Q.appendleft([y, x - 1, 0, w - 1])

		if L[y][x + 1] == ".":
			if w == 0:
				if dist[y][x + 1] >= dist[y][x] + 1:
					dist[y][x + 1] = dist[y][x] + 1
					Q.append([y, x + 1, 0, K - 1])
			else:
				if dist[y][x + 1] > dist[y][x]:
					dist[y][x + 1] = dist[y][x]
					Q.appendleft([y, x + 1, 0, w - 1])

	return dist

#処理内容
def main():
	H, W, K = getlist()
	y1, x1, y2, x2 = getlist()
	L = []
	L.append(["@"] * (W + 2))
	for i in range(H):
		l = list(input())
		L.append(["@"] + l + ["@"])
	L.append(["@"] * (W + 2))

	#node = [y, x, h, w]
	start = [y1, x1, 0, 0]
	BF = BFS(H, W, L, start, K)
	ans = BF[y2][x2]
	# for i in range(H + 2):
	# 	print(BF[i])
	if ans == INF:
		print(-1)
	else:
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

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
            if(visited[seey][seex][1]==1):
                break
        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
            if(visited[seey][seex][1]==1):
                break
        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
            if(visited[seey][seex][0]==1):
                break
        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
            if(visited[seey][seex][0]==1):
                break
        else:
            break
    done+=1

print(-1)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,cn,k):
    nx=[]

    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            C[x][y+i]=str(cn+1)
            nx.append([x,y+i])
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            C[x][y-i]=str(cn+1)
            nx.append([x,y-i])
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            C[x+i][y]=str(cn+1)
            nx.append([x+i,y])
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            C[x-i][y]=str(cn+1)
            nx.append([x-i,y])
            i+=1

    return nx

C[x1-1][y1-1]=str(0)
taisho=keiro(x1-1,y1-1,0,K)
result=1

while C[x2-1][y2-1]=='.':
    next_taisho=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        m=keiro(l[0],l[1],result,K)

        for n in m:
            next_taisho.append(n)
    result+=1
    taisho=next_taisho.copy()

print(result)

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            for k in range(1, K+1):
                h2 = h + dh*k
                w2 = w + dw*k
                if grid[h2][w2] == '@':
                    break
                if dist[h2][w2] <= dist[h][w] + 1:
                    break
                dist[h2][w2] = dist[h][w] + 1
                que.append((h2, w2))
    return dist

H, W, K = MAP()
x1, y1, x2, y2 = MAP()
grid = build_grid(H, W, '@', str, space=0, padding=1)

res = bfs(grid, [(x1, y1)])
ans = res[x2][y2]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

Submission status: 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
OFFSET = 10 ** 7

visited = [[INF] * w for i in range(h)]
x1 -= 1
y1 -= 1
visited[x1][y1] = 0
q = deque([(x1, y1, -1, 0)])
l, r, u, d = 0, 1, 2, 3
while q:
    i, j, dire, cnt = q.popleft()

    nxt_i, nxt_j = i + 1, j
    if not(0 <= nxt_i < h) or s[nxt_i][nxt_j] == "@":
        pass
    else:
        if dire == d and cnt < k and visited[i][j] <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j]
            q.appendleft((nxt_i, nxt_j, dire, cnt + 1))
        elif visited[i][j] + 1 <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j] + 1
            q.append((nxt_i, nxt_j, d, 1))
 
    nxt_i, nxt_j = i - 1, j
    if not(0 <= nxt_i < h) or s[nxt_i][nxt_j] == "@":
        pass
    else:
        if dire == u and cnt < k and visited[i][j] <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j]
            q.appendleft((nxt_i, nxt_j, dire, cnt + 1))
        elif visited[i][j] + 1 <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j] + 1
            q.append((nxt_i, nxt_j, u, 1))

    nxt_i, nxt_j = i, j + 1
    if not(0 <= nxt_j < w) or s[nxt_i][nxt_j] == "@":
        pass
    else:
        if dire == r and cnt < k and visited[i][j] <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j]
            q.appendleft((nxt_i, nxt_j, dire, cnt + 1))
        elif visited[i][j] + 1 <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j] + 1
            q.append((nxt_i, nxt_j, r, 1))   
            
    nxt_i, nxt_j = i, j - 1
    if not(0 <= nxt_j < w) or s[nxt_i][nxt_j] == "@":
        pass
    else:
        if dire == l and cnt < k and visited[i][j] <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j]
            q.appendleft((nxt_i, nxt_j, dire, cnt + 1))
        elif visited[i][j] + 1 <= visited[nxt_i][nxt_j]:
            visited[nxt_i][nxt_j] = visited[i][j] + 1
            q.append((nxt_i, nxt_j, l, 1))   
   
if visited[x2 - 1][y2 - 1] == INF:
    print(-1)
else:
    print(visited[x2 - 1][y2 - 1])

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 0 <= D[y] < D[x]: 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 0 <= D[y] < D[x]: 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:
import sys
from collections import deque

input = sys.stdin.readline


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


def main():
    h, w, k = map(int, input().strip().split())
    x1, y1, x2, y2 = map(int, input().strip().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    m = []
    costs1 = [[None for j in range(w)] for i in range(h)]
    costs2 = [[None for j in range(w)] for i in range(h)]
    for _ in range(h):
        m.append(list(input().strip()))
    q1 = deque()
    q1.append((x1, y1, 0))
    costs1[x1][y1] = 0
    q2 = deque()
    q2.append((x2, y2, 0))
    costs2[x2][y2] = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q1 and q2:
        (x, y, cost) = q1.popleft()
        if not costs2[x][y] is None:
            print(cost + costs2[x][y])
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@':
                    break
                if costs1[new_x][new_y] is None:
                    costs1[new_x][new_y] = cost + 1
                    q1.append((new_x, new_y, cost + 1))
        (x, y, cost) = q2.popleft()
        if not costs1[x][y] is None:
            print(cost + costs1[x][y])
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@':
                    break
                if costs2[new_x][new_y] is None:
                    costs2[new_x][new_y] = cost + 1
                    q2.append((new_x, new_y, cost + 1))
    print("-1")


if __name__ == '__main__':
    main()