解法
いくつか解法があるが, ダイクストラで解く. コストが \(\frac{1}{k}\) として, 向きを変えたときまたはゴールしたときに,小数点以下の切り上げをする. 少数だと扱いにくいので,コストを \(1\) にして,\(k\) の倍数に切り上げる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w,k; cin >> h >> w >> k;
pll s,t; cin >> s.first >> s.second >> t.first >> t.second;
s.first--;
t.first--;
s.second--;
t.second--;
min_priority_queue<pll> q;
auto id = [&](ll x, ll y, ll r) -> ll {
return (x*w + y)*4 + r;
};
auto push = [&](ll x, ll y, ll r, ll d) -> void {
ll v = id(x,y,r);
if(chmin(dis[v],d)){
q.push({d,v});
}
};
rep(i,4){
push(s.first, s.second, i, 0);
}
while(q.size()){
auto [cd, cv] = q.top(); q.pop();
if(dis[cv] != cd) continue;
ll cx = cv / 4 / w;
ll cy = (cv / 4) % w;
ll cr = cv % 4;
vll dx = {-1,0,1,0};
vll dy = {0,-1,0,1};
rep(i,4){
ll nx = cx + dx[i];
ll ny = cy + dy[i];
if(in(nx,h) && in(ny,w) && c[nx][ny]=='.'){
if(i == cr) push(nx, ny, i, cd+1);
else push(nx, ny, i, ceil(cd,k)*k + 1);
}
}
}
ll ans = INFL;
rep(i,4) chmin(ans, dis[id(t.first, t.second, i)]);
if(ans >= INFL) {
cout << -1 << endl;
return 0;
}
cout << ceil(ans,k)*k/k << endl; // rem: ceil mod k
return 0;
}