#include <array>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int R, C, K, Sr, Sc, Gr, Gc;
cin >> R >> C >> K >> Sr >> Sc >> Gr >> Gc;
K = 1 - K; Sr--; Sc--; Gr--; Gc--;
vector<string> A(R);
for(string& a : A) {
cin >> a;
for(char& c : a) c = c == '#';
}
// {гЃ“гЃ“гЃ«иѕїг‚ЉзќЂгЃЏгЃѕгЃ§гЃ«еї…и¦ЃгЃЄеЎ—г‚ЉгЃ¤гЃ¶гЃ—е›ћж•°, жњЂеѕЊгЃ®еЎ—г‚ЉгЃ¤гЃ¶гЃ—гЃ«г‚€гЃЈгЃ¦иЎЊгЃ‘г‚‹зё¦гЃ®з§»е‹•й‡Џ, жњЂеѕЊгЃ®еЎ—г‚ЉгЃ¤гЃ¶гЃ—гЃ«г‚€гЃЈгЃ¦иЎЊгЃ‘г‚‹жЁЄгЃ®з§»е‹•й‡Џ} г‚’жЊЃгЃ¤
// 各レイヤー 3 フェーズの BFS
// 1. 4 ж–№еђ‘гЃ« 白なら移動 / 黒なら (K - 1, K - 1) гЃ§еЎ—г‚ЉгЃ¤гЃ¶гЃ—иїЅеЉ
// 2. жЁЄж–№еђ‘гЃ«з§»е‹•
// 3. зё¦ж–№еђ‘гЃ«з§»е‹•
vector cost(R, vector(C, array{INT_MAX, 0, 0}));
vector<pair<int, int>> q1, q2;
auto push = [&](vector<pair<int, int>>& q, int r, int c, int x, int y, int z) -> void {
if(r < 0 || r >= R || c < 0 || c >= C) return;
if(cost[r][c][0] <= x) return;
cost[r][c] = {x, y, z};
q.emplace_back(r, c);
};
auto push2 = [&](int r, int c, int x) -> void {
if(r < 0 || r >= R || c < 0 || c >= C) return;
if(A[r][c]) push(q2, r, c, x + 1, K, K);
else push(q1, r, c, x, 0, 0);
};
push(q1, Sr, Sc, 0, 0, 0);
while(q1.size()) {
// жЁЄж–№еђ‘гЃ«з§»е‹•
for(int i = 0; i < q1.size(); i++) {
const auto [r, c] = q1[i];
const auto [x, y, z] = cost[r][c];
if(z == 0) continue;
push(q1, r, c - 1, x, y, z + 1);
push(q1, r, c + 1, x, y, z + 1);
}
// зё¦ж–№еђ‘гЃ«з§»е‹•
for(int i = 0; i < q1.size(); i++) {
const auto [r, c] = q1[i];
const auto [x, y, z] = cost[r][c];
if(y == 0) continue;
push(q1, r - 1, c, x, y + 1, z);
push(q1, r + 1, c, x, y + 1, z);
}
// BFS
for(int i = 0; i < q1.size(); i++) {
const auto [r, c] = q1[i];
const auto [x, y, z] = cost[r][c];
push2(r - 1, c, x);
push2(r + 1, c, x);
push2(r, c - 1, x);
push2(r, c + 1, x);
}
swap(q1, q2);
q2.clear();
}
cout << cost[Gr][Gc][0] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |