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: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(si, sj)])
    while queue:
        i, j = queue.popleft()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                if dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q0 = deque([(0,x1,y1,(0,0),0)])
q1 = deque()

dx = [0,1,0,-1]
dy = [1,0,-1,0]
# dist = [[None]*w for _ in range(h)]
dist = [None]*(w*h)
dist[x1*w+y1] = 0
# done = [[0]*w for _ in range(h)]
done = [0]*(w*h)
done[x1*w+y1] = 15

while q0 or q1:
    if not q0:
        q0 = q1
        q1 = deque()
    d, x, y, t, td = q0.popleft()
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
            q = q0
        else:
            nd = d+1
            ntd = 1
            q = q1
        if dist[nx*w+ny] is None or nd<dist[nx*w+ny]:
            q.append((nd,nx,ny,(xx,yy),ntd))
            dist[nx*w+ny] = nd
            done[nx*w+ny] = 1<<(i)
        elif nd==dist[nx*w+ny]and ((done[nx*w+ny]&1<<(i))==0):
            q.append((nd,nx,ny,(xx,yy),ntd))
            done[nx*w+ny] |= 1<<(i)
            
if dist[x2*w+y2] is None:
    print(-1)
else:
    print(dist[x2*w+y2])

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      if dp[pp * W + q] != inf: continue
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      if dp[pp * W + q] != inf: continue
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      if dp[p * W + qq] != inf: continue
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      if dp[p * W + qq] != inf: continue
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()
        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1  # ここで更新しないと無駄な探索が発生する

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()
        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

                # if (0 <= x2 < H) and (0 <= y2 < W):
                #     if m[x2][y2] == '@':
                #         break
                #     elif M[x2][y2] == -1:
                #         M[x2][y2] = d + 1
                #         q.append((d + 1, x2, y2))
                #     elif M[x2][y2] == d + 1:
                #         continue
                #     else:
                #         break
                # else:
                #     break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

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

bfs(xs - 1, ys - 1, 0)

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))  # 新しい点を足す。
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(xs, ys, d):
    queue = deque()
    queue.append((xs, ys, d))
    M[xs][ys] = d
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1, d = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return

        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:  # まだ来たことない点だったという条件
                        M[x2][y2] = d + 1
                        queue.append((x2, y2, d + 1))  # 新しい点を足す。
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(xs, ys):
    queue = deque([[xs, ys]])
    M[xs][ys] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1 = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[x1][y1]

        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  # まだ来たことない点だったという条件
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  # 新しい点を足す。
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys)

print(M[xg][yg])

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(M, sy, sx):
    queue = deque([[xs, ys]])
    M[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1 = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[x1][y1]
        
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  # まだ来たことない点だったという条件
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  # 新しい点を足す。
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(M, xs, ys)

print(M[xg][yg])

Submission status: Accepted

Solution code:
from collections import deque
import sys

def bfs(M, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    M[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[y][x]
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k

                if (0 <= new_y < H) and (0 <= new_x < W):
                    if m[new_y][new_x] == "@":
                        break
                    elif M[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        M[new_y][new_x] = M[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif M[new_y][new_x] < M[y][x] + 1:
                        break
                else:
                    break


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

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))
    
M = [[-1] * W for i in range(H)]

bfs(M, x1, y1, x2, y2)

print(M[x2][y2])

Submission status: Accepted

Solution code:
from collections import deque


def bfs(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 dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k

                if (0 <= new_y < H) and (0 <= new_x < W):
                    if m[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break


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
m = []
for i in range(H):
    m.append(str(input()))
visited = [[-1] * W for i in range(H)]
bfs(visited, x1, y1, x2, y2)
print(visited[x2][y2])

Submission status: Accepted

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 dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k
                
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break


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

Submission status: Accepted

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]):
            l = 1
            while True:
                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] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


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

Submission status: Accepted

Solution code:
import collections
H,W,K = map(int,input().split())
s1,e1,s2,e2 = map(int,input().split())
s1-=1
e1-=1
s2-=1
e2-=1
L = []
board = []
for _ in range(H):
    a = input()
    L.append(a)
for i in range(H):
    l = L[i]
    tmp = []
    for j in range(len(l)):
        tmp.append(l[j])
    board.append(tmp)

queue = collections.deque()
queue.append([0,s1,e1])
seen = [[float('inf')]*(W) for _ in range(H)]
destination = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
    cost,x,y = queue.popleft()
    seen[x][y] = cost
    if x==s2 and y ==e2:
        print(cost);exit()
        break
    for dx,dy in destination:
        X,Y = x,y
        for i in range(1,K+1):
            NX = X +i*dx
            NY = Y + i*dy
            if 0>NX or NX>=H or 0>NY or NY>=W or seen[NX][NY] < seen[X][Y]+1: break
            else:
                if board[NX][NY]=='@':
                    break
                elif seen[NX][NY] ==float('inf'):
                    queue.append([cost+1,NX,NY])
                    seen[NX][NY] = cost+1

print(-1)

Submission status: Accepted

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


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [input() for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                ny, nx = y+dy*j, x+dx*j
                if (not (0<=ny<H and 0<=nx<W)) or l[ny][nx]=="@" or dist[(ny, nx)] < dist[(y, x)] + 1:
                    break
                if dist[(ny, nx)] > dist[(y, x)] + 1:
                    dist[(ny, nx)] = dist[(y, x)] + 1
                    q.append((ny, nx))
                else:
                    continue

    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                ny, nx = y+dy*j, x+dx*j
                if (not (0<=ny<H and 0<=nx<W)) or l[ny][nx] or dist[(ny, nx)] < dist[(y, x)] + 1:
                    break
                if dist[(ny, nx)] > dist[(y, x)] + 1:
                    dist[(ny, nx)] = dist[(y, x)] + 1
                    q.append((ny, nx))
                else:
                    continue

    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if (not (0<=y+dy*j<H and 0<=x+dx*j<W)) or l[y+dy*j][x+dx*j] or dist[(y+dy*j, x+dx*j)] < dist[(y, x)] + 1:
                    break
                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                else:
                    continue

    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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

c = [input().rstrip() for _ in range(H)]

d = deque([(x1-1, y1-1)])

dp = [[-1] * W for _ in range(H)]
dp[x1-1][y1-1] = 0

while d:
    x, y = d.popleft()
    if x == x2-1 and y == y2-1:
        print(dp[x][y])
        break

    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        for i in range(1, K+1):
            nx = x + dx * i
            ny = y + dy * i

            if 0 > nx or nx >= H or 0 > ny or ny >= W or c[nx][ny] == '@':
                break

            if dp[nx][ny] == -1:
                dp[nx][ny] = dp[x][y] + 1
                d.append((nx, ny))
            elif dp[nx][ny] <= dp[x][y]:
                break
else:
    print(-1)

Submission status: Accepted

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


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                elif dist[(y+dy*j, x+dx*j)] == dist[(y, x)] + 1:
                    continue
                else:
                    break


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()