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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,m,k=map(int,input().split())
    x1,y1,x2,y2=[int(x)-1 for x in input().split()]
    a=[ [x!='.' for x in input()] for _ in range(n)]

    ans=[[1<<20]*m for _ in range(n)]
    dir=[(0,1),(0,-1),(1,0),(-1,0)]
    cst=-1
    cur={(x1,y1):True}
    while cur:
        dp={}
        nxt={}
        cst+=1
        # print(cst,cur)
        mvf={}
        for x,y in cur:
            # print(x,y)
            if a[x][y] or ans[x][y]<=cst:
                continue
            ans[x][y]=cst
            for i in range(len(dir)):
                mvf[(x,y,i)]=True
        # print("mvf",mvf)

        for _ in range(k):
            if not mvf:
                break
            # print("mvf",mvf)
            mvn={}
            for v in mvf:
                x,y=v[0]+dir[v[2]][0],v[1]+dir[v[2]][1]
                if 0>x or x>=n or 0>y or y>=m:
                    continue
                if a[x][y] or (x,y,v[2]) in dp:
                    continue

                dp[(x,y,v[2])]=True
                mvn[(x,y,v[2])]=True
                nxt[(x,y)]=True
            mvf=mvn

        cur=nxt
    # print(ans)
    print(-1 if ans[x2][y2]==(1<<20) else ans[x2][y2])
# region fastio

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
S = [input() for _ in range(H)]
from collections import deque

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

# 深さ優先探索
def bfs(x, y):
    stack = deque([[x, y]])
    cost[x][y] = 0
    while stack:
        x, y = stack[0]
        point = cost[x][y]
        # up
        for i in range(1, K+1):
            if x-i >= 0:
                if S[x-i][y] == "." and cost[x-i][y] == -1:
                    cost[x-i][y] = point+1
                    stack.append([x-i, y])
                elif S[x-i][y] == "@":
                    break
            else:
                break
        # down
        for i in range(1, K+1):
            if x+i < H:
                if S[x+i][y] == "." and cost[x+i][y] == -1:
                    cost[x+i][y] = point+1
                    stack.append([x+i, y])
                elif S[x+i][y] == "@":
                    break
            else:
                break
        # left
        for i in range(1, K+1):
            if y-i >= 0:
                if S[x][y-i] == "." and cost[x][y-i] == -1:
                    cost[x][y-i] = point+1
                    stack.append([x, y-i])
                elif S[x][y-i] == "@":
                    break
            else:
                break
        # right
        for i in range(1, K+1):
            if y+i < W:
                if S[x][y+i] == "." and cost[x][y+i] == -1:
                    cost[x][y+i] = point+1
                    stack.append([x, y+i])
                elif S[x][y+i] == "@":
                    break
            else:
                break

        stack.popleft()        

bfs(sx-1, sy-1)
print(cost[gx-1][gy-1])

Submission status: Time Limit Exceeded

Solution code:
import queue

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

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]


xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            if nx>=0 and nx<H and ny>=0 and ny<W and cnt[nx][ny]==10**10:
                if li[nx][ny]=="@":
                    # print(nx,ny)
                    break
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = [(x1-1,y1-1)]
step = 1

while len(que)>0:
  que_next = []
  for q in que:
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next.append((x-i,y))
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next.append((x+i,y))
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next.append((x,y-i))
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next.append((x,y+i))
  que = que_next
  for q in que:
    T[q[0]][q[1]] = 1
  step += 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append((sx,sy))
  while d:
    x,y=d.popleft()
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      b[x-i][y]=b[x][y]+1
      d.append((x-i,y))
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      b[x+i][y]=b[x][y]+1
      d.append((x+i,y))
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      b[x][y-j]=b[x][y]+1
      d.append((x,y-j))
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      b[x][y+j]=b[x][y]+1
      d.append((x,y+j))
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            for k in range(1, K+1):
                h2 = h + dh*k
                w2 = w + dw*k
                if grid[h2][w2] == '@':
                    break
                if dist[h2][w2] != INF:
                    continue
                dist[h2][w2] = dist[h][w] + 1
                que.append((h2, w2))
    return dist

H, W, K = MAP()
x1, y1, x2, y2 = MAP()
grid = build_grid(H, W, '@', str, space=0, padding=1)

res = bfs(grid, [(x1, y1)])
ans = res[x2][y2]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
sx,sy,tx,ty=map(int,input().split())
b=[[-1]*(w+2)]
for i in range(h):
  s=input()
  bb=[-1]
  for j in s:
    if j==".":bb.append(0)
    else:bb.append(-1)
  bb.append(-1)
  b.append(bb)
b.append([-1]*(w+2))
from collections import deque
d=deque()
d.append((sx,sy))
while d:
  x,y=d.popleft()
  if x==tx and y==ty:
    exit(print(b[x][y]))
  for i in range(1,k+1):
    if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
    b[x-i][y]=b[x][y]+1
    d.append((x-i,y))
  for i in range(1,k+1):
    if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
    b[x+i][y]=b[x][y]+1
    d.append((x+i,y))
  for j in range(1,k+1):
    if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
    b[x][y-j]=b[x][y]+1
    d.append((x,y-j))
  for j in range(1,k+1):
    if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
    b[x][y+j]=b[x][y]+1
    d.append((x,y+j))
print(-1)

Submission status: Time Limit Exceeded

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


def to_ind(i, j):
    return i * w + j

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 9

graph = [[] for i in range(h * w)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "@":
            continue
        for dj in range(1, k + 1):
            if not(0 <= j + dj < w):
                break
            if s[i][j + dj] == "@":
                break
            graph[to_ind(i, j)].append(to_ind(i, j + dj))
            graph[to_ind(i, j + dj)].append(to_ind(i, j))
        for di in range(1, k + 1):
            if not(0 <= i + di < h):
                break
            if s[i + di][j] == "@":
                break
            graph[to_ind(i, j)].append(to_ind(i + di, j))
            graph[to_ind(i + di, j)].append(to_ind(i, j))   

visited = [INF] * (h * w)
visited[to_ind(x1 - 1, y1 - 1)] = 0
q = deque([to_ind(x1 - 1, y1 - 1)])
while q:
    v = q.popleft()
    for nxt_v in graph[v]:
        if visited[nxt_v] <= visited[v] + 1:
            continue
        visited[nxt_v] = visited[v] + 1
        q.append(nxt_v)

if visited[to_ind(x2 - 1, y2 - 1)] == INF:
    print(-1)
else:
    print(visited[to_ind(x2 - 1, y2 - 1)])

Submission status: Time Limit Exceeded

Solution code:
import heapq

H, W, K=map(int, input().split())
x1, y1, x2, y2=map(int, input().split())
c=['@'*(W+2)]+['@'+input()+'@' for _ in range(H)]+['@'*(W+2)]
l=[[-2]*(W+2) for _ in range(H+2)]
q=[[0, x1, y1]]

heapq.heapify(q)

while q:
  tmp=heapq.heappop(q)
  l[tmp[1]][tmp[2]]=tmp[0]
  
  j=1
  while j<=K and c[tmp[1]-j][tmp[2]]=='.' and l[tmp[1]-j][tmp[2]]==-2:
    heapq.heappush(q, [tmp[0]+1, tmp[1]-j, tmp[2]])
    l[tmp[1]-j][tmp[2]]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]+j][tmp[2]]=='.':
    if l[tmp[1]+j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]+j, tmp[2]])
      l[tmp[1]+j][tmp[2]]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]][tmp[2]-j]=='.':
    if l[tmp[1]][tmp[2]-j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]-j])
      l[tmp[1]][tmp[2]-j]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]][tmp[2]+j]=='.':
    if l[tmp[1]][tmp[2]+j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]+j])
      l[tmp[1]][tmp[2]+j]=-1
    j+=1
    
  if l[x2][y2]>=0:
    print(l[x2][y2])
    exit()

if l[x2][y2]<0:
  print(-1)
else:
  print(l[x2][y2])

Submission status: Time Limit Exceeded

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

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]

from collections import deque

d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((x1,y1))
d[x1][y1]=0
# tmp_ans=-1
while queue:
    y,x=queue.popleft()
    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        cnt_k=0
        while cnt_k<k:
            if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
                break
            if c[new_y][new_x]=='.' and (d[new_y][new_x]==-1 or d[new_y][new_x]==d[y][x]+1):
                d[new_y][new_x]=d[y][x]+1
                queue.append((new_y, new_x))
                new_y=new_y+d_y
                new_x=new_x+d_x
                cnt_k+=1
            else:
                break

print(d[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**7
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	if i == gh and j == gw:
		print(dist[i][j])
		sys.exit()
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "." and dist[ii][jj] > dist[i][j]:
				dist[ii][jj] = dist[i][j] + 1
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6):
    next = deque()
    while now:
        y,x = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        for i in range(1,k+1):
            if y-i < 0 or map[y-i][x] == "@":
                break
            else:
                if gone[y-i][x] == 0:
                    gone[y-i][x] = 1
                    next.append((y-i,x))
        for i in range(1,k+1):
            if y +i >= h or map[y+i][x] == "@":
                break
            else:
                if gone[y + i][x] == 0:
                    gone[y + i][x] = 1
                    next.append((y+i,x))
        for i in range(1,k+1):
            if x - i < 0 or map[y][x-i] == "@":
                break
            else:
                if gone[y][x-i] == 0:
                    gone[y][x-i] = 1
                    next.append((y,x-i))
        for i in range(1, k + 1):
            if x+i >= w or map[y][x+i] == "@":
                break
            else:
                if gone[y][x+i] == 0:
                    gone[y][x+i] = 1
                    next.append((y,x+i))
    if next == deque():
        print(-1)
        exit()
    now = next
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

x_1, y_1, x_2, y_2 = map(int, input().split())

pond_map = [input() for i in range(h)]

seen = set()

seen.add((x_1, y_1))

d = deque()

d.append((x_1, y_1, 0))

answer = -1

get_answer = False

while len(d) != 0:
    now_pos = d.popleft()
    for i in range(k):
        next_pos = (now_pos[0], now_pos[1] + i + 1, now_pos[2] + 1)
        if next_pos[1] > w:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] not in seen:
            seen.add(next_pos[:2])
            d.append(next_pos)
    if get_answer:
        break

    for i in range(k):
        next_pos = (now_pos[0], now_pos[1] - i - 1, now_pos[2] + 1)
        if next_pos[1] < 1:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] not in seen:
            seen.add(next_pos[:2])
            d.append(next_pos)
    if get_answer:
        break

    for i in range(k):
        next_pos = (now_pos[0] + 1 + i, now_pos[1], now_pos[2] + 1)
        if next_pos[0] > h:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] not in seen:
            seen.add(next_pos[:2])
            d.append(next_pos)
    if get_answer:
        break

    for i in range(k):
        next_pos = (now_pos[0] - i - 1, now_pos[1], now_pos[2] + 1)
        if next_pos[0] < 1:
            break
        if next_pos[:2] == (x_2, y_2):
            answer = now_pos[2] + 1
            get_answer = True
            break
        if pond_map[next_pos[0] - 1][next_pos[1] - 1] == '@':
            seen.add(next_pos[:2])
            break
        if next_pos[:2] not in seen:
            seen.add(next_pos[:2])
            d.append(next_pos)
    if get_answer:
        break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
r, c, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
C = [input() for _ in range(r)]

from collections import deque

q = deque()
D = [[0]*c for _ in range(r)]
ans = []
q.append((sx-1, sy-1))
D[sx-1][sy-1] = 1

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

while q:
    x, y = q.popleft()
    for dx, dy in dxy:
        for i in range(1, k+1):
            _x, _y = x + dx*i, y + dy*i
            if 0<=_x<r and 0<=_y<c and D[_x][_y] in [0, D[x][y] + 1] and C[_x][_y] == '.':
                D[_x][_y] = D[x][y] + 1
                q.append((_x, _y))
                if _x == gx-1 and _y == gy-1:
                    print(D[gx-1][gy-1]-1)
                    exit()
            else:
                break

print(D[gx-1][gy-1]-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
C = [None for i in range(H)]
for i in range(H):
    C[i] = input()
B = [[10**6 for i in range(W)] for j in range(H)]
B[x1-1][y1-1] = 0
A = [[x1-1,y1-1]]
while(A):
    a,b = A.pop()
    for i in range(a,min(a+1+K,H)):
        if C[i][b] == "@":
            break
        else:
            if B[i][b] > B[a][b]:
                B[i][b] = B[a][b] + 1
                A.append([i,b])
    for i in range(a,max(a-1-K,-1),-1):
        if C[i][b] == "@":
            break
        else:
            if B[i][b] > B[a][b]:
                B[i][b] = B[a][b] + 1
                A.append([i,b])
    for j in range(b,min(b+1+K,W)):
        if C[a][j] == "@":
            break
        else:
            if B[a][j] > B[a][b]:
                B[a][j] = B[a][b] + 1
                A.append([a,j])
    for j in range(b,max(b-1-K,-1),-1):
        if C[a][j] == "@":
            break
        else:
            if B[a][j] > B[a][b]:
                B[a][j] = B[a][b] + 1
                A.append([a,j])
if B[x2-1][y2-1] == 10**6:
    print(-1)
else:
    print(B[x2-1][y2-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l #改行して条件文を続けるときにバックスラッシュ
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**7
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append((sh, sw))
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	i, j = q.popleft()
	if i == gh and j == gw:
		print(dist[i][j])
		sys.exit()
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "." and dist[ii][jj] > dist[i][j]:
				dist[ii][jj] = dist[i][j] + 1
				q.append((ii, jj))
			else:
				break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx))
gone[sy][sx] = 1
for ans in range(10 ** 6):
    next = deque()
    while now:
        y,x = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        for i in range(1,k+1):
            if y-i < 0 or map[y-i][x] == "@":
                break
            else:
                if gone[y-i][x] == 0:
                    gone[y-i][x] = 1
                    next.append((y-i,x))
        for i in range(1, k + 1):
            if y +i >= h or map[y + i][x] == "@":
                break
            else:
                if gone[y + i][x] == 0:
                    gone[y + i][x] = 1
                    next.append((y+i,x))
        for i in range(1, k + 1):
            if x - i < 0 or map[y][x-i] == "@":
                break
            else:
                if gone[y][x-i] == 0:
                    gone[y][x-i] = 1
                    next.append((y,x-i))
        for i in range(1, k + 1):
            if x+i >= w or map[y][x+i] == "@":
                break
            else:
                if gone[y][x+i] == 0:
                    gone[y][x+i] = 1
                    next.append((y,x+i))
    if next == deque():
        print(-1)
        exit()
    now = next
print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    l = []
    v = [[0] * W for _ in range(H)]
    v[x1-1][y1-1] = 1
    for _ in range(H):
        c = input()
        l.append(c)
    cur = [(x1-1, y1-1)]
    r = 0
    while cur:
        r += 1
        nex = set()
        for x, y in cur:
            # north
            i = 1
            while x-i > -1 and i <= K:
                a, b = x-i, y
                if a == x2-1 and b == y2-1:
                    return r
                if l[x-i][y] == '.' and v[x-i][y] == 0:
                    v[x-i][y] = 1
                    nex.add((x-i, y))
                if l[x-i][y] == '@':
                    break
                i += 1
            # south
            i = 1
            while x+i < H and i <= K:
                a, b = x+i, y
                if a == x2-1 and b == y2-1:
                    return r
                if l[x+i][y] == '.' and v[x+i][y] == 0:
                    v[x+i][y] = 1
                    nex.add((x+i, y))
                if l[x+i][y] == '@':
                    break
                i += 1
            # west
            i = 1
            while y-i > -1 and i <= K:
                a, b = x, y-i
                if a == x2-1 and b == y2-1:
                    return r
                if l[x][y-i] == '.' and v[x][y-i] == 0:
                    v[x][y-i] = 1
                    nex.add((x, y-i))
                if l[x][y-i] == '@':
                    break
                i += 1
            # south
            i = 1
            while y+i < W and i <= K:
                a, b = x, y+i
                if a == x2-1 and b == y2-1:
                    return r
                if l[x][y+i] == '.' and v[x][y+i] == 0:
                    v[x][y+i] = 1
                    nex.add((x, y+i))
                if l[x][y+i] == '@':
                    break
                i += 1
        cur = nex
        if not cur:
            return -1
    return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
sy, sx, gy, gx = LI()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
grid = SRL(h)

def solve():
    min_cost = [[INF] * w for _ in range(h)]
    min_cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for l in range(1, k + 1):
                ny = cy + i * l
                nx = cx + j * l
                if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == '.':
                    if grid[ny][nx] == '.':
                        if min_cost[cy][cx] + 1 <= min_cost[ny][nx]:
                            min_cost[ny][nx] = min_cost[cy][cx] + 1
                            que += [(ny, nx)]
                        else:
                            break
                else:
                    break
    return min_cost

ans = solve()[gy][gx]
if ans == INF:
    print(-1)
else:
    print(ans)