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 heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 9
        visited = [[False]*(w+2) for _ in range(h+2)]

        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[xs][ys] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1,0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)
            if (x, y) == (xg, yg):
                ans = (dp[x][y] + k -1)//k
                return ans

            if not visited[x][y]:
                for i in range(4):
                    nx, ny = x+direction[i][0], y+ direction[i][1]
                    if field[nx][ny]:
                        if i == dirt:
                            if dp[nx][ny] > dp[x][y] + 1:
                                dp[nx][ny] = dp[x][y] + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                        else:
                            if dp[nx][ny] > (dp[x][y] + k-1)//k*k + 1:
                                dp[nx][ny] = (dp[x][y] + k-1)//k*k + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                visited[x][y] = True
        return -1





    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 7
        visited = [[False]*(w+2) for _ in range(h+2)]

        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[xs][ys] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1,0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)
            if (x, y) == (xg, yg):
                ans = (dp[x][y] + k -1)//k
                return ans

            if not visited[x][y]:
                for i in range(4):
                    nx, ny = x+direction[i][0], y+ direction[i][1]
                    if field[nx][ny]:
                        if i == dirt:
                            if dp[nx][ny] > dp[x][y] + 1:
                                dp[nx][ny] = dp[x][y] + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                        else:
                            if dp[nx][ny] > (dp[x][y] + (k-1))//k*k + 1:
                                dp[nx][ny] = (dp[x][y] + (k-1))//k*k + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                visited[x][y] = True
        return -1





    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w, k = LI()
x1, y1, x2, y2 = LI()
c = [input() for _ in range(h)]

que = deque()
que.append((y1-1, x1-1))
dp = [[inf] * w for _ in range(h)]
dp[x1-1][y1-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        if i == 0:
            for ki in range(k):
                nx = x + (ki + 1)
                if 0 <= nx < w:
                    if c[y][nx] == '.':
                        if dp[y][nx] <= dp[y][x] + 1:
                            break
                        dp[y][nx] = dp[y][x] + 1
                        que.append((nx, y))
                    else:
                        break
                else:
                    break
        elif i == 1:
            for ki in range(k):
                ny = y + (ki + 1)
                if 0 <= ny < h:
                    if c[ny][x] == '.':
                        if dp[ny][x] <= dp[y][x] + 1:
                            break
                        dp[ny][x] = dp[y][x] + 1
                        que.append((x, ny))
                    else:
                        break
                else:
                    break
        elif i == 2:
            for ki in range(k):
                nx = x - (ki + 1)
                if 0 <= nx < w:
                    if c[y][nx] == '.':
                        if dp[y][nx] <= dp[y][x] + 1:
                            break
                        dp[y][nx] = dp[y][x] + 1
                        que.append((nx, y))
                    else:
                        break
                else:
                    break
        else:
            for ki in range(k):
                ny = y - (ki + 1)
                if 0 <= ny < h:
                    if c[ny][x] == '.':
                        if dp[ny][x] <= dp[y][x] + 1:
                            break
                        dp[ny][x] = dp[y][x] + 1
                        que.append((x, ny))
                    else:
                        break
                else:
                    break
ans = dp[x2-1][y2-1]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                if depth[ny][nx] == depth[y][x]+1:
                    continue
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
            else:
                break
            K -= 1
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(h):
    maze.append(list(input()))
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
maze[a][b] = "@"
while dq:
    x,y = dq.popleft()
    if (x,y) == (d,c):
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@":
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
                maze[ny][nx] = "@"
            else:
                break
            K -= 1
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(h):
    maze.append(list(input()))
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
maze[a][b] = "@"
while dq:
    x,y = dq.popleft()
    if (x,y) == (d,c):
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@":
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
                maze[ny][nx] = "@"
            else:
                break
            K -= 1
print(depth)
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Wrong Answer

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    row = set()
    col = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in col or np in st or pond[x-i][y] == 1:
                break
            if np in row:
                col.add(np)
                continue
            heapq.heappush(hq, [c, (x-i, y)])
            col.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in col or np in st or pond[x+i][y] == 1:
                break
            if np in row:
                col.add(np)
                continue
            heapq.heappush(hq, [c, (x+i, y)])
            col.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in row or np in st or pond[x][y-i] == 1:
                break
            if np in col:
                row.add(np)
                continue
            heapq.heappush(hq, [c, (x, y-i)])
            row.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in row or np in st or pond[x][y+i] == 1:
                break
            if np in col:
                row.add(np)
                continue
            heapq.heappush(hq, [c, (x, y+i)])
            row.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    row = set()
    col = set()
    st.add((x1, y1))
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in col or pond[x-i][y] == 1:
                break
            if np in row:
                col.add(np)
                continue
            heapq.heappush(hq, [c, (x-i, y)])
            st.add(np)
            col.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in col or pond[x+i][y] == 1:
                break
            if np in row:
                col.add(np)
                continue
            heapq.heappush(hq, [c, (x+i, y)])
            st.add(np)
            col.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in row or pond[x][y-i] == 1:
                break
            if np in col:
                row.add(np)
                continue
            heapq.heappush(hq, [c, (x, y-i)])
            st.add(np)
            row.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in row or pond[x][y+i] == 1:
                break
            if np in col:
                row.add(np)
                continue
            heapq.heappush(hq, [c, (x, y+i)])
            st.add(np)
            row.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = ["@" for _ in range(h+2)]
    for i in range(w+1):
        pond[0] += "@"
        pond[h+1] += "@"
    for i in range(1, h+1):
        s = input()
        pond[i] += s + "@"
    hq = [[0, (x1, y1)]]
    st = set()
    st.add((x1, y1))
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in st or pond[x-i][y] == "@":
                break
            heapq.heappush(hq, [c, (x-i, y)])
            st.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in st or pond[x+i][y] == "@":
                break
            heapq.heappush(hq, [c, (x+i, y)])
            st.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in st or pond[x][y-i] == "@":
                break
            heapq.heappush(hq, [c, (x, y-i)])
            st.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in st or pond[x][y+i] == "@":
                break
            heapq.heappush(hq, [c, (x, y+i)])
            st.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import heapq
#from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
que = []
#que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], (x1,y1)))
#que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y= heapq.heappop(que)[1]
  #x,y= p[0],p[1]
  #x,y = que.popleft()
  if (x == x2) & (y == y2):exit(print(dp[x2][y2]))
  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) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[x][y]:break
      if dp[nx][ny] == -1:
        heapq.heappush(que, (dp[nx][ny], (nx,ny)))
        #que.append((nx,ny))
      dp[nx][ny] = dp[x][y] + 1

print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
#from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
que = []
#que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
#que.append((dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)[1]
  x,y= p[0],p[1]
  #x,y = que.popleft()
  if (x == x2) & (y == y2):exit(print(dp[x2][y2]))
  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) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[x][y]:break
      if dp[nx][ny] == -1:
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        #que.append((dp[nx][ny], [nx,ny]))
      dp[nx][ny] = dp[x][y] + 1

print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
#from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
que = []
#que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
#que.append((dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)[1]
  #p = que.popleft()
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      if dp[nx][ny] == -1:
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        #que.append((dp[nx][ny], [nx,ny]))
      dp[nx][ny] = dp[p[0]][p[1]] + 1

print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
#from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
que = []
#que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
#que.append((dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  #p = que.popleft()
  p = p[1]
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      if dp[nx][ny] == -1:
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        #que.append((dp[nx][ny], [nx,ny]))
      dp[nx][ny] = dp[p[0]][p[1]] + 1

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  c[i] = input()

dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]-1))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if (dp[nx][ny] != 0) | (dp[nx][ny] > dp[p[0]][p[1]]):break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  c[i] = input()

dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      if c[nx][ny] == '@':dp[nx][ny] = -1
      while (0 <= dp[nx][ny] < dp[p[0]][p[1]]):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import collections
H, W, K = [int(_) for _ in input().split()]
x1, y1, x2, y2 = [int(_) - 1 for _ in input().split()]
C = [[10**6 if s == '.' else None for s in input()] for _ in range(H)]
C[x1][y1] = 0
Qx = collections.deque([(x1, y1)])  #次にxが変化
Qy = collections.deque([(x1, y1)])  #次にyが変化
while True:
    if not (Qx or Qy):
        break
    Qy2 = collections.deque([])
    while Qx:
        x, y = Qx.popleft()
        for nx in range(x + 1, H):
            if C[nx][y] is None:
                break
            elif C[nx][y] == 10**6:
                Qy2 += [(nx, y)]
                C[nx][y] = C[x][y] + 1 + (nx - x - 1) // K
        for nx in range(x - 1, -1, -1):
            if C[nx][y] is None:
                break
            elif C[nx][y] == 10**6:
                Qy2 += [(nx, y)]
                C[nx][y] = C[x][y] + 1 + (x - nx - 1) // K
    Qx2 = collections.deque([])
    while Qy:
        x, y = Qy.popleft()
        for ny in range(y + 1, W):
            if C[x][ny] is None:
                break
            elif C[x][ny] == 10**6:
                Qx2 += [(x, ny)]
                C[x][ny] = C[x][y] + 1 + (ny - y - 1) // K
        for ny in range(y - 1, -1, -1):
            if C[x][ny] is None:
                break
            elif C[x][ny] == 10**6:
                Qx2 += [(x, ny)]
                C[x][ny] = C[x][y] + 1 + (y - ny - 1) // K
    Qx = Qx2
    Qy = Qy2
ans = C[x2][y2]
print(ans if ans < 10**6 else -1)

Submission status: Wrong Answer

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    ki = 1
    while ki <= k:
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (nx<0) | (nx>(h-1)) | (ny<0) | (ny>(w-1)) :break
      if (dp[nx][ny] != 0):break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))
      ki += 1

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

Submission status: Wrong Answer

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

def dijkstra():
    dist = [[[10**18]*4 for _ in range(W)] for _ in range(H)]
    pq = []
    
    for i in range(4):
        dist[sx][sy][i] = 0
        heappush(pq, (0, sx, sy, i))
    
    while pq:
        d, cx, cy, dire = heappop(pq)
        
        if dist[cx][cy][dire]<d:
            continue
        
        for nx, ny, ndire in [(cx-1, cy, 0), (cx+1, cy, 1), (cx, cy-1, 2), (cx, cy+1, 2)]:
            if dire==ndire and 0<=nx<H and 0<=ny<W and c[nx][ny]=='.':
                if dist[nx][ny][dire]>d+1:
                    dist[nx][ny][dire] = d+1
                    heappush(pq, (d+1, nx, ny, dire))
        
        for ndire in range(4):
            if dire!=ndire:
                if dist[cx][cy][ndire]>(d+K-1)//K*K:
                    dist[cx][cy][ndire] = (d+K-1)//K*K
                    heappush(pq, ((d+K-1)//K*K, cx, cy, ndire))
    
    return (min(dist[gx][gy])+K-1)//K

H, W, K = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [input()[:-1] for _ in range(H)]
ans = dijkstra()

if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        if (dp[nnx][nny] == (dp[p[0]][p[1]] + 1)):dp[nnx][nny] = 0
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

heap = []

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

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heapq.heappush(heap, (0, 0, s))

vis = [[[False for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heapq.heappop(heap)
    if vis[d][p[0]][p[1]]:
        continue
    vis[d][p[0]][p[1]] = True
    if p == t:
        ans = (cost + k - 1) // k
        break

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]] and not vis[d][next_p[0]][next_p[1]]:
        heapq.heappush(heap, (cost + 1, d, next_p))

    for i in range(4):
        if not vis[i][p[0]][p[1]]:
            next_cost = (cost + k - 1) // k
            heapq.heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = deque()
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p = que.popleft()
  if (p[0] == x2) & (p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 0
      while dp[nx][ny] == 0:
        que.append((nx,ny))
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt >= k):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = deque()
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p = que.popleft()
  if (p[0] == x2) & (p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 0
      while dp[nx][ny] == 0:
        que.append((nx,ny))
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = deque()
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p = que.popleft()
  if (p[0] == x2) & (p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      while dp[nx][ny] == 0:
        que.append((nx,ny))
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)