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:
#import time 
#it = time.time()
from heapq import heapify,heappush,heappop
import sys

def conv_4(s):
  return [s,s,s,s]

H, W, K = map(int,input().split()) #南北、東西、可動範囲
xs, ys, xg, yg = map(int,input().split()) 

#グラフを作る　
graph0 = [[["@"]*4]*(W+2)]
graph1 = [[["@"]*4]+ list(map(conv_4, input())) +[["@"]*4] for _ in range(H)]
graph = graph0 + graph1 + graph0 #はすで囲まれた盤面

#or a in graph:
#  print(a)

#Dijkstra法による探索  頂点：（座標、向き(s0,n1,e2,w3)）

q=[]#未確定の頂点を格納しておく。
heappush(q,(1,0,(xs,ys,0))) #座標と向き(s0,n1,e2,w3)
heappush(q,(1,0,(xs,ys,1)))
heappush(q,(1,0,(xs,ys,2)))
heappush(q,(1,0,(xs,ys,3)))

cost=[[[(-1,0) for _ in range(4)] for _ in range(W+2)] for _ in range(H+2)]

# Dijkstra Loop
while True:
  while True:#未確定の点が取り出されるまで試す
    if len(q) == 0:
      break
    c, a, s = heappop(q)
    #print(q,graph[s[0]][s[1]][s[2]])
    if graph[s[0]][s[1]][s[2]] == ".":
      break
  #print(q)
  if (len(q) == 0) or ((s[0],s[1])==(xg,yg)):
    break#未確定要素がなくなったら終了
    
  cost[s[0]][s[1]][s[2]] = (c,a) #確定したコストの値を書き込む
  graph[s[0]][s[1]][s[2]] = "@"#確定させる場所にはすを置き、二度と訪れないようにする
  #print((c,a,s))
  #進行方向に移動する場合
  if s[2] == 0:#南向き
    s_next = (s[0]+1,s[1],0)
  if s[2] == 1:#北向き
    s_next = (s[0]-1,s[1],1)
  if s[2] == 2:#東向き
    s_next = (s[0],s[1]+1,2)
  if s[2] == 3:#にし向き
    s_next = (s[0],s[1]-1,3)
  if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
    if a < K:
      heappush(q,(c,a+1,s_next))#勢いを１失って、移動
    else:
      heappush(q,(c+1,1,s_next))#再び水を掻いて、移動
    
  #進行方向を変更する場合
  for d in range(3):#それぞれの向きについて
    s_next = (s[0],s[1],d)
    if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
      heappush(q,(c+1,0,s_next))#再び水を掻く。

#cost 出力
ans = -1
for i in range(3):
  if ans == -1 and cost[xg][yg][i][0] >= 0:
    ans = cost[xg][yg][i][0]
  elif ans >= 0 and cost[xg][yg][i][0] < ans:
    ans = cost[xg][yg][i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
#import time 
#it = time.time()
from heapq import heapify,heappush,heappop
import sys

def conv_4(s):
  return [s,s,s,s]

H, W, K = map(int,input().split()) #南北、東西、可動範囲
xs, ys, xg, yg = map(int,input().split()) 

#グラフを作る　
graph0 = [[["@"]*4]*(W+2)]
graph1 = [[["@"]*4]+ list(map(conv_4, input())) +[["@"]*4] for _ in range(H)]
graph = graph0 + graph1 + graph0 #はすで囲まれた盤面

#or a in graph:
#  print(a)

#Dijkstra法による探索  頂点：（座標、向き(s0,n1,e2,w3)）

q=[]#未確定の頂点を格納しておく。
heappush(q,(1,0,(xs,ys,0))) #座標と向き(s0,n1,e2,w3)
heappush(q,(1,0,(xs,ys,1)))
heappush(q,(1,0,(xs,ys,2)))
heappush(q,(1,0,(xs,ys,3)))

cost=[[[(-1,0) for _ in range(4)] for _ in range(W+2)] for _ in range(H+2)]

# Dijkstra Loop
while True:
  while True:#未確定の点が取り出されるまで試す
    if len(q) == 0:
      break
    c, a, s = heappop(q)
    #print(q,graph[s[0]][s[1]][s[2]])
    if graph[s[0]][s[1]][s[2]] == ".":
      break
  #print(q)
  if (len(q) == 0) or ((s[0],s[1])==(xg,yg)):
    break#未確定要素がなくなったら終了
    
  cost[s[0]][s[1]][s[2]] = (c,a) #確定したコストの値を書き込む
  graph[s[0]][s[1]][s[2]] = "@"#確定させる場所にはすを置き、二度と訪れないようにする
  #print((c,a,s))
  #進行方向に移動する場合
  if s[2] == 0:#南向き
    s_next = (s[0]+1,s[1],0)
  if s[2] == 1:#北向き
    s_next = (s[0]-1,s[1],1)
  if s[2] == 2:#東向き
    s_next = (s[0],s[1]+1,2)
  if s[2] == 3:#にし向き
    s_next = (s[0],s[1]-1,3)
  if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
    if a < K:
      heappush(q,(c,a+1,s_next))#勢いを１失って、移動
    else:
      heappush(q,(c+1,1,s_next))#再び水を掻いて、移動
    
  #進行方向を変更する場合
  for d in range(3):#それぞれの向きについて
    s_next = (s[0],s[1],d)
    if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
      heappush(q,(c+1,0,s_next))#再び水を掻く。

#cost 出力
ans = -1
for i in range(3):
  if ans == -1 and cost[xg][yg][i][0] > 0:
    ans = cost[xg][yg][i][0]
  elif ans >= 0 and cost[xg][yg][i][0] < ans:
    ans = cost[xg][yg][i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
#import time 
#it = time.time()
from heapq import heapify,heappush,heappop
import sys

def conv_4(s):
  return [s,s,s,s]

H, W, K = map(int,input().split()) #南北、東西、可動範囲
xs, ys, xg, yg = map(int,input().split()) 

#グラフを作る　
graph0 = [[["@"]*4]*(W+2)]
graph1 = [[["@"]*4]+ list(map(conv_4, input())) +[["@"]*4] for _ in range(H)]
graph = graph0 + graph1 + graph0 #はすで囲まれた盤面

#or a in graph:
#  print(a)

#Dijkstra法による探索  頂点：（座標、向き(s0,n1,e2,w3)）

q=[]#未確定の頂点を格納しておく。
heappush(q,(1,0,(xs,ys,0))) #座標と向き(s0,n1,e2,w3)
heappush(q,(1,0,(xs,ys,1)))
heappush(q,(1,0,(xs,ys,2)))
heappush(q,(1,0,(xs,ys,3)))

cost=[[[(-1,0) for _ in range(4)] for _ in range(W+2)] for _ in range(H+2)]

# Dijkstra Loop
while True:
  while True:#未確定の点が取り出されるまで試す
    if len(q) == 0:
      break
    c, a, s = heappop(q)
    #print(q,graph[s[0]][s[1]][s[2]])
    if graph[s[0]][s[1]][s[2]] == "." or len(q) == 0:
      break
  #print(q)
  if (len(q) == 0 ):
    break#未確定要素がなくなったら終了
    
  cost[s[0]][s[1]][s[2]] = (c,a) #確定したコストの値を書き込む
  graph[s[0]][s[1]][s[2]] = "@"#確定させる場所にはすを置き、二度と訪れないようにする
  #print((c,a,s))
  #進行方向に移動する場合
  if s[2] == 0:#南向き
    s_next = (s[0]+1,s[1],0)
  if s[2] == 1:#北向き
    s_next = (s[0]-1,s[1],1)
  if s[2] == 2:#東向き
    s_next = (s[0],s[1]+1,2)
  if s[2] == 3:#にし向き
    s_next = (s[0],s[1]-1,3)
  if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
    if a < K:
      heappush(q,(c,a+1,s_next))#勢いを１失って、移動
    else:
      heappush(q,(c+1,1,s_next))#再び水を掻いて、移動
    
  #進行方向を変更する場合
  for d in range(3):#それぞれの向きについて
    s_next = (s[0],s[1],d)
    if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
      heappush(q,(c+1,0,s_next))#再び水を掻く。

#cost 出力
ans = -1
for i in range(3):
  if ans == -1 and cost[xg][yg][i][0] > 0:
    ans = cost[xg][yg][i][0]
  elif ans >= 0 and cost[xg][yg][i][0] < ans:
    ans = cost[xg][yg][i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
#import time 
#it = time.time()
from heapq import heapify,heappush,heappop
import sys

def conv_4(s):
  return [s,s,s,s]

H, W, K = map(int,input().split()) #南北、東西、可動範囲
xs, ys, xg, yg = map(int,input().split()) 

#グラフを作る　
graph0 = [[["@"]*4]*(W+2)]
graph1 = [[["@"]*4]+ list(map(conv_4, input())) +[["@"]*4] for _ in range(H)]
graph = graph0 + graph1 + graph0 #はすで囲まれた盤面

#or a in graph:
#  print(a)

#Dijkstra法による探索  頂点：（座標、向き(s0,n1,e2,w3)）

q=[]#未確定の頂点を格納しておく。
heappush(q,(1,0,(xs,ys,0))) #座標と向き(s0,n1,e2,w3)
heappush(q,(1,0,(xs,ys,1)))
heappush(q,(1,0,(xs,ys,2)))
heappush(q,(1,0,(xs,ys,3)))

cost=[[[(10**20,0) for _ in range(4)] for _ in range(W+2)] for _ in range(H+2)]

# Dijkstra Loop
while True:
  while True:#未確定の点が取り出されるまで試す
    if len(q) == 0:
      break
    c, a, s = heappop(q)
    #print(q,graph[s[0]][s[1]][s[2]])
    if graph[s[0]][s[1]][s[2]] == "." or len(q) == 0:
      break
  #print(q)
  if (len(q) == 0 ):
    break#未確定要素がなくなったら終了
    
  cost[s[0]][s[1]][s[2]] = (c,a) #確定したコストの値を書き込む
  graph[s[0]][s[1]][s[2]] = "@"#確定させる場所にはすを置き、二度と訪れないようにする
  #print((c,a,s))
  #進行方向に移動する場合
  if s[2] == 0:#南向き
    s_next = (s[0]+1,s[1],0)
  if s[2] == 1:#北向き
    s_next = (s[0]-1,s[1],1)
  if s[2] == 2:#東向き
    s_next = (s[0],s[1]+1,2)
  if s[2] == 3:#にし向き
    s_next = (s[0],s[1]-1,3)
  if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
    if a < K:
      heappush(q,(c,a+1,s_next))#勢いを１失って、移動
    else:
      heappush(q,(c+1,1,s_next))#再び水を掻いて、移動
    
  #進行方向を変更する場合
  for d in range(3):#それぞれの向きについて
    s_next = (s[0],s[1],d)
    if graph[s_next[0]][s_next[1]][s_next[2]] == ".":
      heappush(q,(c+1,0,s_next))#再び水を掻く。

#cost 出力
ans = min(cost[xg][yg]) 
if ans[0] == 10**20:
  ans = (-1,0)
print(ans[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

try:
    profile
except:
    def profile(f): return f

DEBUG = False
if DEBUG:
    def dp(*x):  # debugprint
        print(*x)
else:
    def dp(*x): pass


@profile
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    mapdata = sys.stdin.buffer.read().splitlines()
    # print(data)
    start = (x1, y1)
    goal = (x2, y2)

    distances = defaultdict(lambda: (INF, 0))
    distances[(start, 0)] = (0, 0)
    shortest_path = {}
    shortest_path[(start, 0)] = None

    leaf = ord("@")

    queue = [((0, 0), (start, 0))]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), (frm, direction) = heappop(queue)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        if distances[(frm, direction)] < (d, frac):
            # already know shorter path
            continue
        if frm == goal:
            break

        x, y = frm
        # same direction
        # dp("direction", direction)
        dx, dy = DIRS[direction]
        nx = x + dx
        ny = y + dy
        if nx < 1 or H < nx or ny < 1 or W < ny:
            # dp("out of bounds")
            pass
        elif mapdata[nx - 1][ny - 1] == leaf:
            # dp("hit leaf")
            pass
        else:
            if frac == 0:
                newd = d + 1
                newfrac = -K + 1
            else:
                newd = d
                newfrac = frac + 1
            newdist = (newd, newfrac)
            to = ((nx, ny), direction)

            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm

        if direction < 2:
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if W < ny:
                # dp("out of bounds")
                continue
            # dp(nx, ny, mapdata[nx - 1][ny - 1])
            if mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                continue
            newdist = (d + 1, -K + 1)

            to = ((nx, ny), dir)
            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm

            dir = 3
            nx = x
            ny = y - 1
            if ny < 1:
                # dp("out of bounds")
                continue
            # dp(nx, ny, mapdata[nx - 1][ny - 1])
            if mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                continue
            newdist = (d + 1, -K + 1)

            to = ((nx, ny), dir)
            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm
        else:
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if H < nx:
                # dp("out of bounds")
                continue
            # dp(nx, ny, mapdata[nx - 1][ny - 1])
            if mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                continue
            newdist = (d + 1, -K + 1)

            to = ((nx, ny), dir)
            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm

            dir = 1
            nx = x - 1
            ny = y
            if nx < 1:
                # dp("out of bounds")
                continue
            # dp(nx, ny, mapdata[nx - 1][ny - 1])
            if mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                continue
            newdist = (d + 1, -K + 1)

            to = ((nx, ny), dir)
            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm

        # dp("distances", distances)

    dist = min(distances[(goal, dir)] for dir in range(4))
    if dist[0] == INF:
        # unreachable
        print(-1)
    else:
        print(dist[0])


main()

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m,k=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    ar=[]
    ans=[]
    #visited=[]
    for i in range(n):
        #visited.append([False]*m)
        ar.append(input())
        ans.append([0]*m)

    if(ar[x1-1][y1-1]=='@' or ar[x2-1][y2-1]=='@'):
        print(-1)
    q=[(x1-1,y1-1)]
    br=[(-1,0),(1,0),(0,1),(0,-1)]
    while(q):
        a,b=q.pop(0)
        #print(a,b)
        if(a==x2-1 and b==y2-1):
            print(ans[a][b])
            exit()
        for p,r in br:
            for i in range(1,k+1):
                x=a+i*p
                y=b+i*r
                if not (0<=x<n and 0<=y<m) or ar[x][y]=='@':
                    break
                if(0<ans[x][y]<=ans[a][b]+1):
                    break

                ans[x][y]=ans[a][b]+1
                q.append((x,y))
    print(-1)







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

try:
    profile
except:
    def profile(f): return f

DEBUG = False
if DEBUG:
    def dp(*x):  # debugprint
        print(*x)
else:
    def dp(*x): pass


@profile
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    mapdata = sys.stdin.buffer.read().splitlines()
    # print(data)
    start = (x1, y1)
    goal = (x2, y2)

    distances = defaultdict(lambda: (INF, 0))
    distances[(start, 0)] = (0, 0)
    shortest_path = {}
    shortest_path[(start, 0)] = None

    leaf = ord("@")

    queue = [((0, 0), (start, 0))]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), (frm, direction) = heappop(queue)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        if distances[(frm, direction)] < (d, frac):
            # already know shorter path
            continue
        if frm == goal:
            break

        x, y = frm
        # same direction
        # dp("direction", direction)
        dx, dy = DIRS[direction]
        nx = x + dx
        ny = y + dy
        if nx < 1 or H < nx or ny < 1 or W < ny:
            # dp("out of bounds")
            pass
        elif mapdata[nx - 1][ny - 1] == leaf:
            # dp("hit leaf")
            pass
        else:
            if frac == 0:
                newd = d + 1
                newfrac = -K + 1
            else:
                newd = d
                newfrac = frac + 1
            newdist = (newd, newfrac)
            to = ((nx, ny), direction)

            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm

        for dir in range(4):
            if dir == direction:
                continue
            # dp("dir", dir)
            dx, dy = DIRS[dir]
            # dp("dx, dy", dx, dy)
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)

            if nx < 1 or H < nx or ny < 1 or W < ny:
                # dp("out of bounds")
                continue
            dp(nx, ny, mapdata[nx - 1][ny - 1])
            if mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                continue
            newdist = (d + 1, -K + 1)

            to = ((nx, ny), dir)
            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm
        # dp("distances", distances)

    dist = min(distances[(goal, dir)] for dir in range(4))
    if dist == INF:
        # unreachable
        print(-1)
    else:
        print(dist[0])

        # path = []
        # cur = goal
        # while True:
        #     frm = shortest_path[cur]
        #     path.append(frm)
        #     cur = frm
        #     if frm == start:
        #         break
        # path.reverse()
        # print(len(path))  # edge count
        # for (frm, to) in path:
        #     print(frm, to)


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

H,W,K = LI()
x1,y1,x2,y2 = LI()
c = [list(map(str,input())) for _ in range(H)]

def grid_bfs(S,s,default=-1):
    dist = [[default]*W for _ in range(H)]
    can_visit_mark = ['.']
    if S[s[0]][s[1]] not in can_visit_mark:
        return dist
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    dist[s[0]][s[1]] = 0
    q = [s]
    counter = 1
    while q:
        q1 = []
        for now in q:
            for delta in d:
                for i in range(1,K+1):
                    new = (now[0]+i*delta[0], now[1]+i*delta[1])
                    if 0 <= new[0] <= H-1 and 0 <= new[1] <= W-1:
                        if S[new[0]][new[1]] in can_visit_mark:  
                            if dist[new[0]][new[1]] == default:
                                dist[new[0]][new[1]] = counter
                                q1.append(new)
                            else:
                                break
                        else:
                            break
                    else:
                        break
        if dist[x2-1][y2-1] != default:
            return dist[x2-1][y2-1]
        q = q1
        counter += 1
    return -1

print(grid_bfs(c,(x1-1,y1-1),default=-1))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
n = h*w
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = divmod(v, w)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            for a in range(1, k+1):
                x, y = i+di*a, j+dj*a
                if x < 0 or h <= x or y < 0 or w <= y:
                    break
                v2 = x*w+y
                if fld[v2] == '@':
                    break
                if dist[v2] <= dist[v]+1:
                    break
                dist[v2] = dist[v]+1
                next_v.append(v2)
    return dist


dist = bfs(x1*w+y1)
ans = dist[x2*w+y2]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
n = h*w
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = divmod(v, w)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            for a in range(1, k+1):
                x, y = i+di*a, j+dj*a
                if x < 0 or h <= x or y < 0 or w <= y:
                    continue
                v2 = x*w+y
                if fld[v2] == '@':
                    break
                if dist[v2] <= dist[v]+1:
                    break
                dist[v2] = dist[v]+1
                next_v.append(v2)
    return dist


dist = bfs(x1*w+y1)
ans = dist[x2*w+y2]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()
INF = 10**18
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    C = [list(input()) for _ in range(H)]

    """
    まずはKの制約がない時を考える。単純なBFSでは明らかに間に合わないが、
    「位置」と「向き」の直積を頂点として扱うのがポイント。
    隣の頂点に同じ向きで移動するのにコスト0、同じ頂点で向きを変えるのにコスト1かかるとして
    辺を張れば、ダイクストラにより計算量O((4HW + 4HW) * log(4HW))で解ける。

    ではKの制約がある時はどうするかというと、コストを(従来のコスト, 直線移動距離)のペアに変更する。
    直線移動距離がKを超えたら従来のコストを１つ繰り上げる。
    このペアによるコストは辞書式順序により全順序構造を持つので同様にダイクストラで扱える。

    さらに実はこのコストはペアで扱わないにすることもでき、
        直線移動のコスト＝1/K
        方向転換のコスト＝切り上げ
    と定めると整数部分が本問で求めるコストになっている。
    少数は少し怖いので実際にはK倍して扱う。
    """

    # 向き付き2次元配列を１次元に押し込める補助関数を用意
    def toId(i, j, v):
        return (i * W + j) * 4 + v

    dist = [INF] * (H * W * 4)
    q = []

    # ダイクストラ更新１回分の補助関数
    def push(i, j, v, x):
        id = toId(i, j, v)
        if dist[id] <= x: return
        dist[id] = x
        heappush(q, (x, id))

    # ダイクストラ
    for v in range(4): push(x1, y1, v, 0)
    while q:
        x, id = heappop(q)
        if dist[id] != x: continue # 途中で値が書き換わっていたら伝搬は無効化する！
        i, j, v = (id // 4) // W, (id // 4) % W, id % 4
        # 方向転換
        push(i, j, (v + 1) % 4, (x + K - 1) // K * K)
        push(i, j, (v + 2) % 4, (x + K - 1) // K * K)
        push(i, j, (v + 3) % 4, (x + K - 1) // K * K)
        # 直進
        ni, nj = i + di[v], j + dj[v]
        if 0 <= ni < H and 0 <= nj < W and C[ni][nj] == '.':
            push(ni, nj, v, x + 1)
    ans = min(dist[toId(x2, y2, k)] for k in range(4))
    ans = (ans + K - 1) // K
    if ans == INF: print(-1)
    else :print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 10
# INF = float("inf")

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
map = sys.stdin.buffer.read().splitlines()
# print(data)
start = (x1, y1)
goal = (x2, y2)

distances = defaultdict(lambda: INF)
distances[start] = 0
shortest_path = {}
shortest_path[start] = None

maxdist = max(H, W)

leaf = ord("@")


def neighbor(frm):
    "return (to, cost)"
    x, y = frm
    # print("frm", frm)
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x
        ny = y
        for dist in range(1, maxdist):
            nx += dx
            ny += dy
            if nx < 1 or H < nx or ny < 1 or W < ny:
                # print("out of bounds")
                break
            # print(nx, ny, data[nx - 1][ny - 1])
            if map[nx - 1][ny - 1] == leaf:
                # print("hit leaf")
                break
            cost = (dist - 1) // K + 1
            yield ((nx, ny), cost)


queue = [(0, start)]
while queue:
    d, frm = heappop(queue)
    if distances[frm] < d:
        # already know shorter path
        continue
    if frm == goal:  # goal
        break
    for to, cost in neighbor(frm):
        if distances[to] > distances[frm] + cost:
            # found shorter path
            distances[to] = distances[frm] + cost
            heappush(queue, (distances[to], to))
            shortest_path[to] = frm
    # print(distances)

if distances[goal] == INF:
    # unreachable
    print(-1)
else:
    path = []
    cur = goal
    while True:
        frm = shortest_path[cur]
        path.append(frm)
        cur = frm
        if frm == start:
            break
    path.reverse()
    print(len(path) + 1)
    if 0:
        for (frm, to) in path:
            print(frm, to)

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()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
                else:
                    break
            else:
                break
print(-1)

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()
maze = [input() for _ in range(H)]
dp = [[(10**10, 0, 0)] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
h = []
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = (0, 0, -1)
while que:
    y, x = que.popleft()
    dist_xy, use_xy, direct_xy = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist_xy)
        quit()
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < H and 0 <= nx < W:
            if maze[ny][nx] == '@':
                continue
            dist_nxny, use_nxny, direct_nxny = dp[ny][nx]
            if i == direct_xy and use_xy < k:
                if dist_xy < dist_nxny:
                    dp[ny][nx] = (dist_xy, use_xy + 1, i)
                    que.appendleft((ny, nx))
                elif dist_xy == dist_nxny:
                    if use_xy + 1 < use_nxny:
                        dp[ny][nx] = (dist_xy, use_xy + 1, i)
                        que.appendleft((ny, nx))
            elif i == direct_xy and use_xy == k:
                if dist_xy + 1 < dist_nxny:
                    dp[ny][nx] = (dist_xy + 1, 1, i)
                    que.appendleft((ny, nx))
            elif i != direct_xy:
                if dist_xy + 1 < dist_nxny:
                    dp[ny][nx] = (dist_xy + 1, 1, i)
                    que.appendleft((ny, nx))
print(-1)