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:
import heapq as hq

H,W,K = map(int,input().split())
H = H+2
W = W+2
sx,sy,gx,gy = map(int,input().split())
sx,sy = sy,sx
gx,gy = gy,gx
inf = 10**7

M = [["@"]*W for _ in range(H)]

for h in range(1,H-1):
    M[h][1:-1] = list(input())

dist = [[[[inf,inf] for ___ in range(4)] for _ in range(W)] for __ in range(H)]
visited = [[[False for ___ in range(4)] for _ in range(W)] for __ in range(H)]
movable_state = 0
for h in range(H):
    for w in range(W):
        if M[h][w] == ".":
            movable_state += 4



for i in range(4):
    dist[sy][sx][i] = [0,0]

q = [[0,sx,sy,0],[0,sx,sy,1],[0,sx,sy,2],[0,sx,sy,3]]

def can_go(x,y):
    return M[y][x] == "."

def f(x):
    return x[0]*10**7+x[1]


while q != []:
    c,x,y,to = hq.heappop(q)
    swing,step = dist[y][x][to]
    if to == 0:
        if can_go(x-1,y):
            if step <= K-1:
                dist[y][x-1][0] = min([swing,step+1],dist[y][x-1][0],key=f)
                if not visited[y][x-1][0]:
                    hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
            else:
                dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
                if not visited[y][x-1][0]:
                    hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x,y-1):
            dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
            if not visited[y-1][x][1]:
                hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x+1,y):
            dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
            if not visited[y][x+1][2]:
                hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
        if can_go(x,y+1):
            dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
            if not visited[y+1][x][3]:
                hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
    if to == 1:
        if can_go(x,y-1):
            if step <= K-1:
                dist[y-1][x][1] = min([swing,step+1],dist[y-1][x][1],key=f)
                if not visited[y-1][x][1]:
                    hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
            else:
                dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
                if not visited[y-1][x][1]:
                    hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x-1,y):
            dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
            if not visited[y][x-1][0]:
                hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x+1,y):
            dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
            if not visited[y][x+1][2]:
                hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
        if can_go(x,y+1):
            dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
            if not visited[y+1][x][3]:
                hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
    
    if to == 2:
        if can_go(x+1,y):
            if step <= K-1:
                dist[y][x+1][2] = min([swing,step+1],dist[y][x+1][2],key=f)
                if not visited[y][x+1][2]:
                    hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
            if step == K:
                dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
                if not visited[y][x+1][2]:
                    hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
        
        if can_go(x-1,y):
            dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
            if not visited[y][x-1][0]:
                hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x,y-1):
            dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
            if not visited[y-1][x][1]:
                hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x,y+1):
            dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
            if not visited[y+1][x][3]:
                hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
    
    if to == 3:
        if can_go(x,y+1):
            if step <= K-1:
                dist[y+1][x][3] = min([swing,step+1],dist[y+1][x][3],key=f)
                if not visited[y+1][x][3]:
                    hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
            else:
                dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
                if not visited[y+1][x][3]:
                    hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
        if can_go(x-1,y):
            dist[y][x-1][0] = min([swing,1],dist[y][x-1][0],key=f)
            if not visited[y][x-1][0]:
                hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x,y-1):
            dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
            if not visited[y-1][x][1]:
                hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x+1,y):
            dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
            if not visited[y][x+1][2]:
                hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
    visited[y][x][to] = True

if not visited[gy][gx][0]:
    print(-1)
    exit()
print(min(dist[gy][gx][0][0],dist[gy][gx][1][0],dist[gy][gx][2][0],dist[gy][gx][3][0])+1)

"""
for h in range(H):
    for w in range(W):
        m = inf
        for i in range(4):
            m = min(m,dist[h][w][i][0])
        print(m,end=" ")
    print("\n")
"""

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in edge]) for edge in self.edges]):
            print( [[nd for nd,d in edge] for edge in self.edges] )
        else:
            print(self)
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True
ans=0



h,w,k=LI()
sh,sw,gh,gw=LI()
h,w,g,_=GGI(h,w,search=[],replacement_of_found='.',mp_def={'@':1,'.':0},boundary=1) # sample usage

goal=gh*w+gw
start=sh*w+sw


D=10**7

v=[[inf]*h*w for i in rep(4)]
#dist=[[inf]*h*w for i in rep(4)]
q=[start*10+i for i in rep(4)]
q=deque(q)
for i in rep(4):
    v[i][start]=0

ans=inf
show(q,goal)
while q:
    c=q.pop()
    c,dr=c//10,c%10
    #show(c,dr)
    dd=[-1,1,-w,w][dr]
    for i in rep(1,k+1):
        nx=c+dd*i
        if g[nx]==1:
            break
        if v[dr][nx]==inf:
            q.appendleft((c+dd)*10+dr)
            v[dr][nx]=v[dr][c]+i
            if v[dr][nx]%D>k:
                v[dr][nx]=(v[dr][nx]//D+1)*D
            if nx==goal:
                ans=min(ans,(v[dr][nx]+D-1)//D)
    for nxr in [(dr+i+1)%4 for i in rep(3)]:
        if v[nxr][c]==inf:
            q.append(c*10+nxr)
            v[nxr][c]=(v[dr][c]//D+1)*D
        
print(ans)
for j in v:
    for i in rep(h):
        show(j[i*w:-~i*w])
    show()

for i in rep(h):
    show(g[i*w:-~i*w])

exit()

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())
map = [list(input())[:-1] for _ in range(h)]
is_visit = [[10**7 for _ in range(w)] for _ in range(h)]
is_visit[x2-1][y2-1] = 0

q = deque()
q.append((y2-1, x2-1, 0))

while len(q) != 0:
    x, y, c = q.popleft()
    # print(x, y, is_visit)
    for i in range(1, k+1):
        if x-i >= 0 and is_visit[y][x-i] > is_visit[y][x-(i-1)] and map[y][x-i] == '.':
            is_visit[y][x-i] = c+1
            q.append((x-i, y, c+1))
        else:
            break
    for i in range(1, k+1):
        if x+i < w and is_visit[y][x+i] > is_visit[y][x+(i-1)] and map[y][x+i] == '.':
            is_visit[y][x+i] = c+1
            q.append((x+i, y, c+1))
        else:
            break
    for i in range(1, k+1):
        if y-i >= 0 and is_visit[y-i][x] > is_visit[y-(i-1)][x] and map[y-i][x] == '.':
            is_visit[y-i][x] = c+1
            q.append((x, y-i, c+1))
        else:
            break
    for i in range(1, k+1):
        if y+i < h and is_visit[y+i][x] > is_visit[y+(i-1)][x] and map[y+i][x] == '.':
            is_visit[y+i][x] = c+1
            q.append((x, y+i, c+1))
        else:
            break

ans = is_visit[x1-1][y1-1]
if ans == 10**7:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

que = deque([(sx,sy)])
while que:
    x,y = que.popleft()
    for i in range(4): #方向決め
        for k in range(1,K+1):
            nx = x+k*dif[i][0]
            ny = y+k*dif[i][1]
            if nx<0 or nx>=H or ny<0 or ny>= W or grid[nx][ny] == "@":
                break
            if reach[x][y]+1 >= reach[nx][ny]: # これ以上進んでも無利益なので探索をやめる
                break
            if reach[x][y]+1 < reach[nx][ny]:
                reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
                que.append((nx,ny))
            if nx == gx and ny == gy:
                print(reach[nx][ny])
                exit()
print(-1)

Submission status: Wrong Answer

Solution code:

#not my code.
from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")
 
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]
 
todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0
 
while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                break
                # 更に伸ばす必要はない
            if maze[nx][ny]=="@":
                break
                # 蓮の向こうにはいけない
            if cost[nx][ny]!=-1:
                # 更新を1回以上受けていて、更に良くならない場合はbreak
                break
            if cost[nx][ny]==-1:
                cost[nx][ny]=cost[x][y]+1
                todo.append((nx,ny))
 
 
# pp(cost)
ans=cost[x2][y2]
print(ans)

Submission status: Wrong Answer

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

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

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

print(-1)

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)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        ny,nx = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = ny,nx
            before_d = -3
            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 and dist[y][x] <= before_d:
                    break
                if dist[y][x] < 0:
                    dist[y][x] = dist[ny][nx] + 1
                    q.append((y,x))
                    before_d = dist[y][x]
                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:
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)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        ny,nx = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = ny,nx
            before_d = dist[ny][nx]
            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 and dist[y][x] <= before_d:
                    break
                if dist[y][x] < 0:
                    dist[y][x] = dist[ny][nx] + 1
                    q.append((y,x))
                    before_d = dist[y][x]
                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:
from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]

q = deque()
for d in range(4):
    path[x1][y1][d] = (1, 0)
    q.append((x1, y1, d, 1, 0))

D = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    x, y, d, s, k = q.popleft()
    if k == K:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
            else:
                dx, dy = 0, 0
            nx = x + dx; ny = y + dy
            ns = s + 1
            nk = 0
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                q.append((nx, ny, nd, ns, nk))
    else:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
            else:
                dx, dy = 0, 0
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            nk = 0 if d != nd else k + 1
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                if ns == s:
                    q.appendleft((nx, ny, nd, ns, nk))
                else:
                    q.append((nx, ny, nd, ns, nk))

ans = INF
for d in range(4):
    ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans
print(ans)

Submission status: Wrong Answer

Solution code:
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

xxx = set()
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '@':
            xxx.add((hh, ww))

from heapq import heappush, heappop
q = []
heappush(q, (0, x1, y1))
d = {}
d[(x1, y1)] = 0
while q:
    s, x, y = heappop(q)
    print(s,x,y)

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

print(-1)

Submission status: Wrong Answer

Solution code:
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

xxx = set()
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '@':
            xxx.add((hh, ww))

from heapq import heappush, heappop
q = []
heappush(q, (0, x1, y1))
d = {}
while q:
    s, x, y = heappop(q)
    d[(x, y)] = s
    if x == x2 and y == y2:
        exit(0)

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

dD = [[10**13 for _ in range(w)] for _ in range(h)]
dU = [[10**13 for _ in range(w)] for _ in range(h)]
dR = [[10**13 for _ in range(w)] for _ in range(h)]
dL = [[10**13 for _ in range(w)] for _ in range(h)]

dD[x1][y1] = 0
dU[x1][y1] = 0
dR[x1][y1] = 0
dL[x1][y1] = 0

q = deque([((x1, y1), "D", 0)])

while q:
    v, direction, p = q.popleft()
    x = v[0]
    y = v[1]
    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and direction == "D":
        if dD[x+1][y] > dD[x][y] + (p == 0):
            dD[x+1][y] = dD[x][y] + (p == 0)
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.':
        if dD[x+1][y] >= dD[x][y] > dR[x][y] + 1:
            dD[x+1][y] = dR[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))
        if dD[x+1][y] >= dD[x][y] > dL[x][y] + 1:
            dD[x+1][y] = dL[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and direction == "U":
        if dU[x-1][y] > dU[x][y]+(p == 0):
            dU[x-1][y] = dU[x][y]+(p == 0)
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.':
        if dU[x-1][y] >= dU[x][y] > dR[x][y] + 1:
            dU[x-1][y] = dR[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))
        if dU[x-1][y] >= dU[x][y] > dL[x][y] + 1:
            dU[x-1][y] = dL[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and direction == "R":
        if dR[x][y+1] > dR[x][y] + (p == 0):
            dR[x][y+1] = dR[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.':
        if dR[x][y+1] >= dR[x][y] > dD[x][y] + 1:
            dR[x][y+1] = dD[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))
        if dR[x][y+1] >= dR[x][y] > dU[x][y] + 1:
            dR[x][y+1] = dU[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and direction == "L":
        if dL[x][y-1] > dL[x][y] + (p == 0):
            dL[x][y-1] = dL[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.':
        if dL[x][y-1] >= dL[x][y] > dD[x][y] + 1:
            dL[x][y-1] = dD[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))
        if dL[x][y-1] >= dL[x][y] > dU[x][y] + 1:
            dL[x][y-1] = dU[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))

ans = min(dD[x2][y2], dU[x2][y2], dR[x2][y2], dL[x2][y2])
print(-1 if ans == 10**13 else ans)