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 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)]
q=[start*10+i for i in rep(4)]
q=deque(q)
for i in rep(4):
    v[i][start]=0

ans=inf

while q:
    c=q.pop()
    c,dr=c//10,c%10
    #show(c,dr)
    dd=[-1,1,-w,w][dr]
    nx=c+dd
    if g[nx]!=1 and v[dr][nx]==inf:
        if v[dr][c]%D==k:
            q.append(nx*10+dr)
            v[dr][nx]=(v[dr][c]//D+1)*D+1
        else:
            q.appendleft(nx*10+dr)
            v[dr][nx]=v[dr][c]+1
        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

ans=-1 if ans==inf else ans
print(ans)

Submission status: Wrong Answer

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w;d=[I]*h*w;a=~w+a*w+b
d[a]=2
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Submission status: Wrong Answer

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


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        for xx,yy in [(1,0),(0,1),(-1,0),(0,-1)]:
            for i in range(1,k+1):
                nx,ny = x+xx*i,y+yy*i
                if cord[ny][nx] == '.':
                    l.append((nx,ny))
                elif type(cord[ny][nx]) != int or cord[ny][nx] == dep+1:
                    break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

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

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

print(bfs(xg,yg))

Submission status: Wrong Answer

Solution code:
# F - Pond Skater

from collections import deque

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

dist = [[-1] * W for _ in range(H)]
dist[x1][y1] = 0
q = deque()
q.append((x1, y1))

while q:
    (x, y) = q.popleft()
    if (x, y) == (x2, y2):
        break
    for vx, vy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        for k in range(1, K+1):
            nx = x + vx*k
            ny = y + vy*k
            if nx < 0 or nx >= H or ny < 0 or ny >= W or grid[nx][ny] == '@':
                break
            if dist[nx][ny] != -1 and dist[nx][ny] != dist[x][y]:
                break
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

print(dist[x2][y2])

Submission status: Wrong Answer

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=9**9]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(-1,0),(0,-1),(0,1),(1,0):
  for z in range(k):
   if(h>(i:=s+y*~z)>-1<(j:=t+x*~z)<w)-1or'.'<m[i][j]or d[i*w+j]<=p:break
   q+=(i,j),;d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x] + 1: break
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()

Submission status: Wrong Answer

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


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

        while update:
            x,y = update.popleft()
            cord[y][x] = '#'
            queue.append((nx,ny,dep+1))

    return -1

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

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = 'S'

print(bfs(xg,yg))
'''
bfs(xg,yg)
for i in cord:
    print(*i)
'''

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = [(0, (x1, y1))]
    while Q:
        curr, (x, y) = heapq.heappop(Q)
        for dx, dy in zip(DX, DY):
            for k in range(1, K+1):
                # ヒープキューで管理していることから考えると
                # 値が存在する場所と比較しても更新できることはない。
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if dist[X][Y] < INF:
                    break
                if c[X][Y] == "@":
                    break
                # これ実質的に距離はcurrだけでよいのだけど
                dist[X][Y] = curr+1
                heapq.heappush(Q, (curr+1, (X, Y)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            return
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = [(0, (x1, y1))]
    while Q:
        curr, (x, y) = heapq.heappop(Q)
        for dx, dy in zip(DX, DY):
            for k in range(1, K+1):
                # ヒープキューで管理していることから考えると
                # 値が存在する場所と比較しても更新できることはない。
                if not (0 <= x + k*dx < H):
                    break
                if not (0 <= y + k*dy < W):
                    break
                if dist[x+k*dx][y+k*dy] >= 0:
                    break
                if c[x+k*dx][y+k*dy] == "@":
                    break
                # これ実質的に距離はcurrだけでよいのだけど
                dist[x+k*dx][y+k*dy] = curr+1
                heapq.heappush(Q, (curr+1, (x+k*dx, y+k*dy)))
                if dist[x2][y2] > 0:
                    break
            if dist[x2][y2] > 0:
                break
        if dist[x2][y2] > 0:
            break

    print(dist[x2][y2])
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = [None]*H
    for i in range(H):
        c[i] = input()
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # 難しさがわからないのでダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    prev = [[None]*W for _ in range(H)]
    Q = [(dist[x1][y1], (x1, y1))]
    while Q:
        curr, (x, y) = heapq.heappop(Q)
        for dx, dy in zip(DX, DY):
            if not (0 <= x + dx < H):
                continue
            if not (0 <= y + dy < W):
                continue
            for k in range(1, K+1):
                # ヒープキューで管理していることから考えると
                # 値が存在する場所と比較しても更新できることはない。
                if not (0 <= x + k*dx < H):
                    break
                if not (0 <= y + k*dy < W):
                    break
                if dist[x+k*dx][y+k*dy] >= 0:
                    break
                if c[x+k*dx][y+k*dy] == "@":
                    break
                dist[x+k*dx][y+k*dy] = curr+1
                heapq.heappush(Q, (curr+1, (x+k*dx, y+k*dy)))
                if dist[x2][y2] >= 0:
                    break
            if dist[x2][y2] >= 0:
                break
        if dist[x2][y2] >= 0:
            break
    print(dist[x2][y2])

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] > DP[x][y]+1):
                break
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
            if nx==gx and ny==gy:
                print(DP[nx][ny])
                exit()
print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = [None]*H
    for i in range(H):
        c[i] = input()
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # 難しさがわからないのでダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    prev = [[None]*W for _ in range(H)]
    Q = [(dist[x1][y1], (x1, y1))]
    while Q:
        curr, (x, y) = heapq.heappop(Q)
        for dx, dy in zip(DX, DY):
            if not (0 <= x + dx < H):
                continue
            if not (0 <= y + dy < W):
                continue
            for k in range(1, K+1):
                # ヒープキューで管理していることから考えると
                # 値が存在する場所と比較しても更新できることはない。
                if not (0 <= x + k*dx < H):
                    break
                if not (0 <= y + k*dy < W):
                    break
                if dist[x+k*dx][y+k*dy] > 0:
                    break
                if c[x+k*dx][y+k*dy] == "@":
                    break
                dist[x+k*dx][y+k*dy] = curr+1
                heapq.heappush(Q, (curr+1, (x+k*dx, y+k*dy)))
                if dist[x2][y2] > 0:
                    break
            if dist[x2][y2] > 0:
                break
        if dist[x2][y2] > 0:
            break
    print(dist[x2][y2])

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(1,k+1):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] > DP[x][y]+1):
                break
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))

ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth,stw,glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

q = [(0,x1-1,y1-1,0,())]
while(q):
  qq = []
  for a,x,y,kk,d in q:
    #print(x,y,c[x][y])
    if c[x][y] == '.':
      c[x][y] = a
    else:
      if a < c[x][y]:
        c[x][y] = a
      else:
        continue
    # c[x][y] = min(c[x][y],a)
    # c[x][y] = a
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      if 0 <= x+dx < h and 0 <= y+dy < w and c[x+dx][y+dy] != '@':
        if kk == 0 or d != (dx,dy):
          nk = k-1
          na = a+1
        else:
          nk = kk-1
          na = a
        if c[x+dx][y+dy] == '.' or c[x+dx][y+dy] >= na:
          qq.append((na,x+dx,y+dy,nk,(dx,dy)))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)

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 (visited[gy][gx][0] | visited[gy][gx][1] | visited[gy][gx][2] | visited[gy][gx][3]) == False:
    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")
"""