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 sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w, k = MAP()
sx, sy, gx, gy = MAP()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [STR() for _ in range(h)]
marked = [[inf for _ in range(w)] for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
que = deque([[gx, gy, 0]])
while que:
    x, y, num = que.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if ny < 0 or w <= ny or nx < 0 or h <= nx:
            continue
        if arr[nx][ny] == inf:
            arr[nx][ny] = num + 1
            que.append([nx, ny, num + 1])
marked[sx][sy] = 0
que = [[sx, sy, -1, 0, 0]]
while que:
    x, y, l_mov, cnt, num = que.pop()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if ny < 0 or w <= ny or nx < 0 or h <= nx:
            continue
        if c[nx][ny] == '@':
            continue
        n_num = num
        n_cnt = cnt
        if l_mov == i and cnt < k:
            n_cnt += 1
        else:
            n_num += 1
            n_cnt = 1
        if marked[nx][ny] >= n_num:
            marked[nx][ny] = n_num
            if nx == gx and ny == gy:
                continue
            if n_num + arr[nx][ny] > marked[gx][gy]:
                continue
            que.append([nx, ny, i, n_cnt, n_num])
#for i in marked:
#    print(i)
ans = marked[gx][gy]
print(ans if ans != inf else -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:
  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
      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
      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
      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
      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:
#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)
        while True:
          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)

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

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-1,y1-1] )
M[x1-1][y1-1]=0

while Q:
  x,y = Q.popleft()
  # p("x,y = ", x,y)
  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-1][y2-1]
if ans == INF: ans = -1
print(ans)

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):
        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:
#!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)]

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 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:
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 = 1001001001001001  
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=-1
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]=cost+1
            heapq.heappush(q,(cost+1,nx,ny))
            if nx==gx and ny==gy:
                ans=costgrid[nx][ny]
                q=[]

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import namedtuple, deque, defaultdict
Edge = namedtuple('Edge', 'to cost')
# State = namedtuple('State', 'cost node')
# Node = namedtuple('Node', 'x y d k')
D = tuple(zip((1, 0, -1, 0), (0, 1, 0, -1)))

def solve(H, W, K, sx, sy, ex, ey, C):
    # print(*C,sep="\n")
    q = deque([(0, (sx, sy, -1, 0))])
    # min_costs = defaultdict(lambda: float("inf"))
    visited = set()
    while q:
        s = q.popleft()
        #print(s)
        node = s[1]
        if (node[0], node[1], node[2]) in visited:
            continue
        if node[0] == ex and node[1] == ey:
            return s[0]
        visited.add((node[0], node[1], node[2]))
        for d, (dx, dy) in enumerate(D):
            next_node = (node[0]+dx, node[1]+dy, d, 1 if d != node[2] else node[3] % K + 1)
            if (next_node[0], next_node[1], next_node[2]) in visited:
                continue
            if C[next_node[0]][next_node[1]] == "@":
                continue
            if d == node[2]:
                if next_node[3] != 1:
                    q.appendleft((s[0], next_node))
                else:
                    q.append((s[0]+1, next_node))
            else:
                q.append((s[0]+1, next_node))
    return -1

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W, K = map(int, input().split())
    sx, sy, ex, ey = map(int, input().split())
    C = ["@" * (W+2)]
    C.extend(["@" + input() + "@" for _ in range(H)])
    C.append("@" * (W+2))
    print(solve(H, W, K, sx, sy, ex, ey, C))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

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

grid = [None] * H
for i in range(H):
  grid[i] = readline().rstrip()
  
# 操作としてあり得るのは、
# ・1かきでKマス進む or @の直前まで進む
# ・1かきでKマス未満進んで方向転換する
# 
# ・前回水をかいてから何マス進んでいるか
# ・前回水をかいて、どのむき(U,D,L,R)に進んでいるか
#  (来たところに戻ることはあり得ないので)
# ・今までに何回水をかいたか
# ・今どこにいるか
# 水かき回数でダイクストラ
# たとえ泳ぐ向きが違っても同じ場所を2回通ることはあり得ない。

import numpy as np
# from numba import njit,i8
from collections import defaultdict

import heapq
# 今まで何回水をかいたか,i,j,前回水をかいてから何マス進んでいるか,どのむきに進んでいるか
def solve():
  def get_turn(d):
    if d in ("U","D"): # 縦方向に進んでいた場合の次の進み先
      return ((0,1,"R"),(0,-1,"L"))
    else:
      return ((1,0,"D"),(-1,0,"U"))
  
  def get_straight(d):
    if d == "U":
      return (-1,0,"U")
    if d == "D":
      return (1,0,"D")
    if d == "L":
      return (0,-1,"L")
    if d == "R":
      return (0,1,"R")
  q = []
  heapq.heapify(q)
  # 最初に進む4方向を入れておく
  seen = defaultdict(int)
  for first in "UDLR":
    c = get_straight(first)
    if 0 <= x1 + c[0] < H and 0 <= y1 + c[1] < W:
      if grid[x1 + c[0]][y1 + c[1]] != "@":
        heapq.heappush(q,(1,x1 + c[0],y1 + c[1],1,c[2]))
  seen[(x1,y1)] 
  while q:
    cost,i,j,swim,dire = heapq.heappop(q)
    #print("cost",cost,"i",i,"j",j,"swim",swim,"dire",dire)
    #print(q)
    if (i,j) in seen and seen[(i,j)] <= cost:
      continue
    if i == x2 and j == y2:
      return cost
    seen[(i,j)] = cost
    # 曲がる場合
    cases = get_turn(dire)
    for c in cases:
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
    # 直進する場合
    c = get_straight(dire)
    if swim < K: # まだKマス進んでいない
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えず、swim距離は増える
          heapq.heappush(q,(cost,i + c[0],j + c[1],swim + 1,c[2]))
    elif swim == K: # すでにKマス進んでいる場合
      # 直進する場合
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えて、swim距離は1に
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
  else:
    return -1
print(solve())

Submission status: Wrong Answer

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


def main():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    S = [[False]*W for _ in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                S[i][j] = True

    cost = [[-1]*W for _ in range(H)]

    # 深さ優先探索
    def bfs(x, y):
        stack = deque([[x, y]])
        cost[x][y] = 0
        while stack:
            x, y = stack[0]
            point = cost[x][y] + 1
            # up
            for i in range(1, K+1):
                if x-i >= 0:
                    if S[x-i][y] and cost[x-i][y] == -1:
                        cost[x-i][y] = point
                        stack.append([x-i, y])
                    elif S[x-i][y]:
                        break
                else:
                    break
            # down
            for i in range(1, K+1):
                if x+i < H:
                    if S[x+i][y] and cost[x+i][y] == -1:
                        cost[x+i][y] = point
                        stack.append([x+i, y])
                    elif S[x+i][y]:
                        break
                else:
                    break
            # left
            for i in range(1, K+1):
                if y-i >= 0:
                    if S[x][y-i] and cost[x][y-i] == -1:
                        cost[x][y-i] = point
                        stack.append([x, y-i])
                    elif S[x][y-i]:
                        break
                else:
                    break
            # right
            for i in range(1, K+1):
                if y+i < W:
                    if S[x][y+i] and cost[x][y+i] == -1:
                        cost[x][y+i] = point
                        stack.append([x, y+i])
                    elif S[x][y+i]:
                        break
                else:
                    break

            stack.popleft()        

    bfs(sx-1, sy-1)
    print(cost[gx-1][gy-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# F - Pond Skater
from collections import deque
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()
    i = x-1
    while judge>0 and i>=max(1,x-K) and c[i][y]=='.':
        if d[i][y]<0:
            d[i][y] = d[x][y]+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
        i -= 1
    i = x+1
    while judge>0 and i<=min(H,x+K) and c[i][y]=='.':
        if d[i][y]<0:
            d[i][y] = d[x][y]+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
        i += 1
    j = y-1
    while judge>0 and j>=max(1,y-K) and c[x][j]=='.':
        if d[x][j]<0:
            d[x][j] = d[x][y]+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
        j -= 1
    j = y+1
    while judge>0 and j<=min(W,y+K) and c[x][j]=='.':
        if d[x][j]<0:
            d[x][j] = d[x][y]+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
        j += 1
print(ans)
print(d)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    l = []
    v = [[0] * W for _ in range(H)]
    n = [[0] * W for _ in range(H)]
    s = [[0] * W for _ in range(H)]
    w = [[0] * W for _ in range(H)]
    e = [[0] * W for _ in range(H)]
    v[x1-1][y1-1] = 1
    for _ in range(H):
        c = input()
        l.append([0 if i == '.' else 1 for i in list(c)])
    cur = [(x1-1, y1-1)]
    r = 0
    while cur:
        r += 1
        nex = set()
        for x, y in cur:
            # north
            i = 1
            while x-i > -1 and i <= K:
                a, b = x-i, y
                if a == x2-1 and b == y2-1:
                    return r
                if n[a][b] == 1:
                    break
                if l[x-i][y] == 0:
                    if v[x-i][y] == 0:
                        n[a][b] = 1
                        v[x-i][y] = 1
                        nex.add((x-i, y))
                if l[x-i][y] == 1:
                    break
                i += 1
            # south
            i = 1
            while x+i < H and i <= K:
                a, b = x+i, y
                if a == x2-1 and b == y2-1:
                    return r
                if s[a][b] == 1:
                    break
                if l[x+i][y] == 0:
                    if v[x+i][y] == 0:
                        s[a][b] = 1
                        v[x+i][y] = 1
                        nex.add((x+i, y))
                if l[x+i][y] == 1:
                    break
                i += 1
            # west
            i = 1
            while y-i > -1 and i <= K:
                a, b = x, y-i
                if a == x2-1 and b == y2-1:
                    return r
                if w[a][b] == 1:
                    break
                if l[x][y-i] == 0:
                    if v[x][y-i] == 0:
                        w[a][b] = 1
                        v[x][y-i] = 1
                        nex.add((x, y-i))
                if l[x][y-i] == 1:
                    break
                i += 1
            # east
            i = 1
            while y+i < W and i <= K:
                a, b = x, y+i
                if a == x2-1 and b == y2-1:
                    return r
                if e[a][b] == 1:
                    break
                if l[x][y+i] == 0:
                    if v[a][b] == 0:
                        e[a][b] = 1
                        v[x][y+i] = 1
                        nex.add((x, y+i))
                if l[x][y+i] == 1:
                    break
                i += 1
        cur = nex
        if not cur:
            return -1
    return -1
print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            print(visited[y][x])
            quit()
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              #print(new_y, new_x)
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                else:
                  if visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])#新しい点を足す。
                  else:
                    p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            print(visited[y][x])
            quit()
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              #print(new_y, new_x)
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                else:
                  if visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])#新しい点を足す。
                  else:
                    p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
print(visited)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from collections import deque

def main():
	h,w,k=MI()
	x1,y1,x2,y2=MI()
	G=["@"]*(w+2)
	for _ in range(h):
		G.append("@")
		G+=(list(map(str,input().rstrip())))
		G.append("@")
	G+=["@"]*(w+2)
	#print(G)


	G[x1*(w+2)+y1]=0
	#print(G)

	Q=deque()
	Q.append((x1*(w+2)+y1,0))

	while Q:
		#print(Q)
		now,d=Q.popleft()
		#print(Q)
		for i in range(1,k+1):
			if G[now+i]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])
			else:
				break
		for i in range(1,k+1):
			if G[now-i]==".":
				G[now-i]=d+1
				Q.append([now-i,d+1])
			else:
				break
		for i in range(1,k+1):
			if G[now+(w+2)*i]==".":
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			else:
				break
		for i in range(1,k+1):
			if G[now-(w+2)*i]==".":
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			else:
				break
		#print(Q)
	#print(G)

	if G[x2*(w+2)+y2]==".":
		print(-1)
	else:
		print(G[x2*(w+2)+y2])









































if __name__ == "__main__":
	main()