Buggy python submission (verdict: Time Limit Exceeded):
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())

class Dijkstra():
    class Edge():
        def __init__(self, _to, _type):
            self.to = _to
            self.type=_type

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add(self, _from, _to, _type):
        self.G[_from].append(self.Edge(_to, _type))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e.type==0:
                    if d[e.to] > d[v]-d[v]%K+K*(d[v]%K>0):
                        d[e.to]=d[v]-d[v]%K+K*(d[v]%K>0)
                        heapq.heappush(que,(d[e.to],e.to))
                else:
                    if d[e.to] >d[v]+1:
                        d[e.to]=d[v]+1
                        heapq.heappush(que,(d[e.to],e.to))
        return d

x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
pond=Dijkstra(4*H*W)
for i in range(H*W):
    h=i//W
    w=i%W
    if c[h][w]==".":
        if h!=0 and c[h-1][w]==".":
            pond.add(4*i,4*(i-W),1)
        if h!=H-1 and c[h+1][w]==".":
            pond.add(4*i+2,4*(i+W)+2,1)
        if w!=0 and c[h][w-1]==".":
            pond.add(4*i+3,4*(i-1)+3,1)
        if w!=W-1 and c[h][w+1]==".":
            pond.add(4*i+1,4*(i+1)+1,1)
        for j in range(4):
            pond.add(4*i+j,4*i+(j+1)%4,0)

s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1
ans=pond.shortest_path(4*s)[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Fixed submission:
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())
x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1

import heapq
que = []
d = [float("inf")] * (4*H*W)
d[4*s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4*s))

while len(que) != 0:
    cost, v = heapq.heappop(que)
    if d[v] < cost: continue

    for j in range(4):
        nv=v-v%4+(v%4+j)%4
        if d[nv]>d[v]-d[v]%K+K*(d[v]%K>0):
            d[nv]=d[v]-d[v]%K+K*(d[v]%K>0)
            heapq.heappush(que,(d[nv],nv))

    i=v//4
    h,w=i//W,i%W
    if v%4==0:
        if h!=0 and c[h-1][w]==".":
            if d[v-4*W]>d[v]+1:
                d[v-4*W]=d[v]+1
                heapq.heappush(que,(d[v-4*W],v-4*W))
    elif v%4==2:
        if h!=H-1 and c[h+1][w]==".":
            if d[v+4*W]>d[v]+1:
                d[v+4*W]=d[v]+1
                heapq.heappush(que,(d[v+4*W],v+4*W))
    elif v%4==1:
        if w!=W-1 and c[h][w+1]==".":
            if d[v+4]>d[v]+1:
                d[v+4]=d[v]+1
                heapq.heappush(que,(d[v+4],v+4))
    else:
        if w!=0 and c[h][w-1]==".":
            if d[v-4]>d[v]+1:
                d[v-4]=d[v]+1
                heapq.heappush(que,(d[v-4],v-4))

ans=d[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())

class Dijkstra():
    class Edge():
        def __init__(self, _to, _type):
            self.to = _to
            self.type=_type

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add(self, _from, _to, _type):
        self.G[_from].append(self.Edge(_to, _type))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10**18] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e.type==0:
                    if d[e.to] > d[v]-d[v]%K+K*(d[v]%K>0):
                        d[e.to]=d[v]-d[v]%K+K*(d[v]%K>0)
                        heapq.heappush(que,(d[e.to],e.to))
                else:
                    if d[e.to] >d[v]+1:
                        d[e.to]=d[v]+1
                        heapq.heappush(que,(d[e.to],e.to))
        return d

x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
pond=Dijkstra(4*H*W)
for i in range(H*W):
    h=i//W
    w=i%W
    if c[h][w]==".":
        if h!=0 and c[h-1][w]==".":
            pond.add(4*i,4*(i-W),1)
        if h!=H-1 and c[h+1][w]==".":
            pond.add(4*i+2,4*(i+W)+2,1)
        if w!=0 and c[h][w-1]==".":
            pond.add(4*i+3,4*(i-1)+3,1)
        if w!=W-1 and c[h][w+1]==".":
            pond.add(4*i+1,4*(i+1)+1,1)
        for j in range(4):
            pond.add(4*i+j,4*i+(j+1)%4,0)

s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1
ans=pond.shortest_path(4*s)[4*g]
if ans>=10**18:
    print(-1)
else:
    print(ans//K+(ans%K>0))


Fixed submission:
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())
x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1

import heapq
que = []
d = [float("inf")] * (4*H*W)
d[4*s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4*s))

while len(que) != 0:
    cost, v = heapq.heappop(que)
    if d[v] < cost: continue

    for j in range(4):
        nv=v-v%4+(v%4+j)%4
        if d[nv]>d[v]-d[v]%K+K*(d[v]%K>0):
            d[nv]=d[v]-d[v]%K+K*(d[v]%K>0)
            heapq.heappush(que,(d[nv],nv))

    i=v//4
    h,w=i//W,i%W
    if v%4==0:
        if h!=0 and c[h-1][w]==".":
            if d[v-4*W]>d[v]+1:
                d[v-4*W]=d[v]+1
                heapq.heappush(que,(d[v-4*W],v-4*W))
    elif v%4==2:
        if h!=H-1 and c[h+1][w]==".":
            if d[v+4*W]>d[v]+1:
                d[v+4*W]=d[v]+1
                heapq.heappush(que,(d[v+4*W],v+4*W))
    elif v%4==1:
        if w!=W-1 and c[h][w+1]==".":
            if d[v+4]>d[v]+1:
                d[v+4]=d[v]+1
                heapq.heappush(que,(d[v+4],v+4))
    else:
        if w!=0 and c[h][w-1]==".":
            if d[v-4]>d[v]+1:
                d[v-4]=d[v]+1
                heapq.heappush(que,(d[v-4],v-4))

ans=d[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Buggy python submission (verdict: Runtime Error):
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())

class Dijkstra():
    class Edge():
        def __init__(self, _to, _type):
            self.to = _to
            self.type=_type

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add(self, _from, _to, _type):
        self.G[_from].append(self.Edge(_to, _type))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10**18] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e.type==0:
                    if d[e.to] > d[v]-d[v]%K+K*(d[v]%K>0):
                        d[e.to]=d[v]-d[v]%K+K*(d[v]%K>0)
                        heapq.heappush(que,(d[e.to],e.to))
                else:
                    if d[e.to] >d[v]+1:
                        d[e.to]=d[v]+1
                        heapq.heappush(que,(d[e.to],e.to))
        return d

x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
pond=Dijkstra(4*H*W)
for i in range(H*W):
    h=i//W
    w=i%W
    if c[h][w]==".":
        if h!=0 and c[h-1][w]==".":
            pond.add(4*i,4*(i-W),1)
        if h!=H-1 and c[h+1][w]==".":
            pond.add(4*i+2,4*(i+W)+2,1)
        if w!=0 and c[h][w-1]==".":
            pond.add(4*i+3,4*(i-1)+3,1)
        if w!=W-1 and c[h][w+1]==".":
            pond.add(4*i+1,4*(i+1)+1,1)
        for j in range(4):
            pond.add(4*i+j,4*i+(j+1)%4)

s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1
ans=pond.shortest_path(4*s)[4*g]
if ans>=10**18:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Fixed submission:
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())
x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1

import heapq
que = []
d = [float("inf")] * (4*H*W)
d[4*s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4*s))

while len(que) != 0:
    cost, v = heapq.heappop(que)
    if d[v] < cost: continue

    for j in range(4):
        nv=v-v%4+(v%4+j)%4
        if d[nv]>d[v]-d[v]%K+K*(d[v]%K>0):
            d[nv]=d[v]-d[v]%K+K*(d[v]%K>0)
            heapq.heappush(que,(d[nv],nv))

    i=v//4
    h,w=i//W,i%W
    if v%4==0:
        if h!=0 and c[h-1][w]==".":
            if d[v-4*W]>d[v]+1:
                d[v-4*W]=d[v]+1
                heapq.heappush(que,(d[v-4*W],v-4*W))
    elif v%4==2:
        if h!=H-1 and c[h+1][w]==".":
            if d[v+4*W]>d[v]+1:
                d[v+4*W]=d[v]+1
                heapq.heappush(que,(d[v+4*W],v+4*W))
    elif v%4==1:
        if w!=W-1 and c[h][w+1]==".":
            if d[v+4]>d[v]+1:
                d[v+4]=d[v]+1
                heapq.heappush(que,(d[v+4],v+4))
    else:
        if w!=0 and c[h][w-1]==".":
            if d[v-4]>d[v]+1:
                d[v-4]=d[v]+1
                heapq.heappush(que,(d[v-4],v-4))

ans=d[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())

class Dijkstra():
    class Edge():
        def __init__(self, _to, _type):
            self.to = _to
            self.type=_type

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add(self, _from, _to, _type):
        self.G[_from].append(self.Edge(_to, _type))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10**18] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e.type==0:
                    if d[e.to] > d[v]-d[v]%K+K*(d[v]%K>0):
                        d[e.to]=d[v]-d[v]%K+K*(d[v]%K>0)
                        heapq.heappush(que,(d[e.to],e.to))
                else:
                    if d[e.to] >d[v]+1:
                        d[e.to]=d[v]+1
                        heapq.heappush(que,(d[e.to],e.to))
        return d

x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
pond=Dijkstra(4*H*W)
for i in range(H*W):
    h=i//W
    w=i%W
    if c[h][w]==".":
        if h!=0 and c[h-1][w]==".":
            pond.add(4*i,4*(i-W),1)
        if h!=H-1 and c[h+1][w]==".":
            pond.add(4*i+2,4*(i+W)+2,1)
        if w!=0 and c[h][w-1]==".":
            pond.add(4*i+3,4*(i-1)+3,1)
        if w!=W-1 and c[h][w+1]==".":
            pond.add(4*i+1,4*(i+1)+1,1)
        for j in range(4):
            for k in range(4):
                if j!=k:
                    pond.add(4*i+k,4*i+j,0)

s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1
ans=pond.shortest_path(4*s)[4*g]
if ans>=10**18:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Fixed submission:
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())
x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1

import heapq
que = []
d = [float("inf")] * (4*H*W)
d[4*s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4*s))

while len(que) != 0:
    cost, v = heapq.heappop(que)
    if d[v] < cost: continue

    for j in range(4):
        nv=v-v%4+(v%4+j)%4
        if d[nv]>d[v]-d[v]%K+K*(d[v]%K>0):
            d[nv]=d[v]-d[v]%K+K*(d[v]%K>0)
            heapq.heappush(que,(d[nv],nv))

    i=v//4
    h,w=i//W,i%W
    if v%4==0:
        if h!=0 and c[h-1][w]==".":
            if d[v-4*W]>d[v]+1:
                d[v-4*W]=d[v]+1
                heapq.heappush(que,(d[v-4*W],v-4*W))
    elif v%4==2:
        if h!=H-1 and c[h+1][w]==".":
            if d[v+4*W]>d[v]+1:
                d[v+4*W]=d[v]+1
                heapq.heappush(que,(d[v+4*W],v+4*W))
    elif v%4==1:
        if w!=W-1 and c[h][w+1]==".":
            if d[v+4]>d[v]+1:
                d[v+4]=d[v]+1
                heapq.heappush(que,(d[v+4],v+4))
    else:
        if w!=0 and c[h][w-1]==".":
            if d[v-4]>d[v]+1:
                d[v-4]=d[v]+1
                heapq.heappush(que,(d[v-4],v-4))

ans=d[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Buggy python submission (verdict: Time Limit Exceeded):
H,W,K=map(int,input().split())

class Dijkstra():
    class Edge():
        def __init__(self, _to, _type):
            self.to = _to
            self.type=_type

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add(self, _from, _to, _type):
        self.G[_from].append(self.Edge(_to, _type))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10**18] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e.type==0:
                    if d[e.to] > d[v]-d[v]%K+K*(d[v]%K>0):
                        d[e.to]=d[v]-d[v]%K+K*(d[v]%K>0)
                        heapq.heappush(que,(d[e.to],e.to))
                else:
                    if d[e.to] >d[v]+1:
                        d[e.to]=d[v]+1
                        heapq.heappush(que,(d[e.to],e.to))
        return d

x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(H)]
pond=Dijkstra(4*H*W)
for i in range(H*W):
    h=i//W
    w=i%W
    if c[h][w]==".":
        if h!=0 and c[h-1][w]==".":
            pond.add(4*i,4*(i-W),1)
        if h!=H-1 and c[h+1][w]==".":
            pond.add(4*i+2,4*(i+W)+2,1)
        if w!=0 and c[h][w-1]==".":
            pond.add(4*i+3,4*(i-1)+3,1)
        if w!=W-1 and c[h][w+1]==".":
            pond.add(4*i+1,4*(i+1)+1,1)
        for j in range(4):
            for k in range(4):
                if j!=k:
                    pond.add(4*i+k,4*i+j,0)

s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1
ans=pond.shortest_path(4*s)[4*g]
if ans>=10**18:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Fixed submission:
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())
x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1

import heapq
que = []
d = [float("inf")] * (4*H*W)
d[4*s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4*s))

while len(que) != 0:
    cost, v = heapq.heappop(que)
    if d[v] < cost: continue

    for j in range(4):
        nv=v-v%4+(v%4+j)%4
        if d[nv]>d[v]-d[v]%K+K*(d[v]%K>0):
            d[nv]=d[v]-d[v]%K+K*(d[v]%K>0)
            heapq.heappush(que,(d[nv],nv))

    i=v//4
    h,w=i//W,i%W
    if v%4==0:
        if h!=0 and c[h-1][w]==".":
            if d[v-4*W]>d[v]+1:
                d[v-4*W]=d[v]+1
                heapq.heappush(que,(d[v-4*W],v-4*W))
    elif v%4==2:
        if h!=H-1 and c[h+1][w]==".":
            if d[v+4*W]>d[v]+1:
                d[v+4*W]=d[v]+1
                heapq.heappush(que,(d[v+4*W],v+4*W))
    elif v%4==1:
        if w!=W-1 and c[h][w+1]==".":
            if d[v+4]>d[v]+1:
                d[v+4]=d[v]+1
                heapq.heappush(que,(d[v+4],v+4))
    else:
        if w!=0 and c[h][w-1]==".":
            if d[v-4]>d[v]+1:
                d[v-4]=d[v]+1
                heapq.heappush(que,(d[v-4],v-4))

ans=d[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))