#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define len(v) (int)((v).size())
template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
for (auto& x : a){
out << x << ' ';
}
out << '\n';
return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &a){
for (size_t i = 0; i < a.size(); ++i){
in >> a[i];
}
return in;
}
mt19937 gen;
int di[4] = {0, 0, -1, 1};
int dj[4] = {-1, 1, 0, 0};
inline void solve() {
int r, c, n;
cin >> r >> c >> n;
int sr, sc, gr, gc;
cin >> sr >> sc >> gr >> gc;
--sr, --sc, --gr, --gc;
vector<vector<char>> a(r, vector<char>(c));
for (int i = 0; i < r; ++i){
for (int j = 0; j < c; ++j){
cin >> a[i][j];
}
}
vector<vector<bool>> us(r, vector<bool>(c, false));
queue<pair<int, int>> q1, q2;
us[sr][sc] = true;
q1.push({sr, sc});
int ans = 0;
while (true){
while (!q1.empty()){
pair<int, int> v = q1.front();
q2.push(v);
q1.pop();
for (int w = 0; w < 4; ++w){
int ui = v.first + di[w];
int uj = v.second + dj[w];
if (ui < 0 || ui >= r || uj < 0 || uj >= c || a[ui][uj] == '#' || us[ui][uj]) continue;
us[ui][uj] = true;
q1.push({ui, uj});
}
}
if (us[gr][gc]){
cout << ans << '\n';
break;
}
++ans;
while (!q2.empty()){
pair<int, int> v = q2.front();
q2.pop();
for (int i = max(v.first - n, 0); i < min(v.first + n + 1, r); ++i){
for (int j = max(v.second - n, 0); j < min(v.second + n + 1, c); ++j){
if (abs(i - v.first) + abs(j - v.second) >= 2 * n) continue;
if (!us[i][j]){
q1.push({i, j});
us[i][j] = true;
}
}
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout.precision(60);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
# | 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... |