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:
import sys
input=sys.stdin.readline

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
maze=[list(input()) for _ in range(h)]

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

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

from collections import deque

dis[sy][sx]=0

def pri(x):
    for item in x:
        print(item)

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        maze[gy][gx]="G"

        #pri(dis)
        #pri(maze)

        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    d.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if dijk[dr][x][y] != inf:
    continue
  dijk[dr][x][y] = pt
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] == inf:
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] == inf:
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] == inf:
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] == inf:
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[None]*w for _ in range(h)]
dist[x1][y1] = 0
done = [[0]*w for _ in range(h)]
done[0][0] = 15

while q:
    d, x, y, t, td = hpp(q)
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if dist[nx][ny] is None or nd<dist[nx][ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx][ny] = nd
            done[nx][ny] = 1<<(i+1)
        elif (nd==dist[nx][ny]and ((done[nx][ny]&1<<(i+1))==0)):
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            done[nx][ny] |= 1<<(i+1)
            
if dist[x2][y2] is None:
    print(-1)
else:
    print(dist[x2][y2])

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())
maze=[list(input()) for _ in range(h)]

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

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

dis[sy][sx]=0

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        tmp=[]
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    tmp.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break
        for item in tmp[::-1]:
            d.append(item)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[None]*w for _ in range(h)]
dist[x1][y1] = 0

while q:
    d, x, y, t, td = hpp(q)
    for xx, yy in zip(dx,dy):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if dist[nx][ny] is None or nd<=dist[nx][ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx][ny] = nd
if dist[x2][y2] is None:
    print(-1)
else:
    print(dist[x2][y2])

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())
maze=[list(input()) for _ in range(h)]

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

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

dis[sy][sx]=0

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    d.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if dijk[dr][x][y] != inf:
    continue
  dijk[dr][x][y] = pt
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.':
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.':
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.':
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.':
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[float("inf")]*w for _ in range(h)]
dist[x1][y1] = 0

while q:
    d, x, y, t, td = hpp(q)
    for xx, yy in zip(dx,dy):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if nd<=dist[nx][ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx][ny] = nd
if dist[x2][y2] >10**10:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q = deque([(x1,y1,0,(0,0),0)])
dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[float("inf")]*w for _ in range(h)]
dist[x1][y1] = 0
while q:
    x, y, d, t, td = q.popleft()
    for xx, yy in zip(dx,dy):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if nd<=dist[nx][ny]:
            q.append((nx,ny,nd,(xx,yy),ntd))
            dist[nx][ny] = nd
if dist[x2][y2] >10**10:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
maze=[list(input()) for _ in range(h)]

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

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

from collections import deque

dis[sy][sx]=0

def pri(x):
    for item in x:
        print(item)

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        maze[gy][gx]="G"

        #pri(dis)
        #pri(maze)

        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    d.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break

print(-1)

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())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1

C = [input() for i in range(H)]
dist = {}
d = [[0, x1, y1, K, -1]]
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  cost, x, y, remain, v = heappop(d)
  if (x, y, v) in dist:
    continue
  dist[(x, y, v)] = cost
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and C[xx][yy] != '@':
      if (xx, yy, i) in dist:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, v])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

cands = [dist[(x2, y2, i)] for i in range(4) if (x2, y2, i) in dist]
if cands:
  print(min(cands))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


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):
    q = deque()
    s = (XY1XY2[0]-1)*W + XY1XY2[1]-1
    go = (XY1XY2[2]-1)*W + XY1XY2[3]-1
    q.append(s)
    d = {s: 0}

    rem = set()
    for i in range(H):
        for j in range(W):
            if C[i][j] == '.':
                rem.add(i*W+j)
    rem.remove(s)
    while q and rem:
        u = q.popleft()
        i = u // W
        j = u % W
        e = list()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                n = (i-k)*W + j
                if n not in d:
                    e.append(n)
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                n = (i+k)*W + j
                if n not in d:
                    e.append(n)
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                n = i*W + j-k
                if n not in d:
                    e.append(n)
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                n = i*W + j+k
                if n not in d:
                    e.append(n)
            else:
                break
        for v in e:
            q.append(v)
            d[v] = d[u] + 1
            rem.remove(v)
            if v == go:
                return d[v]

    return -1


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

    # H = 1000
    # W = 1000
    # K = 1000
    # XY1XY2 = [1, 1, H, W]
    # C = [['.'] * W] * H
    # C[H-2][W-1] = '@'
    # C[H-1][W-2] = '@'
    # print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    S = [[False]*W for _ in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                S[i][j] = True

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

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

            stack.popleft()        

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q = deque([(x1,y1,0,(0,0),0)])
dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[float("inf")]*w for _ in range(h)]
dist[x1][y1] = 0
while q:
    x, y, d, t, td = q.popleft()
    for xx, yy in zip(dx,dy):
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if nd<=dist[nx][ny]:
            q.append((nx,ny,nd,(xx,yy),ntd))
            dist[nx][ny] = nd
if dist[x2][y2] >10**10:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w, k = MAP()
sx, sy, gx, gy = MAP()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        arr[i][j] = (abs(gx - i) + k - 1) // k + (abs(gy - j) + k - 1) // k
marked = [[inf for _ in range(w)] for _ in range(h)]
marked[sx][sy] = 0
que = deque([[sx, sy, 0]])
while que:
    x, y, num = que.popleft()
    if num >= marked[gx][gy]:
        break
    for i in range(4):
        for j in range(1, k + 1):
            nx = x + dx[i] * j
            ny = y + dy[i] * j
            if ny < 0 or w <= ny or nx < 0 or h <= nx:
                break
            if c[nx][ny] == '@':
                break
            n_num = num + 1
            if marked[nx][ny] >= n_num:
                marked[nx][ny] = n_num
                if nx == gx and ny == gy:
                    break
                if n_num + arr[nx][ny] > marked[gx][gy]:
                    continue
                que.append([nx, ny, n_num])
            else:
                break
#for i in marked:
#    print(i)
ans = marked[gx][gy]
print(ans if ans != inf else -1)
#print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs():

    d = [[float("inf")] * w for _ in range(h)]
    rule = [[[] for _ in range(w)] for _ in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    sx = x1 - 1
    sy = y1 - 1
    gx = x2 - 1
    gy = y2 - 1

    que = deque([])
    bl = False
    que.append((sx, sy, sx, sy))
    d[sx][sy] = 0
    rule[sx][sy].append([-1, 0])

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            for j in range(len(rule[p[0]][p[1]])):
                if rule[p[0]][p[1]][j][0] == i:
                    if rule[p[0]][p[1]][j][1] == k - 1:
                        ok = 0
                        bl = False
                    else:
                        ok = rule[p[0]][p[1]][j][1] + 1
                        bl = True
                else:
                    ok = 0
                    bl = False

            if 0 <= nx < h and 0 <= ny < w:
                if data[nx][ny] != "@" and (nx != p[2] or ny != p[3]):
                    que.append((nx, ny, p[0], p[1]))
                    rule[nx][ny].append([i, ok])
                    if bl:
                        d[nx][ny] = d[p[0]][p[1]]
                    else:
                        d[nx][ny] = d[p[0]][p[1]] + 1

    if d[gx][gy] != float("inf"):
        return d[gx][gy]
    else:
        return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
data = [list(input()) for i in range(h)]

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w, k = MAP()
sx, sy, gx, gy = MAP()
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [STR() for _ in range(h)]
marked = [[inf for _ in range(w)] for _ in range(h)]
marked[sx][sy] = 0
que = deque([[sx, sy, 0]])
while que:
    x, y, num = que.popleft()
    if num >= marked[gx][gy]:
        break
    for i in range(4):
        for j in range(1, k + 1):
            nx = x + dx[i] * j
            ny = y + dy[i] * j
            if ny < 0 or w <= ny or nx < 0 or h <= nx:
                break
            if c[nx][ny] == '@':
                break
            n_num = num + 1
            if marked[nx][ny] >= n_num:
                marked[nx][ny] = n_num
                if nx == gx and ny == gy:
                    continue
                que.append([nx, ny, n_num])
            else:
                break
#for i in marked:
#    print(i)
ans = marked[gx][gy]
print(ans if ans != inf else -1)
#print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1,0,1))
while q:
  px,py,direc,dis = q.popleft()
  for j in range(1 if direc != "U" else dis,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= dp[px][py]:
      break
    dp[px+j][py] = dp[px][py]+1
    q.append((px+j,py,"U",k-j+1))
  for j in range(1 if direc != "D" else dis,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= dp[px][py]:
      break
    dp[px-j][py] = dp[px][py]+1
    q.append((px-j,py,"D",k-j+1))
  for j in range(1 if direc != "L" else dis,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= dp[px][py]:
      break 
    dp[px][py+j] = dp[px][py]+1
    q.append((px,py+j,"L",k-j+1))
  for j in range(1 if direc != "R" else dis,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= dp[px][py]:
      break
    dp[px][py-j] = dp[px][py]+1
    q.append((px,py-j,"R",k-j+1))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
H,W,K = map(int,input().split())

x1,y1,x2,y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1

c = []

for i in range(H):

    C = list(input())
    c.append(C)

u = [[(float("inf") , float("inf"))] * W for i in range(H)]
d = [[(float("inf") , float("inf"))] * W for i in range(H)]
l = [[(float("inf") , float("inf"))] * W for i in range(H)]
r = [[(float("inf") , float("inf"))] * W for i in range(H)]

q = []
heapq.heappush(q,(0,0,"l",x1,y1))
heapq.heappush(q,(0,0,"r",x1,y1))
heapq.heappush(q,(0,0,"u",x1,y1))
heapq.heappush(q,(0,0,"d",x1,y1))
u[x1][y1] = (0,0)
d[x1][y1] = (0,0)
l[x1][y1] = (0,0)
r[x1][y1] = (0,0)

end = 0
while len(q) > 0:

    tmp = heapq.heappop(q)
    kai,sus,di,x,y = tmp

    if x == x2 and y == y2:
        break

    if end > 4*H*W+10:
        break

    if di == "l" and l[x][y] != (kai,sus):
        continue
    if di == "r" and r[x][y] != (kai,sus):
        continue
    if di == "u" and u[x][y] != (kai,sus):
        continue
    if di == "d" and d[x][y] != (kai,sus):
        continue

    end += 1

    if di == "l" and x != 0 and sus < K and c[x-1][y]!="@" :
        if l[x-1][y] > (kai,sus+1):
            l[x-1][y] = (kai,sus+1)
            heapq.heappush(q, (kai,sus+1,"l",x-1,y) )

    if di == "r" and x != H-1 and sus < K and c[x+1][y]!="@":
        if r[x+1][y] > (kai,sus+1):
            r[x+1][y] = (kai,sus+1)
            heapq.heappush(q, (kai,sus+1,"r",x+1,y) )

    if di == "u" and y != 0 and sus < K and c[x][y-1]!="@":
        if u[x][y-1] > (kai,sus+1):
            u[x][y-1] = (kai,sus+1)
            heapq.heappush(q, (kai,sus+1,"u",x,y-1) )

    if di == "d" and y != W-1 and sus < K and c[x][y+1]!="@":
        if d[x][y+1] > (kai,sus+1):
            d[x][y+1] = (kai,sus+1)
            heapq.heappush(q, (kai,sus+1,"d",x,y+1) )


    if x != 0:
        if l[x-1][y] > (kai+1,1) and c[x-1][y]!="@":
            l[x-1][y] = (kai+1,1)
            heapq.heappush(q, (kai+1,1,"l",x-1,y) )

    if x != H-1:
        if r[x+1][y] > (kai+1,1) and c[x+1][y]!="@":
            r[x+1][y] = (kai+1,1)
            heapq.heappush(q, (kai+1,1,"r",x+1,y) )

    if y != 0:
        if u[x][y-1] > (kai+1,1) and c[x][y-1]!="@":
            u[x][y-1] = (kai+1,1)
            heapq.heappush(q, (kai+1,1,"u",x,y-1) )

    if y != W-1:
        if d[x][y+1] > (kai+1,1) and c[x][y+1]!="@":
            d[x][y+1] = (kai+1,1)
            heapq.heappush(q, (kai+1,1,"d",x,y+1) )

ans = min(l[x2][y2],r[x2][y2],u[x2][y2],d[x2][y2])
if ans[0] == float("inf"):
    print (-1)
else:
    print (ans[0]+1)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
xs,ys,xg,yg=map(int,input().split())
xs-=1
ys-=1
xg-=1
yg-=1
maze=[]
d=[]
for i in range(H):
  maze.append(list(map(str,input())))
  d.append([1000000000 for _ in range(W)])

que=[[xs,ys]]
d[xs][ys]=0
while(que):
  z=que[0]
  que.remove(que[0])
  if z==[xg,yg]:
    break
  for i in range(4):
    for j in range(K):
      if i ==0:
        x=z[0]+j+1
        y=z[1]
      elif i==1:
        x=z[0]
        y=z[1]+j+1
      elif i==2:
        x=z[0]-(j+1)
        y=z[1]
      else:
        x=z[0]
        y=z[1]-(j+1)
      if 0<=x and H>x and 0<=y and y<W  and maze[x][y]!="@" and d[x][y]>=d[z[0]][z[1]]+1:
        que.append([x,y])
        d[x][y]=d[z[0]][z[1]]+1
      else:
        break
if d[xg][yg]==1000000000:
  print("-1")
else:
  print(d[xg][yg])