Problem:


Score : 600 points

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2).
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

Submission status: Wrong Answer

Solution code:
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 = [[-1]*W for i in range(H)]
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 0 <= dist[x][y] < cost:
    continue
  dist[x][y] = cost
  if (x, y) == (x2, y2):
    print(cost)
    quit()
  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 dist[xx][yy] >= 0:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, v])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

Submission status: Wrong Answer

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

pq = [0]*(h*w)


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


pq[x1*w + y1] = 3
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 and pq[now+i] < 3:
            pq[now+i] += 1 
            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 and pq[now-i] < 3:
            pq[now-i] += 1
            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 and pq[now+i*w] < 3:
            pq[now+i*w] += 1
            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 and pq[now-i*w] < 3:
            pq[now-i*w] += 1
            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: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
X=[int(i) for i in input().split()]
C=[]
for i in range(h):
    C.append(list(input()))

que=[(X[0]-1,X[1]-1,0)]
now=0

while now<len(que):
    pic=[]
    nx,ny,sc=que[now][0],que[now][1],que[now][2]
    if nx==X[2]-1 and ny==X[3]-1:
        print(sc)
        break
    
    for i in range(1,k+1):
        if nx+i<h and C[nx+i][ny]==".":
            C[nx+i][ny]="x"
            pic.append((nx+i,ny,sc+1))
        else:
            break
        
    for i in range(1,k+1):
        if nx-i>=0 and C[nx-i][ny]==".":
            C[nx-i][ny]="x"
            pic.append((nx-i,ny,sc+1))
        else:
            break
    
    for i in range(1,k+1):
        if ny+i<w and C[nx][ny+i]==".":
            C[nx][ny+i]="x"
            pic.append((nx,ny+i,sc+1))
        else:
            break
    
    for i in range(1,k+1):
        if ny-i>=0 and C[nx][ny-i]==".":
            C[nx][ny-i]="x"
            pic.append((nx,ny-i,sc+1))
        else:
            break
    
    que.extend(pic[::-1])
    
    
    now+=1
    #print(que)
else:
    print(-1)

Submission status: Wrong Answer

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


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] * 4 for _ in range(w)] for _ in range(h)]
    min_cost[sy][sx] = [0, 0, 0, 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
                flg = i * 2 + j
                if 0 <= ny < h and 0 <= nx < w:
                    if grid[ny][nx] == "@":
                        break
                    elif min(min_cost[cy][cx]) + 1 < min_cost[ny][nx][flg]:
                        min_cost[ny][nx][flg] = min(min_cost[cy][cx]) + 1
                        que += [(ny, nx)]
                    elif min(min_cost[cy][cx]) + 1 == min_cost[ny][nx][flg]:
                        continue
                    else:
                        break
                else:
                    break
    return min(min_cost[gy][gx])

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

Submission status: Wrong Answer

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 = [[-1]*W for i in range(H)]
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 dist[x][y] >= 0 and dist[x][y] < cost:
    continue
  dist[x][y] = cost
  if (x, y) == (x2, y2):
    print(cost)
    quit()
  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 dist[xx][yy] >= 0:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, v])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

print(-1)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
#block = [list(input()) for _ in range(h)]
block = []
for i in range(h):
    l = list(input())
    block.append([float("inf") if i == "." else i for i in l])
migi = 0
hidari = 1
ue = 2
sita = 3
q = deque()
q.append([x1-1, y1-1, 6, 1])
block[x1-1][y1-1] = 0
while q:
    xx, yy, houkou, kaisuu = q.popleft()
    if xx+1 <= h-1 and block[xx+1][yy] != "@":
        if houkou == sita and kaisuu < k and block[xx+1][yy] > block[xx][yy]:
            block[xx+1][yy] = block[xx][yy]
            q.append([xx+1, yy, sita, kaisuu+1])
        elif block[xx+1][yy] >= block[xx][yy]+1:
            block[xx+1][yy] = block[xx][yy]+1
            q.append([xx+1, yy, sita, 1])
    if xx-1 >= 0 and block[xx-1][yy] != "@":
        if houkou == ue and kaisuu < k and block[xx-1][yy] > block[xx][yy]:
            block[xx-1][yy] = block[xx][yy]
            q.append([xx-1, yy, ue, kaisuu+1])
        elif block[xx-1][yy] >= block[xx][yy]+1:
            block[xx-1][yy] = block[xx][yy]+1
            q.append([xx-1, yy, ue, 1])
    if yy+1 <= w-1 and block[xx][yy+1] != "@":
        if houkou == migi and kaisuu < k and block[xx][yy+1] > block[xx][yy]:
            block[xx][yy+1] = block[xx][yy]
            q.append([xx, yy+1, migi, kaisuu+1])
        elif block[xx][yy+1] >= block[xx][yy]+1:
            block[xx][yy+1] = block[xx][yy]+1
            q.append([xx, yy+1, migi, 1])
    if yy-1 >= 0 and block[xx][yy-1] != "@":
        if houkou == hidari and kaisuu < k and block[xx][yy-1] > block[xx][yy]:
            block[xx][yy-1] = block[xx][yy]
            q.append([xx, yy-1, hidari, kaisuu+1])
        elif block[xx][yy-1] >= block[xx][yy]+1:
            block[xx][yy-1] = block[xx][yy]+1
            q.append([xx, yy-1, hidari, 1])
if block[x2-1][y2-1] == float("inf"):
    print(-1)
else:
    print(block[x2-1][y2-1])

Submission status: Wrong Answer

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]

from collections import deque
sys.setrecursionlimit(10**6)
h,w,k=NM()
x1,y1,x2,y2=NM()
l=[[1]*(w+2)]+[[1]+[1 if j=="@" else 0 for j in input()]+[1] for i in range(h)]+[[1]*(w+2)]
ans=[[-1]*(w+2) for i in range(h+2)]
def dfs(x,y,d,muki,p):
    if ans[x][y]!=-1 or l[x][y]==1:
        return 1
    ans[x][y]=d
    if p>0:
        dx,dy=muki
        if dfs(x+dx,y+dy,d,muki,p-1):
            q.append((x,y))
    else:
        q.append((x,y))
    return 0
        
q=deque([(x1,y1)])
ans[x1][y1]=0
while q:
    x,y=q.popleft()
    d=ans[x][y]
    dfs(x+1,y,d+1,(1,0),k-1)
    dfs(x-1,y,d+1,(-1,0),k-1)
    dfs(x,y+1,d+1,(0,1),k-1)
    dfs(x,y-1,d+1,(0,-1),k-1)

print(ans[x2][y2])

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost+1):
                break
            if(costgrid[nx][ny]>cost+1):
                costgrid[nx][ny]=cost+1
                heapq.heappush(q,(cost+1,nx,ny))
                if nx==gx and ny==gy:
                    ans=min(costgrid[nx][ny],ans)
                    q=[]

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

H,W,K=map(int,input().split())
x,y,u,v=map(int,input().split())
C=[[]]

for u in range(H):
    C.append("*"+input())
    
Q=deque([(x,y)])
S=set((x,y))
D={(x,y):0}
R=[(1,0),(0,1),(-1,0),(0,-1)]
T=0

while Q:
    (p,q)=Q.popleft()

    N=[]
    for (a,b) in R:
        for m in range(1,K+1):
            X,Y=p+a*m,q+b*m
            if (1<=X<=H) and (1<=Y<=W):
                if (C[X][Y]=="."):
                    N.append((X,Y))
                else:
                    break
            else:
                break

    d=D[(p,q)]
    T=set()
    for (s,t) in N:
        if (s,t) not in S:
            T.add((s,t))
            Q.append((s,t))
            D[(s,t)]=d+1
            if (s,t)==(u,v):
                print(d+1)
                sys.exit()
    S|=T
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
P = [input() for _ in range(H)]

queue = deque([[xs, ys]])
visited = [[-1 for i in range(W+1)]for j in range(H+1)]
visited[xs][ys] = 0
while queue:
    x, y = queue.popleft()
    step = 1
    while step <= K:
        new_y, new_x = y+step, x
        if new_y > W:
            break
        elif P[new_x-1][new_y-1] == '@':
            break
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y] = visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
    step = 1
    while step <= K:
        new_y, new_x = y-step, x
        if new_y < 1:
            break
        elif P[new_x-1][new_y-1] == '@':
            break   
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y] = visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
    step = 1
    while step <= K:
        new_y, new_x = y, x+step
        if new_x > H:
            break
        elif P[new_x-1][new_y-1] == '@':
            break
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y]= visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
    step = 1
    while step <= K:
        new_y, new_x= y, x-step
        if new_x < 1:
            break
        elif P[new_x-1][new_y-1] == '@':
            break
        elif visited[new_x][new_y] == -1:
            visited[new_x][new_y] = visited[x][y] + 1
            queue.append([new_x, new_y])
            step += 1
        else:
            break
print(visited[xg][yg])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx,-1)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        oy,ox,turn = q.popleft()
        for i,dy,dx in zip(range(4),Dy,Dx):
            if i == turn:
                continue
            y,x = oy,ox
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0:
                    break
                dist[y][x] = dist[oy][ox] + 1
                q.append((y,x,(i + 2)%4))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def LI():return list(map(int,input().split()))

INF=float("inf")
# from pprint import*
from collections import deque

def main():
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=[list(input()) for _ in range(h)]
    dist=[[INF]*(w) for _ in range(h)]
    
    q=deque([])
    
    q.append((x1,y1))
    dist[x1][y1]=0
    while q:
        (xn,yn)=q.popleft()
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,-kk),(0,kk),(-kk,0),(kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))

        
        
    # pprint(maze)
    # for j in dist:print(*j)
    ans=dist[x2][y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    h,w,k=INTM()
    xs,ys,xg,yg=INTM()
    xs-=1
    ys-=1
    xg-=1
    yg-=1
    ban=[]
    for i in range(h):
        ban.append(STR())
    step=[10**9]*w*h
    step[xs*w+ys]=0
    que=deque([xs*w+ys])
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    #print(len(step),xg*w +yg)
    while len(que)>0 and step[xg*w +yg] == 10**9:
        q=que.pop()
        x=q//w
        y=q%w
        for i in range(k,0,-1):
            for j in range(4):
                #print(i,'i')
                my = y + dy[j]*i
                mx = x + dx[j]*i
                print(mx,my)
                
                if not((0 <=mx <= h-1) and (0 <= my <= w-1)):
                    #print('q')
                    continue
                    
                temp=[]
                for l in range(1,i+1):
                    #print(k,'k')
                    #print('kx',x + dx[j]*k,y + dy[j]*k)
                    #print(ban)
                    #print(ban[x + dx[j]*k][y + dy[j]*k])
                    temp.append(ban[x + dx[j]*l][y + dy[j]*l])
                
                if '@' in temp:
                #print('b')
                    continue
                if step[(mx*w + my)] <= step[x*w + y] + 1:
                #print('c')
                    continue
                
                for l in range(1,i+1):
                    #print(k,'k')
                    #print('kx',x + dx[j]*k,y + dy[j]*k)
                    #print(ban)
                    #print(ban[x + dx[j]*k][y + dy[j]*k])
                    #temp.append(ban[x + dx[j]*k][y + dy[j]*k])
                    step[(x + dx[j]*l)*w + (y + dy[j]*l)] = min(step[x*w + y] + 1, step[(x + dx[j]*l)*w + (y + dy[j]*l)]) 
                    que.append((x + dx[j]*l)*w + (y + dy[j]*l))
    
    if step[xg*w +yg] == 10**9:
        print(-1)
    else:
        print(step[xg*w +yg])
        
    
    
if __name__ == '__main__':
    do()

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs():

    d = [[float("inf")] * w for _ in range(h)]
    rule = [[[]] * 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, -1, 0, bl))
    d[sx][sy] = 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]
            if p[2] == i:
                if p[3] == k - 1:
                    ok = 0
                    bl = False
                else:
                    ok = p[3] + 1
                    bl = True
            else:
                ok = 0
                bl = False

            if 0 <= nx < h and 0 <= ny < w:
                if data[nx][ny] != "@" and d[nx][ny] == float("inf"):
                    que.append((nx, ny, i, ok, bl))
                    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: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
q = deque([(x1-1, y1-1)])
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
dist = [[0]*w for _ in range(h)]
while q:
    x, y = q.popleft()
    for ddx, ddy in dxdy:
        for i in range(1, k+1):
            dx = ddx*i
            dy = ddy*i
            if not (0<=x+dx<w and 0<=y+dy<h):
                break
            if c[y+dy][x+dx]=='@' or dist[y+dy][x+dx]<=dist[y][x]:
                break
            if dx==x2-1 and dy==y2-1:
                print(dist[y][x]+1)
                exit(0)
            dist[y+dy][x+dx] = dist[y][x]+1
            q.append((x+dx, y+dy))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def mbfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=1
    tank=[[-1]*W for i in range(H)]
    tank[sh][sw]=K
    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            for i in range(1,100000):
                nh=h+dx[dir]*i
                nw=w+dy[dir]*i
                if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    continue
                if dist[nh][nw]!=-1 or S[nh][nw]=='@':
                    break
                #発見した地点への操作
                dist[nh][nw]=dist[h+dx[dir]*(i-1)][w+dy[dir]*(i-1)]
                if tank[h+dx[dir]*(i-1)][w+dy[dir]*(i-1)]==0:
                    tank[nh][nw]=K-1
                    dist[nh][nw]+=1
                else:
                    tank[nh][nw]=tank[h+dx[dir]*(i-1)][w+dy[dir]*(i-1)]-1
                d.append([nh,nw])
                #ここまで
    return dist

H,W,K=map(int,input().split())
sx,sy,gx,gy=map(lambda x:int(x)-1,input().split())

c=[list(input()) for i in range(H)]

dist=mbfs(c,H,W,sx,sy)
print(dist[gx][gy])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h, w, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
pond = []
for _ in range(h):
    pond.append(list(input()))

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

# def dfs(x, y, prev_k=-1, dist=0):
#     for k in range(4):
#         nx = x + dx[k]
#         ny = y + dy[k]
#         if 0 <= nx < h and 0 <= ny < w and pond[nx][ny] != "@":
#             if k == prev_k:
#                 dist = dfs()

dist = [[10 ** 8] * w for _ in range(h)]
dist[x1][y1] = 0
q = deque([(x1, y1, -1, 0)])
while q:
    x, y, prev_k, cnt = q.popleft()
    cnt += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < h and 0 <= ny < w and pond[nx][ny] != "@":
            cost = 0
            cnt2 = cnt
            if k != prev_k or cnt2 > K:
                cost = 1
                cnt2 = 1
            if dist[x][y] + cost < dist[nx][ny]:
                dist[nx][ny] = dist[x][y] + cost
                q.append((nx, ny, k, cnt2))
if dist[x2][y2] == 10 ** 8:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Wrong Answer

Solution code:
####################################################################
import sys
def p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
H,W,K = map(int, input().split())		# 5 7 2

x1,y1,x2,y2 = map(int, input().split())		# 5 7 2

x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1

M = list( list(input()) for _ in range(H) )
#=> [['.', '.', '.', '.'], ['.', 'S', 'S', '.'], ['.', '.', 'S', '.'], ['.', '.', '.', '.']]

INF = 10**12

for h in range(H):
  for w in range(W):
    c = M[h][w]
    if c == ".": M[h][w] = INF
    if c == "@": M[h][w] = -1

# dXY=[]
# for i in range(1,K+1):
#   dXY.append(( i, 0))
#   dXY.append((-i, 0))
#   dXY.append(( 0, i))
#   dXY.append(( 0,-i))
dXY=[ [0,1], [0,-1], [1,0], [-1,0] ]

from collections import deque
Q = deque()
Q.append( [x1,y1] )
M[x1][y1]=0

while Q:
  x,y = Q.popleft()
  # p("x,y = ", x,y)
  if x==x2 and y==y2: break
  for dx, dy in dXY:

    for k in range(K):
      if dx > 0: dx += k
      if dx < 0: dx -= k
      if dy > 0: dy += k
      if dy < 0: dy -= k
      h = x + dx
      w = y + dy
      if h<0 or H<=h or w<0 or W<=w: break
      # p("h,w,x,y = ", h,w,x,y)
      # p( "M[h][w]", M[h][w])
      # p( "M[x][y]", M[x][y])
      if M[h][w] == -1: break
      if M[x][y]+1 < M[h][w]:
        M[h][w] = M[x][y]+1
        Q.append( [h,w] )
      else:
        break

ans = M[x2][y2]
if ans == INF: ans = -1
print(ans)

Submission status: Wrong Answer

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

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("\n"))

dist = [[10 ** 18 for i in range(w)] for j in range(h)]

def bfs(cx, cy, x, y, cost, cnt):
    stack = deque([[cx, cy, x, y, cost, cnt]])
    stack_append = stack.append
    stack_popleft = stack.popleft
    while stack:
        cx, cy, x, y, cost, cnt = stack_popleft()
        if dist[x][y] > cost:
            dist[x][y] = cost
            for vx, vy in ((0,1), (0,-1), (-1,0), (1,0)):
                nx, ny = x + vx, y + vy
                if 0 <= nx and nx < h and 0 <= ny and ny < w:
                    if nx == cx and ny == cy:
                        continue
                    if c[nx][ny] == "@":
                        continue
                    if x - cx == vx and y - cy == vy and cnt < k-1:
                        stack_append([x, y, nx, ny, cost, cnt+1])
                    else:
                        stack_append([x, y, nx, ny, cost+1, 1])

bfs(-2, -2, x1-1, y1-1, 0, 0)
# print(dist)

ans = dist[x2-1][y2-1]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
X=[int(i) for i in input().split()]
C=[]
for i in range(h):
    C.append(list(input()))

que=[(X[0]-1,X[1]-1,0)]
now=0

while now<len(que):
    nx,ny,sc=que[now][0],que[now][1],que[now][2]
    if nx==X[2]-1 and ny==X[3]-1:
        print(sc)
        break
    
    for i in range(k,0,-1):
        if nx+i<h and C[nx+i][ny]==".":
            C[nx+i][ny]="x"
            que.append((nx+i,ny,sc+1))
        else:
            break
        
    for i in range(k,0,-1):
        if nx-i>=0 and C[nx-i][ny]==".":
            C[nx-i][ny]="x"
            que.append((nx-i,ny,sc+1))
        else:
            break
    
    for i in range(k,0,-1):
        if ny+i<w and C[nx][ny+i]==".":
            C[nx][ny+i]="x"
            que.append((nx,ny+i,sc+1))
        else:
            break
    
    for i in range(k,0,-1):
        if ny-i>=0 and C[nx][ny-i]==".":
            C[nx][ny-i]="x"
            que.append((nx,ny-i,sc+1))
        else:
            break
    
    
    now+=1
else:
    print(-1)

Submission status: Wrong Answer

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

H,W,K = map(int,readline().split())
x1,y1,x2,y2 = map(int,readline().split())
x1,y1,x2,y2 = x1 - 1,y1 - 1,x2 - 1,y2 - 1

grid = [None] * H
for i in range(H):
  grid[i] = readline().rstrip()
  
# 操作としてあり得るのは、
# ・1かきでKマス進む or @の直前まで進む
# ・1かきでKマス未満進んで方向転換する
# 
# ・前回水をかいてから何マス進んでいるか
# ・前回水をかいて、どのむき(U,D,L,R)に進んでいるか
#  (来たところに戻ることはあり得ないので)
# ・今までに何回水をかいたか
# ・今どこにいるか
# 水かき回数でダイクストラ
# たとえ泳ぐ向きが違っても同じ場所を2回通ることはあり得ない。

import numpy as np
# from numba import njit,i8
from collections import defaultdict

import heapq
# 今まで何回水をかいたか,i,j,前回水をかいてから何マス進んでいるか,どのむきに進んでいるか
def solve():
  def get_turn(d):
    if d in ("U","D"): # 縦方向に進んでいた場合の次の進み先
      return ((0,1,"R"),(0,-1,"L"))
    else:
      return ((1,0,"D"),(-1,0,"U"))
  
  def get_straight(d):
    if d == "U":
      return (-1,0,"U")
    if d == "D":
      return (1,0,"D")
    if d == "L":
      return (0,-1,"L")
    if d == "R":
      return (0,1,"R")
  q = []
  heapq.heapify(q)
  # 最初に進む4方向を入れておく
  seen = defaultdict(int)
  for first in "UDLR":
    c = get_straight(first)
    if 0 <= x1 + c[0] < H and 0 <= y1 + c[1] < W:
      if grid[x1 + c[0]][y1 + c[1]] != "@":
        heapq.heappush(q,(1,x1 + c[0],y1 + c[1],1,c[2]))
  seen[(x1,y1)] = 0
  while q:
    cost,i,j,swim,dire = heapq.heappop(q)
    #print("cost",cost,"i",i,"j",j,"swim",swim,"dire",dire)
    #print(q)
    if (i,j) in seen and seen[(i,j)] <= cost:
      continue
    if i == x2 and j == y2:
      return cost
    seen[(i,j)] = cost
    # 曲がる場合
    cases = get_turn(dire)
    for c in cases:
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
    # 直進する場合
    c = get_straight(dire)
    if swim < K: # まだKマス進んでいない
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えず、swim距離は増える
          heapq.heappush(q,(cost,i + c[0],j + c[1],swim + 1,c[2]))
    elif swim == K: # すでにKマス進んでいる場合
      # 直進する場合
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えて、swim距離は1に
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
  else:
    return -1
print(solve())