Problem:


Score : 600 points

Problem Statement

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

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

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

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

Constraints

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

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

5

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

-1



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


Sample output:
5

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break
        if dp[i][y] > c + 1:
            dp[i][y] = c + 1
            q.append((i, y))
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break
        if dp[i][y] > c + 1:
            dp[i][y] = c + 1
            q.append((i, y))
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break
        if dp[x][j] > c + 1:
            dp[x][j] = c + 1
            q.append((x, j))
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break
        if dp[x][j] > c + 1:
            dp[x][j] = c + 1
            q.append((x, j))
        else:
            break

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
X1, Y1, X2, Y2 = lr()
X1 -= 1; Y1 -= 1; X2 -= 1; Y2 -= 1
C = [sr() for _ in range(H)]
graph = [[] for _ in range((H*W)*4)]  # 0-indexed
for i in range(H):
    for j in range(W):
        pos = (W*i + j)*4
        left = False; right = False
        if C[i][j] == '@':
            continue
        if j == 0: left = True
        if j == W-1: right = True
        for con, dir in [(0, -4*W), (1, 4), (2, 4*W), (3, -4)]:
            # 0を上、1を右
            if left and con == 3: continue
            if right and con == 1: continue
            if 0 <= pos + con + dir < H*W*4:
                z = (pos + dir) // 4
                w = z % W; h = z // W
                if C[h][w] == '@':
                    continue
                graph[pos + con].append(((pos+con+dir), 1))
        for con in range(4):
            graph[pos+con].append(((pos+(con+1)%4), -1))
            graph[pos+con].append(((pos+(con-1)%4), -1))
            graph[pos+con].append(((pos+(con+2)%4), -1))

INF = 10 ** 23

def dijkstra(start):
    dist = [INF] * H * W * 4
    que = [(0, start)]
    dist[start] = 0
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, dis in graph[prev]:
            if dis == -1:
                d1 = (d+K-1)//K * K
            else:
                d1 = d + dis
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

start = (W*X1+Y1)*4
dist = dijkstra(start)
goal = (W*X2 + Y2)*4
answer = dist[goal]
answer = (answer+K-1) // K
print(answer if answer != INF // K else -1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    while q:
      y,x = q.popleft()
      if (y,x) == (s,t):
          print(d[s][t])
          return
      nd = d[y][x] + 1
      for dy,dx in dd:
          ny,nx = y,x
          for _ in range(k):
              ny += dy
              nx += dx
              if 0 <= ny < h and 0 <= nx < w and c[ny][nx] != "@" and nd < d[ny][nx]:
                  d[ny][nx] = nd
                  q.append((ny,nx))
                  continue
              break
    print(-1)
    return

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

Submission status: Wrong Answer

Solution code:
from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]


q = [(0<<128)+(0<<96)+((x1-1)<<64)+((y1-1)<<32)+i for i in range(4)]
for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)


a = ((1<<128)+(4<<96)+(9<<64)) - (1<<128)
a >> 96
while q:
    v = heappop(q)
    count1 = v >> 128
    v -= count1<<128
    count2 = v >> 96
    v -= count2 << 96
    x = v >> 64
    v -= x << 64
    y = v >> 32
    v -= y << 32
    d = v
    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count2 == k-1:
                    nextcount = (count1+1, 0)
                else:
                    nextcount = (count1, count2+1)

                if dp[x+dx][y+dy][dd] > nextcount:
                    dp[x+dx][y+dy][dd] = nextcount
                    heappush(q, (nextcount[0]<<128)+(nextcount[1]<<96)+((x+dx)<<64)+((y+dy)<<32)+dd)
            else:
                nextcount = (count1+1, 0)
                if dp[x][y][dd] > nextcount:
                    dp[x][y][dd] = nextcount
                    heappush(q, (nextcount[0]<<128)+(nextcount[1]<<96)+(x<<64)+(y<<32)+dd)

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = [(y,x)]
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    while q:
      y,x = q.pop()
      if (y,x) == (s,t):
          print(d[s][t])
          return
      nd = d[y][x] + 1
      for dy,dx in dd:
          ny,nx = y,x
          for _ in range(k):
              ny += dy
              nx += dx
              if 0 <= ny < h and 0 <= nx < w and c[ny][nx] != "@" and nd < d[ny][nx]:
                  d[ny][nx] = nd
                  q.append((ny,nx))
                  continue
              break
    print(-1)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = [(y,x)]
    d = [[0]*w for i in range(h)]
    while q:
      i,j = q.pop()
      for dy,dx in dd:
          ny,nx = i+dy,j+dx
          if 0 <= ny < h and 0 <= nx < w:
              if c[ny][nx] != "@" and not d[ny][nx]:
                  d[ny][nx] = 1
                  q.append((ny,nx))
    if not d[ny][nx]:
        print(-1)
        return
    cost = 1/k
    d = defaultdict(lambda : float("inf"))
    for i in range(4):
        d[(y,x,i)] = 0
        q.append((0,y,x,i))

    while q:
        dyx,y,x,p = heappop(q)
        if (y,x) == (s,t):
            print(math.ceil(round(dyx,6)))
            return
        if d[(y,x,p)] < dyx:
            continue

        for i,(dy,dx) in enumerate(dd):
            if i == p:
                nd = dyx + cost
            else:
                nd = math.ceil(round(dyx,6)) + cost
            ny,nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if c[ny][nx] != "@":
                    if nd < d[(ny,nx,i)]:
                        d[(ny,nx,i)] = nd
                        heappush(q,(nd,ny,nx,i))
    return

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

Submission status: Wrong Answer

Solution code:
from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

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


while q:
    count, x, y, d = heappop(q)
    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

                if dp[x+dx][y+dy][dd] > nextcount:
                    dp[x+dx][y+dy][dd] = nextcount
                    heappush(q, (nextcount, x+dx, y+dy, dd))
            else:
                nextcount = (count[0]+1, 0)
                if dp[x][y][dd] > nextcount:
                    dp[x][y][dd] = nextcount
                    heappush(q, (nextcount, x, y, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1

print(ans)

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()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    cost = 1/k
    d = defaultdict(lambda : float("inf"))
    q = []
    for i in range(4):
        d[(y,x,i)] = 0
        q.append((0,y,x,i))

    while q:
        dyx,y,x,p = heappop(q)
        if (y,x) == (s,t):
            print(math.ceil(dyx))
            return
        if d[(y,x,p)] < dyx:
            continue

        for i,(dy,dx) in enumerate(dd):
            if i == p:
                nd = dyx + cost
            else:
                nd = math.ceil(dyx) + cost
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if c[ny][nx] != "@":
                    if nd < d[(ny,nx,i)]:
                        d[(ny,nx,i)] = nd
                        heappush(q,(nd,ny,nx,i))
    print(-1)
    return

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
X1, Y1, X2, Y2 = lr()
X1 -= 1; Y1 -= 1; X2 -= 1; Y2 -= 1
C = [sr() for _ in range(H)]
graph = [[] for _ in range((H*W)*4)]  # 0-indexed
for i in range(H):
    for j in range(W):
        pos = (W*i + j)*4
        left = False; right = False
        if C[i][j] == '@':
            continue
        if j == 0: left = True
        if j == W-1: right = True
        for con, dir in [(0, -4*W), (1, 4), (2, 4*W), (3, -4)]:
            # 0を上、1を右
            if left and con == 3: continue
            if right and con == 1: continue
            if 0 <= pos + con + dir < H*W*4:
                graph[pos + con].append(((pos+con+dir), 1))
        for con in range(4):
            graph[pos+con].append(((pos+(con+1)%4), -1))
            graph[pos+con].append(((pos+(con-1)%4), -1))
            graph[pos+con].append(((pos+(con+2)%4), -1))

INF = 10 ** 19

def dijkstra(start):
    dist = [INF] * H * W * 4
    que = [(0, start)]
    dist[start] = 0
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, dis in graph[prev]:
            if dis == -1:
                d1 = (d+K-1)//K * K
            else:
                d1 = d + dis
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

start = (W*X1+Y1)*4
dist = dijkstra(start)
goal = (W*X2 + Y2)*4
answer = min(dist[goal:goal+4])
answer = (answer+K-1) // K
print(answer if answer != INF // K else -1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
X1, Y1, X2, Y2 = lr()
X1 -= 1; Y1 -= 1; X2 -= 1; Y2 -= 1
C = [sr() for _ in range(H)]
graph = [[] for _ in range((H*W)*4)]  # 0-indexed
for i in range(H):
    for j in range(W):
        pos = (W*i + j)*4
        left = False; right = False
        if C[i][j] == '@':
            continue
        if j == 0: left = True
        if j == W-1: right = True
        for con, dir in [(0, -4*W), (1, 4), (2, 4*W), (3, -4)]:
            # 0を上、1を右
            if left and con == 3: continue
            if right and con == 1: continue
            if 0 <= pos + con + dir < H*W*4:
                graph[pos + con].append(((pos+con+dir), 1))
        for con in range(4):
            graph[pos+con].append(((pos+(con+1)%4), -1))
            graph[pos+con].append(((pos+(con-1)%4), -1))

INF = 10 ** 10

def dijkstra(start):
    dist = [INF] * H * W * 4
    que = [(0, start)]
    dist[start] = 0
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, dis in graph[prev]:
            if dis == -1:
                d1 = (d+K-1)//K * K
            else:
                d1 = d + dis
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

start = (W*X1+Y1)*4
dist = dijkstra(start)
goal = (W*X2 + Y2)*4
answer = min(dist[goal:goal+4])
answer = (answer+K-1) // K
print(answer if answer != INF // K else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

dD = [[10**13 for _ in range(w)] for _ in range(h)]
dU = [[10**13 for _ in range(w)] for _ in range(h)]
dR = [[10**13 for _ in range(w)] for _ in range(h)]
dL = [[10**13 for _ in range(w)] for _ in range(h)]
visitedD = [[False for _ in range(w)] for _ in range(h)]
visitedU = [[False for _ in range(w)] for _ in range(h)]
visitedR = [[False for _ in range(w)] for _ in range(h)]
visitedL = [[False for _ in range(w)] for _ in range(h)]

dD[x1][y1] = 0
dU[x1][y1] = 0
dR[x1][y1] = 0
dL[x1][y1] = 0
visitedD[x1][y1] = True
visitedU[x1][y1] = True
visitedR[x1][y1] = True
visitedL[x1][y1] = True

q = deque([((x1, y1), "D", 0), ((x1, y1), "U", 0),
           ((x1, y1), "R", 0), ((x1, y1), "L", 0)])

while q:
    v, direction, p = q.popleft()
    x = v[0]
    y = v[1]
    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and not visitedD[x+1][y] and direction == "D":
        if dD[x+1][y] > dD[x][y] + (p == 0):
            dD[x+1][y] = dD[x][y] + (p == 0)
            visitedD[x+1][y] = True
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.' and not visitedD[x+1][y]:
        if dD[x+1][y] > min(dR[x][y], dL[x][y]) + 1:
            visitedD[x+1][y] = True
            dD[x+1][y] = min(dR[x][y], dL[x][y]) + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and not visitedU[x-1][y] and direction == "U":
        if dU[x-1][y] > dU[x][y]+(p == 0):
            dU[x-1][y] = dU[x][y]+(p == 0)
            visitedU[x-1][y] = True
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.'and not visitedU[x-1][y]:
        if dU[x-1][y] > min(dR[x][y], dL[x][y]) + 1:
            visitedU[x-1][y] = True
            dU[x-1][y] = min(dR[x][y], dL[x][y]) + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and not visitedR[x][y+1] and direction == "R":
        if dR[x][y+1] > dR[x][y] + (p == 0):
            visitedR[x][y+1] = True
            dR[x][y+1] = dR[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and not visitedR[x][y+1]:
        if dR[x][y+1] > min(dD[x][y], dU[x][y]) + 1:
            visitedR[x][y+1] = True
            dR[x][y+1] = min(dD[x][y], dU[x][y]) + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and not visitedL[x][y-1] and direction == "L":
        if dL[x][y-1] > dL[x][y] + (p == 0):
            visitedL[x][y-1] = True
            dL[x][y-1] = dL[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and not visitedL[x][y-1]:
        if dL[x][y-1] > min(dD[x][y], dU[x][y]) + 1:
            visitedL[x][y-1] = True
            dL[x][y-1] = min(dD[x][y], dU[x][y]) + 1
            q.append(((x, y-1), "L", 1 % k))

ans = min(dD[x2][y2], dU[x2][y2], dR[x2][y2], dL[x2][y2])
print(-1 if ans == 10**13 else ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 >= reach[nx][ny]: #すでに余裕をもって到達済み
        break
      reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
      Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if 0<=nx<H and 0<=ny<W:
        if Pond[nx][ny] == "@": #一回蓮があったらその向きはもう無理
          break
        if reach[x][y]+1 < reach[nx][ny]:
          reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
          Q.append((nx,ny))
        if nx == gx and ny == gy:
          print(reach)
          print(reach[nx][ny])
          exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        oy,ox = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = oy,ox
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[oy][ox] <= dist[y][x]:
                    break
                if dist[y][x] < 0:
                    dist[y][x] = dist[oy][ox] + 1
                    q.append((y,x))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

dD = [[10**13 for _ in range(w)] for _ in range(h)]
dU = [[10**13 for _ in range(w)] for _ in range(h)]
dR = [[10**13 for _ in range(w)] for _ in range(h)]
dL = [[10**13 for _ in range(w)] for _ in range(h)]

dD[x1][y1] = 0
dU[x1][y1] = 0
dR[x1][y1] = 0
dL[x1][y1] = 0

q = deque([((x1, y1), "D", 0), ((x1, y1), "U", 0),
           ((x1, y1), "R", 0), ((x1, y1), "L", 0)])


while q:
    v, direction, p = q.popleft()
    if v == (x2, y2):
        continue
    x = v[0]
    y = v[1]
    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and direction == "D":
        if dD[x+1][y] > dD[x][y] + (p == 0):
            dD[x+1][y] = dD[x][y] + (p == 0)
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.':
        if dD[x+1][y] > dR[x][y] + 1:
            dD[x+1][y] = dR[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))
        if dD[x+1][y] > dL[x][y] + 1:
            dD[x+1][y] = dL[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and direction == "U":
        if dU[x-1][y] > dU[x][y]+(p == 0):
            dU[x-1][y] = dU[x][y]+(p == 0)
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.':
        if dU[x-1][y] > dR[x][y] + 1:
            dU[x-1][y] = dR[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))
        if dU[x-1][y] > dL[x][y] + 1:
            dU[x-1][y] = dL[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and direction == "R":
        if dR[x][y+1] > dR[x][y] + (p == 0):
            dR[x][y+1] = dR[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.':
        if dR[x][y+1] > dD[x][y] + 1:
            dR[x][y+1] = dD[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))
        if dR[x][y+1] > dU[x][y] + 1:
            dR[x][y+1] = dU[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and direction == "L":
        if dL[x][y-1] > dL[x][y] + (p == 0):
            dL[x][y-1] = dL[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.':
        if dL[x][y-1] > dD[x][y] + 1:
            dL[x][y-1] = dD[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))
        if dL[x][y-1] > dU[x][y] + 1:
            dL[x][y-1] = dU[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))

ans = min(dD[x2][y2], dU[x2][y2], dR[x2][y2], dL[x2][y2])
print(-1 if ans == 10**13 else ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

d = [[10**13 for _ in range(w)] for __ in range(h)]
d[x1][y1] = 0

q = deque([((x1, y1), "D", 0), ((x1, y1), "U", 0),
           ((x1, y1), "R", 0), ((x1, y1), "L", 0)])
while q:
    v, direction, p = q.popleft()
    if v == (x2, y2):
        continue
    x = v[0]
    y = v[1]

    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and direction == "D":
        if d[x+1][y] > d[x][y] + (p == 0):
            d[x+1][y] = d[x][y] + (p == 0)
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.':
        if d[x+1][y] > d[x][y] + 1:
            d[x+1][y] = d[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and direction == "U":
        if d[x-1][y] > d[x][y] + (p == 0):
            d[x-1][y] = d[x][y] + (p == 0)
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.':
        if d[x-1][y] > d[x][y] + 1:
            d[x-1][y] = d[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and direction == "R":
        if d[x][y+1] > d[x][y] + (p == 0):
            d[x][y+1] = d[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.':
        if d[x][y+1] > d[x][y] + 1:
            d[x][y+1] = d[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and direction == "L":
        if d[x][y-1] > d[x][y] + (p == 0):
            d[x][y-1] = d[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.':
        if d[x][y-1] > d[x][y] + 1:
            d[x][y-1] = d[x][y] + 1
            q.append(((x, y), "L", 1 % k))


print(-1 if d[x2][y2] == 10**13 else d[x2][y2])

Submission status: Wrong Answer

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 = [[-1] * W for _ in range(H)]

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