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:
#!python3

from collections import deque

LI = lambda: list(map(int, input().split()))

# input
H, W, K = LI()
x1, y1, x2, y2 = LI()
C = [input() for _ in range(H)]

w = [[None] * W for _ in range(H)]
dq = deque([])


def main():
    w[x1 - 1][y1 - 1] = 0
    # cost, x, y
    dq.append((1, x1 - 1, y1 - 1))
    while dq:
        c, x, y = dq.popleft()
        # 上
        for i in range(1, min(K + 1, x + 1)):
            if w[x - i][y] is not None and w[x - i][y] < c:
                break
            if C[x - i][y] == "@":
                break
            w[x - i][y] = c
            dq.append((c + 1, x - i, y))
        # 下
        for i in range(1, min(K + 1, H - x)):
            if w[x + i][y] is not None and w[x + i][y] < c:
                break
            if C[x + i][y] == "@":
                break
            w[x + i][y] = c
            dq.append((c + 1, x + i, y))
        # 左
        for i in range(1, min(K + 1, y + 1)):
            if w[x][y - i] is not None and w[x][y - i] < c:
                break
            if C[x][y - i] == "@":
                break
            w[x][y - i] = c
            dq.append((c + 1, x, y - i))
        # 右
        for i in range(1, min(K + 1, W - y)):
            if w[x][y + i] is not None and w[x][y + i] < c:
                break
            if C[x][y + i] == "@":
                break
            w[x][y + i] = c
            dq.append((c + 1, x, y + i))
    
    ans = w[x2 - 1][y2 - 1]
    if ans is None:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(init,glh,glw):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 0

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

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q,glh,glw)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    g = defaultdict(set)
    for i in range(H):
        for j in range(W):
            for k in range(1, K+1):
                if i - k >= 0 and C[i-k][j] != '@':
                    g[(i, j)].add((i-k, j))
                else:
                    break
            for k in range(1, K+1):
                if i + k < H and C[i+k][j] != '@':
                    g[(i, j)].add((i+k, j))
                else:
                    break
            for k in range(1, K+1):
                if j - k >= 0 and C[i][j-k] != '@':
                    g[(i, j)].add((i, j-k))
                else:
                    break
            for k in range(1, K+1):
                if j + k < W and C[i][j+k] != '@':
                    g[(i, j)].add((i, j+k))
                else:
                    break
    # for k in g:
    #     print(k, g[k])
    q = deque()
    s = (XY1XY2[0]-1, XY1XY2[1]-1)
    go = (XY1XY2[2]-1, XY1XY2[3]-1)
    q.append(s)
    d = {s: 0}
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in d:
                q.append(v)
                d[v] = d[u] + 1

    return -1 if go not in d else d[go]


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  tx,ty,sx,sy=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))
  d=[]
  d.append((sx,sy))
  s=set()
  for ss in d:
    x,y=ss
    t=x*1000000+y
    if t in s:
      s.discard(t)
      continue
    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
      d.append((x+i,y))
      if b[x+i][y]!=0:
        s.add(t+1000000*i)
      b[x+i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((x-i,y))
      if b[x-i][y]!=0:
        s.add(t-1000000*i)
      b[x-i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((x,y+j))
      if b[x][y+j]!=0:
        s.add(t+j)
      b[x][y+j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((x,y-j))
      if b[x][y-j]!=0:
        s.add(t-j)
      b[x][y-j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1 and cord[y][x+i] != '@':
                l.append((x+i,y))
            else:
                f1 = False
            if f2 and cord[y][x-i] != '@':
                l.append((x-i,y))
            else:
                f2 = False
            if f3 and cord[y+i][x] != '@':
                l.append((x,y+i))
            else:
                f3 = False
            if f4 and cord[y-i][x] != '@':
                l.append((x,y-i))
            else:
                f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = '#'
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
print(bfs(xg,yg))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
    H, W, K = map(int, readline().split())
    x1, y1, x2, y2 = map(int,readline().split())
    x1, y1, x2, y2 = (v - 1 for v in (x1, y1, x2, y2))
    C = [readline().rstrip() for i in range(H)]

    visited = [[False] * W for i in range(H)]
    dist = [[0] * W for i in range(H)]

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

    q = deque()

    q.append((x1, y1, 0))
    visited[x1][y1] = True
    dist[x1][y1] = 0

    def aa(_i, _j, y, x, d):
        i, j = _i, _j
        for k in range(K):
            i += y
            j += x
            if not (0 <= i < H and 0 <= j < W):
                break
            if C[i][j] == '@':
                break
            if visited[i][j]:
                continue
            visited[i][j] = True
            dist[i][j] = d
            q.append((i, j, d))

    while q:
        i, j, d = q.popleft()
        for y,x in dirs:
            aa(i, j, y, x, d+1)
    
    if not visited[x2][y2]:
        print(-1)
    else:
        print(dist[x2][y2])
    
solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

c = []
for i in range(H):
    c.append(input().rstrip())

h = [(0, x1-1, y1-1)]

dp = [[False] * W for _ in range(H)]


def check(step, x, y):
    if c[x][y] == '@':
        return False

    if not dp[x][y]:
        dp[x][y] = True
        heappush(h, (step + 1, x, y))

    return True


while h:
    step, x, y = heappop(h)
    if x == x2-1 and y == y2-1:
        print(step)
        break

    for i in range(x+1, min(x+K+1, H)):
        if not check(step, i, y):
            break

    for i in range(x-1, max(-1, x-K-1), -1):
        if not check(step, i, y):
            break

    for j in range(y+1, min(y+K+1, W)):
        if not check(step, x, j):
            break

    for j in range(y-1, max(-1, y-K-1), -1):
        if not check(step, x, j):
            break
else:
    print(-1)

Submission status: Time Limit Exceeded

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] == '.' or 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
      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: Time Limit Exceeded

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] == '.' or 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
      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: Time Limit Exceeded

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    a, b, x, y = map(int, input().split())
    a -= 1
    b -= 1
    x -= 1
    y -= 1
    C = [input().strip("\n") for _ in range(H)]
    D = [[-1 for _ in range(W)] for h in range(H)]
    D[a][b] = 0
    q = []
    heapify(q)
    for h in range(a):
        #up
        if C[a-h-1][b] == "@": break
        else: heappush(q, (h // K + 1, a - h - 1, b, "ud"))
    for h in range(H-a-1):
        #down
        if C[a + h + 1][b] == "@": break
        else: heappush(q, (h // K + 1, a + h + 1, b, "ud"))
    for w in range(b):
        if C[a][b-w-1] == "@": break
        else: heappush(q, (w//K + 1, a, b-w-1, "lr"))
    for w in range(W - b - 1):
        if C[a][b+w+1] == "@": break
        else: heappush(q, (w//K + 1, a, b+w+1, "lr"))

    while q:
        d, h, w, direc = heappop(q)
        if D[h][w] == -1:
            if h == x and w == y:
                print(d)
                break
            D[h][w] = d
            if direc == "lr": #udのみ
                for dh in range(h):
                    if C[h-dh-1][w] == "@": break
                    elif D[h-dh-1][w] == -1: heappush(q, (dh//K + d + 1, h-dh-1, w, "ud"))
                for dh in range(H-h-1):
                    if C[h+dh+1][w] == "@": break
                    elif D[h+dh+1][w] == -1: heappush(q, (dh//K + d + 1, h+dh+1, w, "ud"))
            else:
                for dw in range(w):
                    if C[h][w-dw-1] == "@": break
                    elif D[h][w-dw-1] == -1: heappush(q, (dw//K + d + 1, h, w-dw-1, "lr"))
                for dw in range(W-w-1):
                    if C[h][w+dw+1] == "@": break
                    elif D[h][w+dw+1] == -1: heappush(q, (dw//K + d + 1, h, w+dw+1, "lr"))
    else: print(-1)
    #print(D)

    return 0

if __name__ == "__main__":
    solve()

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))
  d=[]
  d.append((sx,sy))
  s=set()
  for ss in d:
    x,y=ss
    t=x*1000000+y
    if t in s:
      s.discard(t)
      continue
    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
      d.append((x+i,y))
      if b[x+i][y]!=0:
        s.add(t+1000000*i)
      b[x+i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((x-i,y))
      if b[x-i][y]!=0:
        s.add(t-1000000*i)
      b[x-i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((x,y+j))
      if b[x][y+j]!=0:
        s.add(t+j)
      b[x][y+j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((x,y-j))
      if b[x][y-j]!=0:
        s.add(t-j)
      b[x][y-j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
H,W,k = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())
C = [input() for _ in range(H)]

x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
inf = 10**12
d = [[inf]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]

import heapq
def dijkstra(s, t):
    h = [(0, s, t)]
    while h:
        temp = heapq.heappop(h)
        dist = temp[0]
        i = temp[1]
        j = temp[2]
        if used[i][j]:
            continue
        d[i][j] = dist
        used[i][j] = True
        for r in range(i+1, min(H, i+k+1)):
            if used[r][j]:
                continue
            if C[r][j] == "@":
                break
            heapq.heappush(h, (dist+1, r, j))
        for r in range(i-1, max(-1, i-k-1), -1):
            if used[r][j]:
                continue
            if C[r][j] == "@":
                break
            heapq.heappush(h, (dist+1, r, j))
        for c in range(j+1, min(W, j+k+1)):
            if used[i][c]:
                continue
            if C[i][c] == "@":
                break
            heapq.heappush(h, (dist+1, i, c))
        for c in range(j-1, max(-1, j-k-1), -1):
            if used[i][c]:
                continue
            if C[i][c] == "@":
                break
            heapq.heappush(h, (dist+1, i, c))
    return d

d = dijkstra(x1, y1)
if d[x2][y2] == inf:
    print(-1)
else:
    print(d[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
import os
import heapq

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
sx, sy, gx, gy = list(map(int, sys.stdin.buffer.readline().split()))
C = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

u_hist = [[(INF, INF, INF)] * W for _ in range(H)]
d_hist = [[(INF, INF, INF)] * W for _ in range(H)]
l_hist = [[(INF, INF, INF)] * W for _ in range(H)]
r_hist = [[(INF, INF, INF)] * W for _ in range(H)]
u_hist[sx][sy] = (0, 0, 0)
d_hist[sx][sy] = (0, 0, 0)
l_hist[sx][sy] = (0, 0, 0)
r_hist[sx][sy] = (0, 0, 0)
hist = (u_hist, d_hist, l_hist, r_hist)
D = ((0, 1), (1, 0), (0, -1), (-1, 0))

ans = INF
heap = [(0, 0, 0, sx, sy, 0), (0, 0, 0, sx, sy, 1), (0, 0, 0, sx, sy, 2), (0, 0, 0, sx, sy, 3)]
while heap:
    p, s, cnt, x, y, d = heapq.heappop(heap)
    # p = s + cnt / K
    if (p, s, cnt) > hist[d][x][y]:
        continue
    ok=True
    for i in range(4):
        ok&=(p-1, s, cnt) < hist[i][x][y]
    if not ok:
        continue
    if x == gx and y == gy:
        ans = min(ans, s + (cnt + K - 1) // K)
    for i in range(4):
        nd = (d + i) % 4
        dx, dy = D[nd]
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if C[nx][ny] == '@':
            continue
        if nd == d:
            np = s + (cnt + 1) / K
            if hist[nd][nx][ny] < (np, s, cnt + 1):
                continue
            hist[nd][nx][ny] = (np, s, cnt + 1)
            heapq.heappush(heap, (np, s, cnt + 1, nx, ny, nd))
        else:
            ns = s + (cnt + K - 1) // K
            ncnt = 1
            np = ns + 1 / K
            if hist[nd][nx][ny] < (np, ns, ncnt):
                continue
            hist[nd][nx][ny] = (np, ns, ncnt)
            heapq.heappush(heap, (np, ns, ncnt, nx, ny, nd))

if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

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

#46 . 64 @
c = [list(input()) for i in range(h)]

dp = [10**7]*(h*w)

dp[x1*w + y1] = 0
tank = deque([x1*w+y1])

while tank:

    
    now = tank.popleft()
    cost = dp[now]
    
    for i in range(1,k+1):
        if (now+i)%w != 0 and dp[now+i] > cost and c[(now+i)//w][(now+i)%w] == 46:
            dp[now+i] = cost+1
            tank.append(now+i)
        else:
            break
    for i in range(1,k+1):
        if (now-i)%w != w-1 and dp[now-i] > cost and c[(now-i)//w][(now-i)%w] == 46:
            dp[now-i] = cost+1
            tank.append(now-i)
        else:
            break

    for i in range(1,k+1):
        if (now+i*w) < h*w and dp[now+i*w] > cost and c[(now+i*w)//w][(now+i*w)%w] == 46:
            dp[now+i*w] = cost+1
            tank.append(now+i*w)
        else:
            break
    for i in range(1,k+1):
        if (now-i*w) >= 0 and dp[now-i*w] > cost and c[(now-i*w)//w][(now-i*w)%w] == 46:
            dp[now-i*w] = cost+1
            tank.append(now-i*w)
        else:
            break


if dp[x2*w+y2] == 10**7:
    print(-1)
else:
    print(dp[x2*w+y2])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

h,w,k = imap()
sx,sy,gx,gy = imap()
S,G = (sx,sy), (gx,gy)

grid = [[1]*(w+2)] + [[1]+[int(elm == "@") for elm in list(sinput())]+[1] for i in range(h)] + [[1]*(w+2)]

#print(np.array(grid))

q = col.deque([(sx,sy)])
dep = col.defaultdict(int)
dep[S] = 1
while q:
    now = q.popleft()
    if now == (gx,gy): break
    x,y = now[0],now[1]
    nexts = []
    for i in range(1,k+1):
        if grid[x+i][y]: break
        else: nexts.append((x+i, y))
    for i in range(1,k+1):
        if grid[x-i][y]: break
        else: nexts.append((x-i, y))
    for i in range(1,k+1):
        if grid[x][y+i]: break
        else: nexts.append((x, y+i))
    for i in range(1,k+1):
        if grid[x][y-i]: break
        else: nexts.append((x, y-i))
    for next in nexts:
        nx,ny = next[0],next[1]
        if dep[next]: continue # 探索済ならスキップ
        else: dep[next] = dep[now] + 1; q.append(next)

ans = dep[G]-1 if dep[G] else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import heapq

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
sx, sy, gx, gy = list(map(int, sys.stdin.buffer.readline().split()))
C = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

u_hist = [[(INF, INF, INF)] * W for _ in range(H)]
d_hist = [[(INF, INF, INF)] * W for _ in range(H)]
l_hist = [[(INF, INF, INF)] * W for _ in range(H)]
r_hist = [[(INF, INF, INF)] * W for _ in range(H)]
u_hist[sx][sy] = (0, 0, 0)
d_hist[sx][sy] = (0, 0, 0)
l_hist[sx][sy] = (0, 0, 0)
r_hist[sx][sy] = (0, 0, 0)
hist = (u_hist, d_hist, l_hist, r_hist)
D = ((0, 1), (1, 0), (0, -1), (-1, 0))

ans = INF
heap = [(0, 0, 0, sx, sy, 0), (0, 0, 0, sx, sy, 1), (0, 0, 0, sx, sy, 2), (0, 0, 0, sx, sy, 3)]
while heap:
    p, s, cnt, x, y, d = heapq.heappop(heap)
    # p = s + cnt / K
    if (p, s, cnt) > hist[d][x][y]:
        continue
    ok=True
    for i in range(4):
        ok&=(p-2, s, cnt) < hist[i][x][y]
    if not ok:
        continue
    if x == gx and y == gy:
        ans = min(ans, s + (cnt + K - 1) // K)
    for i in range(4):
        nd = (d + i) % 4
        dx, dy = D[nd]
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if C[nx][ny] == '@':
            continue
        if nd == d:
            np = s + (cnt + 1) / K
            if hist[nd][nx][ny] < (np, s, cnt + 1):
                continue
            hist[nd][nx][ny] = (np, s, cnt + 1)
            heapq.heappush(heap, (np, s, cnt + 1, nx, ny, nd))
        else:
            ns = s + (cnt + K - 1) // K
            ncnt = 1
            np = ns + 1 / K
            if hist[nd][nx][ny] < (np, ns, ncnt):
                continue
            hist[nd][nx][ny] = (np, ns, ncnt)
            heapq.heappush(heap, (np, ns, ncnt, nx, ny, nd))

if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from random import randint
if randint(1,10)==1:
  from collections import deque
  import sys
  input=sys.stdin.readline
  calc=lambda x,y:x*1000007+y
  def main():
    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))
    d=deque()
    d.append(calc(sx,sy))
    s=set()
    while d:
      x,y=divmod(d.popleft(),1000007)
      if calc(x,y)in s:
        s.discard((x,y))
        continue
      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
        d.append(calc(x-i,y))
        if b[x-i][y]!=0:
          s.add((x-i,y))
        b[x-i][y]=b[x][y]+1
      for i in range(1,k+1):
        if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
        d.append(calc(x+i,y))
        if b[x+i][y]!=0:
          s.add((x+i,y))
        b[x+i][y]=b[x][y]+1
      for j in range(1,k+1):
        if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
        d.append(calc(x,y-j))
        if b[x][y-j]!=0:
          s.add((x,y-j))
        b[x][y-j]=b[x][y]+1
      for j in range(1,k+1):
        if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
        d.append(calc(x,y+j))
        if b[x][y+j]!=0:
          s.add((x,y+j))
        b[x][y+j]=b[x][y]+1
    print(-1)
  if __name__ == "__main__":
    main()
else:
  def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    sx,sy,tx,ty=map(int,input().split())
    calc=lambda x,y:x*1000007+y
    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))
    s=set()
    while d:
      x,y=d.popleft()
      if calc(x,y)in s:
        s.discard(calc(x,y))
        continue
      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
        d.append((x-i,y))
        if b[x-i][y]!=0:
          s.add(calc(x-i,y))
        b[x-i][y]=b[x][y]+1
      for i in range(1,k+1):
        if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
        d.append((x+i,y))
        if b[x+i][y]!=0:
          s.add(calc(x+i,y))
        b[x+i][y]=b[x][y]+1
      for j in range(1,k+1):
        if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
        d.append((x,y-j))
        if b[x][y-j]!=0:
          s.add(calc(x,y-j))
        b[x][y-j]=b[x][y]+1
      for j in range(1,k+1):
        if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
        d.append((x,y+j))
        if b[x][y+j]!=0:
          s.add(calc(x,y+j))
        b[x][y+j]=b[x][y]+1
    print(-1)
  if __name__ == "__main__":
    main()