#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)(x).size())
#define sumof(x) accumulate(all(x), 0ll)
const int dx[]={1, -1, 0, 0, 1, 1, -1, -1}, dy[]={0, 0, 1, -1, 0, 1, -1, 1, -1};
int n, r, c;
int sr, sc, gr, gc;
template<class T>
struct Vec{
int size;
T data[6000001];
void clear(){
size=0;
}
void push_back(const T &x){
data[size++]=x;
}
auto & operator[](int x){
return data[x];
}
const auto & operator[](int x) const {
return data[x];
}
};
template<class T>
struct Queue{
int bq, eq;
T data[6000001];
int size() const {
return eq-bq+1;
}
void clear(){
bq=1; eq=0;
}
T & front(){
return data[bq];
}
void push(const T &x){
data[++eq]=x;
}
void pop(){
++bq;
}
};
void solve(){
cin >> r >> c >> n;
cin >> sr >> sc >> gr >> gc;
vector<vector<char>> a(r+1, vector<char>(c+1));
vector<vector<int>> dist(r+1, vector<int>(c+1, 1e9));
vector<vector<pair<int, int>>> dist2(r+1, vector<pair<int, int>>(c+1));
for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j) cin >> a[i][j];
Vec<pair<int, int>> roots;
roots.push_back({sr, sc});
Queue<pair<int, int>> q;
auto bfs_white=[&](int distance){
q.clear();
for (int i=0; i<roots.size; ++i) q.push({roots[i].first, roots[i].second}), dist[roots[i].first][roots[i].second]=distance;
roots.clear();
while (q.size()){
int u=q.front().first, v=q.front().second;
q.pop();
for (int i=0; i<4; ++i){
int x=u+dx[i], y=v+dy[i];
if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9) continue;
if (a[x][y]=='.'){
dist[x][y]=distance;
q.push({x, y});
}else{
roots.push_back({x, y}), dist[x][y]=distance+1;
}
}
}
};
Queue<pair<int, int>> qq;
auto bfs_black=[&](int distance){
qq.clear();
for (int i=0; i<roots.size; ++i) qq.push(roots[i]);
roots.clear();
while (qq.size()){
int u=qq.front().first, v=qq.front().second;
roots.push_back({u, v});
qq.pop();
for (int i=0; i<4; ++i){
int x=u+dx[i], y=v+dy[i];
if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9) continue;
int d2x=dist2[u][v].first, d2y=dist2[u][v].second;
d2x+=!!dx[i], d2y+=!!dy[i];
if (d2x>=n || d2y>=n) continue;
dist[x][y]=distance;
dist2[x][y]={d2x, d2y};
qq.push({x, y});
}
}
};
int cur=0;
while (dist[gr][gc]>=1e9){
bfs_white(cur);
bfs_black(++cur);
}
cout << dist[gr][gc];
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve();
return 0;
}
Compilation message
passport.cpp: In function 'void solve()':
passport.cpp:23:11: warning: 'roots.Vec<std::pair<int, int> >::size' may be used uninitialized in this function [-Wmaybe-uninitialized]
23 | data[size++]=x;
| ~~~~^
passport.cpp:61:24: note: 'roots.Vec<std::pair<int, int> >::size' was declared here
61 | Vec<pair<int, int>> roots;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
141136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
141344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
141344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
141344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
141136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
