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:
#!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)]
    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
    q = [(0,y,x,-1,0)]
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    while q:
        dx,y,x,p,l = heappop(q)
        if (y,x) == (s,t):
            print(d[s][t])
            return
        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
                heappush(q,(nd,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
                heappush(q,(nd,ny,nx,p,l-1))
    print(-1)
    return

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
fastinput = sys.stdin.readline
H,W,K = [int(hoge) for hoge in fastinput().split()]
x1,y1,x2,y2 = [int(hoge)-1 for hoge in fastinput().split()]
S = (x1,y1)
G = (x2,y2)
chizu = [fastinput() 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 and chizu[togox][togoy] == ".":
                    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
import math
h,w,k=map(int,input().split())
r=[1, 0, 0, -1] 
c=[0, -1, 1, 0] 
x1,y1,x2,y2=map(int,input().split())
vis=[[False for i in range(w)] for j in range(h)]
arr=[]
for i in range(h):
    ff=list(input())
    arr.append(ff)
f=0
q=deque()
q.append([x1-1,y1-1,0])
vis[x1-1][y1-1]=True
while(len(q)>0):
    curr=q.popleft()
    if curr[0]==x2-1 and curr[1]==y2-1:
        f=curr[2]+2
        break
    for i in range(4):
        row=curr[0]+r[i]
        col=curr[1]+c[i]
    
        if row<=h-1 and row>=0 and col>=0 and col<=w-1 and arr[row][col]=='.' and not vis[row][col]:
                vis[row][col]=True
                b=[row,col,curr[2]+1]
                q.append(b)
if f==0:
    print(-1)
else:
    print(math.ceil(f/k))

Submission status: Wrong Answer

Solution code:
import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]


xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            if nx>=0 and nx<H and ny>=0 and ny<W and cnt[nx][ny]==10**10:
                if li[nx][ny]=="@":
                    # print(nx,ny)
                    break
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()

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()
        if (y,x) == (s,t):
            print(d[s][t])
            return
        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))
    print(-1)
    return

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

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
                            que.append((h_new, w_new))
                            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:
#!/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[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(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:
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 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                  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
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 = []
    costs = [[None for j in range(w)] for i in range(h)]
    for _ in range(h):
        m.append(list(input().strip()))
    q = deque()
    q.append((x1, y1, 0))
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q:
        (x, y, cost) = q.popleft()
        if (x, y) == (x2, y2):
            print(cost)
            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:
                    break
                if m[new_x][new_y] == '.' and costs[new_x][new_y] is None:
                    costs[new_x][new_y] = cost + 1
                    q.append((new_x, new_y, cost + 1))
    print("-1")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

x_1, y_1, x_2, y_2 = map(int, input().split())

pond_map = [list(input()) for i in range(h)]

seen = set()

seen.add((x_1, y_1))

d = deque()

d.append((x_1, y_1, 0))

answer = -1

get_answer = False

while len(d) != 0:
    now_pos = d.popleft()
    for i in range(k):
        next_pos = (now_pos[0], now_pos[1] + i + 1, now_pos[2] + 1)
        if next_pos[1] > w:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] in seen:
            break
        seen.add(next_pos[:2])
        d.append(next_pos)
    if get_answer:
        break

    for i in range(k):
        next_pos = (now_pos[0], now_pos[1] - i - 1, now_pos[2] + 1)
        if next_pos[1] < 1:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] in seen:
            break
        seen.add(next_pos[:2])
        d.append(next_pos)
    if get_answer:
        break

    for i in range(k):
        next_pos = (now_pos[0] + 1 + i, now_pos[1], now_pos[2] + 1)
        if next_pos[0] > h:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] in seen:
            break
        seen.add(next_pos[:2])
        d.append(next_pos)
    if get_answer:
        break

    for i in range(k):
        next_pos = (now_pos[0] - i - 1, now_pos[1], now_pos[2] + 1)
        if next_pos[0] < 1:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] in seen:
            break
        seen.add(next_pos[:2])
        d.append(next_pos)
    if get_answer:
        break

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


input = iter(sys.stdin.readlines()).__next__

R, C, K = [int(x) for x in input().split()]
X1, Y1, X2, Y2 = [int(x) - 1 for x in input().split()]  # 0 indexed

grid = [input().rstrip() for r in range(R)]

source = (X1, Y1)
q = deque([source])
dist = {source: 0}


def getNbr(node):
    r, c = node
    ret = []
    for dr, dc in [(0, 0), (-1, 0), (0, -1), (0, 1), (1, 0)]:
        for k in range(1, K + 1):
            nr = r + dr * k
            nc = c + dc * k
            if not (0 <= nr < R and 0 <= nc < C):
                break
            if grid[nr][nc] == "@" or (nr, nc) in dist:
                break
            ret.append((nr, nc))
    return ret


while q:
    node = q.popleft()
    d = dist[node]
    for nbr in getNbr(node):
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = d + 1


if False:
    for row in grid:
        print(row)
    print()
    for r in range(R):
        for c in range(C):
            print(dist.get((r, c), "?"), end=" ")
        print()


if (X2, Y2) in dist:
    print(dist[(X2, Y2)])
else:
    print(-1)

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:
                    n[a][b] = 1
                    if v[x-i][y] == 0:
                        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:
                    s[a][b] = 1
                    if v[x+i][y] == 0:
                        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:
                    w[a][b] = 1
                    if v[x][y-i] == 0:
                        v[x][y-i] = 1
                        nex.add((x, y-i))
                if l[x][y-i] == 1:
                    break
                i += 1
            # south
            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:
                    e[a][b] = 1
                    if v[a][b] == 0:
                        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 heapq import heappop, heappush


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

    q = [(0, s)]
    while q:
        cost, v = heappop(q)
        nc = cost + 1
        for d, ax 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][ax] <= nc:
                    break
                ans[u][ax] = nc
                heappush(q, (nc, u))
    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:
import sys
sys.setrecursionlimit(10 ** 9)
                      
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

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

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

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

Submission status: Wrong Answer

Solution code:
from 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 = [[10**6 for _ in range(w)] for _ in range(h)]

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

while len(q) != 0:
    x, y, c = q.popleft()
    for i in range(1, k+1):
        if x-i >= 0 and is_visit[y][x-i] > c+1 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] > c+1 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] > c+1 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] > c+1 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 == 10**6:
    print(-1)
else:
    print(ans)

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]:#もしゴールについていたならば、そのときの手数を出す。
            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 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif 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(visited[x2][y2])