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:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())

    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    # ヒープでなくて良い。
    # 高々1しか加わっていかないため、キューに加えられた順で十分昇順になる。
    Q = []
    Q.append((0, x1, y1, 0))
    Q.append((0, x1, y1, 1))
    Q.append((0, x1, y1, 2))
    Q.append((0, x1, y1, 3))
    i = 0
    while i < len(Q):
        curr, x, y, DXY = Q[i]
        dx, dy = DX[DXY], DY[DXY]
        for k in range(1, K+1):
            X, Y = x+k*dx, y+k*dy
            if not (0 <= X < H) or not (0 <= Y < W):
                break
            if 0 < dist[X][Y] < curr+1:
                break
            if dist[X][Y] == curr+1:
                continue
            if c[X][Y] == "@":
                break
            dist[X][Y] = curr+1
            Q.append((curr+1, X, Y, (DXY+1) % 4))
            Q.append((curr+1, X, Y, (DXY-1) % 4))
        else:
            Q.append((curr+1, X, Y, DXY))
        if 0 < dist[x2][y2]:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__


h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

que = [(sx,sy)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
for x,y in que:
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

que = [(sx,sy)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
for x,y in que:
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            # コストが変わらない場合は無視か...
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split());b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0;d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=j:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


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

Submission status: Accepted

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

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
# リストの両端の要素に対する編集が必要
# 同一方向に進むときは移動回数が増えないためリストのの先頭に挿入
# この仕組みを実装するためdequeを読み込み

H, W, K = map(int, input().split())
# HとWとKの値それぞれを取得

x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
# リストの先頭要素は0番目として数えられる
# 座標のそれぞれの値から1を引いて取得

grid = [input() for _ in range(H)]
# グリッド部分をH行にわたって取得

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]
# 無限大の浮動小数点を管理

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 進行方向を座標で管理

q = deque()
for d in range(4):
	path[x1][y1][d] = (1, 0)
	# スタート地点を(1, 0)に設定
	q.append((x1, y1, d, 1, 0))
	# (x, y, 進行方向, 移動回数, 進行済マス数)を要素に追加

while q:
	x, y, d, c, k = q.popleft()
	#要素の削除
	
	# nx, ny: 次の座標
	# nd: 次の進行方向
	# nc: 次の移動回数
	# nk: 次の進行済マス数
	
	for nd in range(4):
		if nd == d:
			dx, dy = D[nd]
			nk = 1 if k == K else k + 1
			nc = c + 1 if k == K else c
		else:
			dx, dy = 0, 0
			nk = 0
			nc = c + 1
		nx = x + dx; ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (nc, nk):
			path[nx][ny][nd] = (nc), (nk)
			if nc == c:
				q.appendleft((nx, ny, nd, nc, nk))
			else:
				q.append((nx, ny, nd, nc, nk))
				
# コストの算出
ans = INF
for d in range(4):
	ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

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

queue = deque([(y1-1, x1-1)])
def bfs(queue):
    while len(queue):
        y, x = queue.popleft()
        if y==y2-1 and x==x2-1:
            return checked[y][x]
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    break
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    checked[ny][nx] = checked[y][x]+1
                    queue.append((ny, nx))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

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

queue = deque([(y1-1, x1-1)])
def bfs(queue):
    while queue:
        y, x = queue.popleft()
        if y==y2-1 and x==x2-1:
            return checked[y][x]
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    checked[ny][nx] = checked[y][x]+1
                    queue.append((ny, nx))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))

Submission status: Accepted

Solution code:
#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])
 
field.append(lastraw)
 
#print(field)
 
goal_point=(y2,x2)
 
[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]
 
field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0
 
while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.':
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            k=0
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            k=0
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)

Submission status: Accepted

Solution code:
#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.':
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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

    q = [(0, s, 0)]
    while q:
        cost, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = -1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            nc = cost + 1 if di == direction else ceiling
            if nc == -1:
                nc = ceiling = ((cost - 1) // k + 1) * k + 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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

    q = [(0, s, 0)]
    while q:
        cost, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            nc = cost + 1 if di == direction else ceiling
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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

    q = [(0, 0, s, 0)]
    while q:
        cost, straight, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            if di == direction:
                nc = cost + 1
                ns = straight + 1
                if ns > k:
                    ns -= k
            else:
                nc = ceiling
                ns = 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, ns, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Submission status: Accepted

Solution code:
import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(1,k+1):
    if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
      if cost[y][x+i]>c+1:
        cost[y][x+i]=c+1
        q.append((x+i,y))
    else:
      break
  for i in range(1,k+1):
    if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
      if cost[y][x-i]>c+1:
        cost[y][x-i]=c+1
        q.append((x-i,y))
    else:
      break
  for i in range(1,k+1):
    if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
      if cost[y+i][x]>c+1:
        cost[y+i][x]=c+1
        q.append((x,y+i))
    else:
      break
  for i in range(1,k+1):
    if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
      if cost[y-i][x]>c+1:
        cost[y-i][x]=c+1
        q.append((x,y-i))
    else:
      break
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

Submission status: Accepted

Solution code:
import collections
import sys
input=sys.stdin.readline

def calc():
  h,w,k=map(int,input().split())
  sy,sx,gy,gx=map(int,input().split())
  sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
  board=[input() for _ in range(h)]
  q=collections.deque()
  q.append((sx,sy))
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  while len(q)!=0:
    x,y=q.popleft()
    c=cost[y][x]
    for i in range(1,k+1):
      if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
        if cost[y][x+i]>c+1:
          cost[y][x+i]=c+1
          q.append((x+i,y))
      else:
        break
    for i in range(1,k+1):
      if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
        if cost[y][x-i]>c+1:
          cost[y][x-i]=c+1
          q.append((x-i,y))
      else:
        break
    for i in range(1,k+1):
      if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
        if cost[y+i][x]>c+1:
          cost[y+i][x]=c+1
          q.append((x,y+i))
      else:
        break
    for i in range(1,k+1):
      if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
        if cost[y-i][x]>c+1:
          cost[y-i][x]=c+1
          q.append((x,y-i))
      else:
        break
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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

    q = [(0, s, 0, k)]
    while q:
        cost, v, direction, remaining = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            if di == direction and remaining > 0:
                nc = cost + 1
                nr = remaining - 1
            else:
                nc = ceiling
                nr = k - 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di, nr))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=set([])

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            if (x,y+i) not in nx:
                nx.add((x,y+i))
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            if (x,y-i) not in nx:
                nx.add((x,y-i))
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            if (x+i,y) not in nx:
                nx.add((x+i,y))
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            if (x-i,y) not in nx:
                nx.add((x-i,y))
            i+=1

    return 0

C[x1-1][y1-1]=0
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=set([])
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = (i-1 for i in map(int,input().split()))
grid = []
inf = 1<<30
reach = [[inf for _ in range(W)] for _ in range(H)]
reach[sx][sy]=0
dif = [(1,0),(-1,0),(0,1),(0,-1)] #向かう方向

for i in range(H):
    grid.append(list(input()))

que = deque([(sx,sy)])
while que:
    x,y = que.popleft()
    for i in range(4): #方向決め
        for k in range(1,K+1):
            nx = x+k*dif[i][0]
            ny = y+k*dif[i][1]
            if nx<0 or nx>=H or ny<0 or ny>= W or grid[nx][ny] == "@":
                break
            if reach[x][y]+1 > reach[nx][ny]:
                break
            if reach[x][y]+1 < reach[nx][ny]:
                reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
                que.append((nx,ny))
            if nx == gx and ny == gy:
                print(reach[nx][ny])
                exit()
print(-1)

Submission status: Accepted

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()
SX, SY, GX, GY = lr()
SX -= 1; SY -= 1; GX -= 1; GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10

def to_ID(x, y, con):
    return (x*W + y) * 4 + con

def mod_ceil_K(x):
    return (x+K-1) // K * K

def push(d, id):
    if dist[id] < d:
        return
    dist[id] = d
    heappush(que, (d, id))    

dist = [INF] * (H*W*4)
start = to_ID(SX, SY, 0)
dist[start] = 0
que = [(0, start)]
UDLR = [(0, -1), (1, 0), (0, 1), (-1, 0)]
goal = to_ID(GX, GY, 0)
while que:
    d, id = heappop(que)
    if id == goal:
        answer = mod_ceil_K(d) // K
        print(answer); exit()
    if dist[id] < d:
        continue
    x = id // 4 // W
    y = id // 4 % W
    con = id % 4
    for i in range(4):
        next_id = to_ID(x, y, i)
        if dist[next_id] > mod_ceil_K(d):
            push(mod_ceil_K(d), next_id)
    dx = UDLR[con][0]; dy = UDLR[con][1]
    nx = x + dx; ny = y + dy
    if not (0 <= nx < H and 0 <= ny < W) or pond[nx][ny] == '@':
        continue
    next_id = to_ID(nx, ny, con)
    if dist[next_id] > d + 1:
        dist[next_id] = d + 1
        push(d+1, next_id)
    
print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import deque

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

H, W, K = lr()
SX, SY, GX, GY = lr()
SX -= 1; SY -= 1; GX -= 1; GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10
dist = [[INF] * W for _ in range(H)]
dist[SX][SY] = 0
que = deque([(0, SX, SY)])
UDLR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    d, px, py = que.popleft()
    if px == GX and py == GY:
        print(d); exit()
    if dist[px][py] < d:
        continue
    nd = d + 1
    for dx, dy in UDLR:
        nx = px + dx; ny = py + dy
        for _ in range(K):
            if not (0 <= nx < H) or not (0 <= ny < W) \
                    or dist[nx][ny] < nd or pond[nx][ny] == '@':
                break
            if dist[nx][ny] > nd:
                que.append((nd, nx, ny))
                dist[nx][ny] = nd
            nx += dx; ny += dy

print(-1)