Problem:


Score : 600 points

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2).
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K = [int(hoge) for hoge in input().split()]
x1,y1,x2,y2 = [int(hoge)-1 for hoge in input().split()]
S = (x1,y1)
G = (x2,y2)
chizu = [input() for h in range(H)]
yoko = []
for row in chizu:
    y = []
    for n,at in enumerate(row):
        if at == "@":
            y.append(n)
    y.append(W)
    yoko.append(y)

tate = []
for w in range(W):
    t = []
    for h in range(H):
        if chizu[h][w] == "@":
            t.append(h)
    t.append(H)
    tate.append(t)

RLDU = [[[-1,-1,-1,-1] for w in range(W)] for h in range(H)]
for h in range(H):
    yokonow = yoko[h]
    nextyoko = 0
    curleft = 0 #実際に動けるマスの数
    curright = yokonow[0] - 1
    for curpos in range(W):
        if chizu[h][curpos] == "@":#葉っぱ
            nextyoko += 1
            curleft = 0
            curright = yokonow[nextyoko] - curpos - 2
        else:
            RLDU[h][curpos][0] = curright
            RLDU[h][curpos][1] = curleft
            curright -= 1
            curleft += 1
        
for w in range(W):
    tatenow = tate[w]
    nexttate = 0
    curup = 0
    curdown = tatenow[0] - 1
    for curpos in range(H):
        if chizu[curpos][w] == "@":
            nexttate += 1
            curup = 0
            curdown = tatenow[nexttate] - curpos - 2
        else:
            RLDU[curpos][w][2] = curdown
            RLDU[curpos][w][3] = curup
            curdown -= 1
            curup += 1

queue = deque()#append,popleft
dist = [[-1] * W for h in range(H)]
queue.append((x1,y1,4,True))#座標+RLDUで来た方角,その方角にさらに進む必要性
dist[x1][y1] = 0
NOTGO = [1,0,4,3,100]
while queue:
    curx,cury,comefrom,isMax = queue.popleft()
    curdist = dist[curx][cury]
    nextRLDU = RLDU[curx][cury]
    for direction in range(4):
        if direction == NOTGO[comefrom]:
            continue
        elif direction == comefrom and not isMax:
            continue
        else:
            Kyori = min(K,nextRLDU[direction])
            for k in range(1,Kyori+1):
                nextismax = (k == K)
                if direction == 0:
                    togo = [curx,cury+k]
                if direction == 1:
                    togo = [curx,cury-k]
                if direction == 2:
                    togo = [curx+k,cury]
                if direction == 3:
                    togo = [curx-k,cury]
                togox,togoy = togo
                if dist[togox][togoy] ==-1:
                    dist[togox][togoy] = curdist + 1
                    queue.append((togox,togoy,direction,nextismax))
print(dist[x2][y2])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q = deque([(x1,y1,0)])
dist = [[-1]*w for _ in range(h)]
over = {}
over["right"] = [[0]*w for _ in range(h)]
over["left"]  = [[0]*w for _ in range(h)]
over["up"]    = [[0]*w for _ in range(h)]
over["down"]  = [[0]*w for _ in range(h)]
while q:
    x,y,d = q.popleft()
    dist[y][x] = d
    if y == y2 and x == x2: break
    for dx,dy,direction in [(-1,0,"left"),(1,0,"right"),(0,-1,"down"),(0,1,"up")]:
        over[direction][y][x] = 1
        newx = x+dx
        newy = y+dy
        count = 1
        while 0<=newx<w and 0<=newy<h and count<=k and c[newy][newx]==".":
            if over[direction][newy][newx] == 1: break
            
            over[direction][newy][newx] = 1
                
            if dist[newy][newx] == -1:
                q.append((newx,newy,d+1))
            newx += dx
            newy += dy
            count += 1

print(dist[y2][x2])

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
#!/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([State(0, Node(sx, sy, -1, 0))])
    # min_costs = defaultdict(lambda: float("inf"))
    visited = set()
    while q:
        s = q.popleft()
        #print(s)
        node = s.node
        if (node.x, node.y) in visited:
            continue
        if node.x == ex and node.y == ey:
            return s.cost
        visited.add((node.x, node.y, node.d))
        for d, (dx, dy) in enumerate(D):
            next_node = Node(node.x+dx, node.y+dy, d,
                             1 if d != node.d else node.k % K + 1)
            if (next_node.x, next_node.y, next_node.d) in visited:
                continue
            if C[next_node.x][next_node.y] == "@":
                continue
            if d == node.d:
                if next_node.k != 1:
                    q.appendleft(State(s.cost, next_node))
                else:
                    q.append(State(s.cost+1, next_node))
            else:
                q.append(State(s.cost+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 collections

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
arr = [[-1] * w for _ in range(h)]
for i in range(h):
  a = input()
  for j, v in enumerate(a):
    if v == '@':
      arr[i][j] = -2
arr[x1-1][y1-1] = 0
q = collections.deque([(x1-1,y1-1)])
while q:
  x, y = q.popleft()
  step = arr[x][y]
  if x == x2-1 and y == y2-1:
    print(step)
    break
  for d in ((0, 1), (1, 0), (0, -1), (-1, 0)):
    for p in range(1, k+1):
      nx, ny = x + p * d[0], y + p * d[1]
      if not 0 <= nx < h or not 0 <= ny < w or arr[nx][ny] != -1:
        break
      arr[nx][ny] = step + 1
      q.append((nx, ny))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
h,w,k=map(int,input().split())
r=[1, 0, 0, -1] 
c=[0, -1, 1, 0] 
x1,y1,x2,y2=map(int,input().split())
vis=[[False for i in range(w)] for j in range(h)]
arr=[]
for i in range(h):
    ff=list(input())
    arr.append(ff)
f=0

q=deque()
q.append([x1-1,y1-1,0])
vis[x1-1][y1-1]=True
while(len(q)>0):
    curr=q.popleft()
    if curr[0]==x2-1 and curr[1]==y2-1:
        f=curr[2]
        break
    for i in range(4):
        row=curr[0]+r[i]
        col=curr[1]+c[i]
        if row<=h-1 and row>=0 and col>=0 and col<=w-1 and arr[row][col]=='.' and not vis[row][col]:
                vis[row][col]=True
                b=[row,col,curr[2]+1]
                q.append(b)
if f==0:
    print(-1)
else:
    f+=1
    print(math.ceil(f/k))

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W, K = map(int, input().split())
    sh, sw, gh, gw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    seen = [[1] * W for _ in range(H)]
    for h in range(H):
        line = input().rstrip('\n')
        for w in range(W):
            if line[w] == "@":
                seen[h][w] = 2

    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    que = deque()
    que.append((sh, sw))
    seen_d = [[[0] * W for _ in range(H)] for _ in range(4)]
    seen[sh][sw] = 0
    while que:
        h, w = que.popleft()
        for id in range(4):
            dh, dw = d[id]
            h_new = h
            w_new = w
            for _ in range(K):
                flg = 1
                h_new += dh
                w_new += dw
                if 0 <= h_new < H and 0 <= w_new < W:
                    if seen[h_new][w_new] == 1:
                        seen[h_new][w_new] = seen[h][w] - 1
                        seen_d[id][h_new][w_new] = 1
                        que.append((h_new, w_new))
                        flg = 0
                    elif seen[h_new][w_new] < 0:
                        if seen_d[id][h_new][w_new] == 0:
                            seen_d[id][h_new][w_new] = 1
                            flg = 0
                if flg:
                    break
    if seen[gh][gw] < 0:
        print(-seen[gh][gw])
    else:
        print(-1)
    #[print(seen[h]) for h in range(H)]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


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

    q = [(0, s)]
    while q:
        cost, v = heappop(q)
        nc = cost + 1
        for d in MOVE:
            for u in range(v + d, v + d * (k + 1), d):
                if field[u] == '@':
                    break
                if u == t:
                    return nc
                if ans[u] <= nc:
                    break
                ans[u] = nc
                heappush(q, (nc, u))
                u += d
    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))

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())
map = [list(input())[:-1] for _ in range(h)]
is_visit = [[0 for _ in range(w)] for _ in range(h)]

q = deque()
q.append((y2-1, x2-1, 0))

j = 0
while len(q) != 0:
    j += 1
    x, y, c = q.popleft()
    for i in range(1, k+1):
        if x-i >= 0 and is_visit[y][x-i] == 0 and map[y][x-i] == '.':
            is_visit[y][x-i] = c+1
            q.append((x-i, y, c+1))
        else:
            break
    for i in range(1, k+1):
        if x+i < w and is_visit[y][x+i] == 0 and map[y][x+i] == '.':
            is_visit[y][x+i] = c+1
            q.append((x+i, y, c+1))
        else:
            break
    for i in range(1, k+1):
        if y-i >= 0 and is_visit[y-i][x] == 0 and map[y-i][x] == '.':
            is_visit[y-i][x] = c+1
            q.append((x, y-i, c+1))
        else:
            break
    for i in range(1, k+1):
        if y+i < h and is_visit[y+i][x] == 0 and map[y+i][x] == '.':
            is_visit[y+i][x] = c+1
            q.append((x, y+i, c+1))
        else:
            break
ans = is_visit[x1-1][y1-1]
if ans == 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W, K = map(int, input().split())
    sh, sw, gh, gw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    seen = [[1] * W for _ in range(H)]
    for h in range(H):
        line = input().rstrip('\n')
        for w in range(W):
            if line[w] == "@":
                seen[h][w] = 2

    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    que = deque()
    que.append((sh, sw))
    seen_d = [[[0] * W for _ in range(H)] for _ in range(4)]
    seen[sh][sw] = 0
    while que:
        h, w = que.popleft()
        for id in range(4):
            dh, dw = d[id]
            h_new = h
            w_new = w
            for _ in range(K):
                flg = 1
                h_new += dh
                w_new += dw
                if 0 <= h_new < H and 0 <= w_new < W:
                    if seen[h_new][w_new] == 1:
                        seen[h_new][w_new] = seen[h][w] - 1
                        seen_d[id][h_new][w_new] = 1
                        que.append((h_new, w_new))
                        flg = 0
                    elif seen[h_new][w_new] < 0:
                        if seen_d[id][h_new][w_new] == 0:
                            flg = 0
                if flg:
                    break
    if seen[gh][gw] < 0:
        print(-seen[gh][gw])
    else:
        print(-1)
    #[print(seen[h]) for h in range(H)]


if __name__ == '__main__':
    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回通ることはあり得ない。

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")

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
sy, sx, gy, gx = LI()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
grid = SRL(h)

def solve():
    min_cost = [[INF] * w for _ in range(h)]
    min_cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for l in range(1, k + 1):
                ny = cy + i * l
                nx = cx + j * l
                if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == '.':
                    if grid[ny][nx] == '.':
                        if min_cost[cy][cx] + 1 <= min_cost[ny][nx]:
                            min_cost[ny][nx] = min_cost[cy][cx] + 1
                            que += [(ny, nx)]
                        else:
                            break
                else:
                    break
    return min_cost

print(solve()[gy][gx])

Submission status: Wrong Answer

Solution code:
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
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = [[sy,sx]]
gone[sy][sx] = 1
for ans in range(10 ** 6):
    next = []
    for y,x in now:
        if y == gy and x == gx:
            print(ans)
            exit()
        for i in range(1,k+1):
            if y-i < 0 or map[y-i][x] == "@":
                break
            else:
                if gone[y-i][x] == 0:
                    gone[y-i][x] = 1
                    next.append([y-i,x])
        for i in range(1, k + 1):
            if y +i >= h or map[y + i][x] == "@":
                break
            else:
                if gone[y + i][x] == 0:
                    gone[y + i][x] = 1
                    next.append([y + i, x])
        for i in range(1, k + 1):
            if x - i < 0 or map[y][x-i] == "@":
                break
            else:
                if gone[y][x-i] == 0:
                    gone[y][x-i] = 1
                    next.append([y,x-1])
        for i in range(1, k + 1):
            if x+i >= w or map[y][x+i] == "@":
                break
            else:
                if gone[y][x+i] == 0:
                    gone[y][x+i] = 1
                    next.append([y,x+i])
    if next == []:
        print(-1)
        exit()
    now = next
print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

H, W, K=map(int, input().split())
x1, y1, x2, y2=map(int, input().split())
c=['@'*(W+2)]+['@'+input()+'@' for _ in range(H)]+['@'*(W+2)]
l=[[-2]*(W+2) for _ in range(H+2)]
q=[[0, x1, y1]]

heapq.heapify(q)

while q:
  tmp=heapq.heappop(q)
  l[tmp[1]][tmp[2]]=tmp[0]
  
  j=1
  while j<=K and c[tmp[1]-j][tmp[2]]=='.' and l[tmp[1]-j][tmp[2]]==-2:
    heapq.heappush(q, [tmp[0]+1, tmp[1]-j, tmp[2]])
    l[tmp[1]-j][tmp[2]]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]+j][tmp[2]]=='.' and l[tmp[1]+j][tmp[2]]==-2:
    heapq.heappush(q, [tmp[0]+1, tmp[1]+j, tmp[2]])
    l[tmp[1]+j][tmp[2]]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]][tmp[2]-j]=='.' and l[tmp[1]][tmp[2]-j]==-2:
    heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]-j])
    l[tmp[1]][tmp[2]-j]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]][tmp[2]+j]=='.' and l[tmp[1]][tmp[2]+j]==-2:
    heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]+j])
    l[tmp[1]][tmp[2]+j]=-1
    j+=1

if l[x2][y2]<0:
  print(-1)
else:
  print(l[x2][y2])

Submission status: Wrong Answer

Solution code:
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
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = [[sy,sx]]
gone[sy][sx] = 1
for ans in range(10 ** 6):
    next = []
    for y,x in now:
        if y == gy and x == gx:
            print(ans)
            exit()
        for i in range(1,k+1):
            if y-i < 0 or map[y-i][x] == "@":
                break
            else:
                if gone[y-i][x] == 0:
                    gone[y-i][x] = 1
                    next.append([y-i,x])
        for i in range(1, k + 1):
            if y +i >= h or map[y + i][x] == "@":
                break
            else:
                if gone[y + i][x] == 0:
                    gone[y + i][x] = 1
                    next.append([y + i, x])
        for i in range(1, k + 1):
            if x - i < 0 or map[y][x-i] == "@":
                break
            else:
                if gone[y][x-i] == 0:
                    gone[y][x-i] = 1
                    next.append([y, x-1])
        for i in range(1, k + 1):
            if x+ i >= w or map[y][x+i] == "@":
                break
            else:
                if gone[y][x+i] == 0:
                    gone[y][x+i] = 1
                    next.append([y, x+i])
    now = next
print(-1)

Submission status: Wrong Answer

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      p = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        for k in range(1, K + 1):
          hh = h + i * k
          ww = w + j * k
          if s.L[hh + 1][ww + 1] >= 0:
            if T[hh][ww] == -1 or T[hh][ww] > p + 1:
              q.put([hh, ww])
              T[hh][ww] = p + 1
            elif T[hh][ww] != p:
              break
          else:
            break
            
    return T, k


H, W, K = list(map(int, input().split()))
xy = list(map(int, input().split()))
c = []
for i in range(H):
  c.append(list(input()))

for i in range(H):
  for j in range(W):
    if c[i][j] == ".":
      c[i][j] = 0
    else:
      c[i][j] = -1

g = gridMan(c)
g.makeWall()

L, k = g.dist([xy[0] - 1, xy[1] - 1])

print(L[xy[2] - 1][xy[3] - 1])

Submission status: Time Limit Exceeded

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

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            elif dp[x+dx*j][y+dy*j]==dp[x][y]+1:continue###
            elif dp[x+dx*j][y+dy*j]<=dp[x][y]:break###
    
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)

Submission status: Time Limit Exceeded

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

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# k の剰余での管理は配列が大きいか
# 適当に枝刈りする
import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    if x==x2 and y==y2:
        print(dp[x][y])
        exit()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))

        
print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[[INF]*4 for _ in range(w)] for _ in range(h)]
dp[x1][y1]=[0]*4
from collections import deque
q=deque()

for i in range(4):q.append((x1,y1,i))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y,i=q.popleft()
    tmp=((dp[x][y][i]+k-1)//k)*k
    tmp2=dp[x][y][i]+1
    for j,(dx,dy) in enumerate(dxy):
        if i!=j and dp[x][y][j]>tmp:
            dp[x][y][j]=tmp
            q.append((x,y,j))
        xd=x+dx;yd=y+dy
        if 0<=xd and  xd<h and 0<=yd and yd<w:
            if c[xd][yd]!='@':
                if i==j and dp[xd][yd][i]>tmp2:
                    dp[xd][yd][i]=tmp2
                    q.append((xd,yd,i))
            
if min(dp[x2][y2])==INF:
    print(-1)
else:
    print((min(dp[x2][y2])+k-1)//k)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
#解説参照
#状態拡張、方向転換を切り上げで表現
h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**15
dp=[[[INF]*4 for _ in range(w)] for _ in range(h)]
dp[x1][y1]=[0]*4
from collections import deque
q=deque()

for i in range(4):q.append((x1,y1,i))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y,i=q.popleft()
    for j,(dx,dy) in enumerate(dxy):
        if i!=j and dp[x][y][j]>((dp[x][y][i]+k-1)//k)*k:
            dp[x][y][j]=((dp[x][y][i]+k-1)//k)*k
            q.append((x,y,j))
        xd=x+dx;yd=y+dy
        if 0<=xd and  xd<h and 0<=yd and yd<w:
            if c[xd][yd]!='@':
                if i==j and dp[xd][yd][i]>dp[x][y][i]+1:
                    dp[xd][yd][i]=dp[x][y][i]+1
                    q.append((xd,yd,i))
            
if min(dp[x2][y2])==INF:
    print(-1)
else:
    print((min(dp[x2][y2])+k-1)//k)