This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(a) (a).begin(), (a).end()
using pii = pair<int, int>;
const int inf = 1e7;
int r, c, n;
int sr, sc, gr, gc;
vector<string> A;
int main() {
cin >> r >> c >> n;
if(c > r) {
swap(r, c);
cin >> sc >> sr >> gc >> gr;
A = vector<string>(r, string(c, '#'));
for(int i = 0; i < c; i++) {
string s; cin >> s;
for(int j = 0; j < r; j++) {
A[j][i] = s[j];
}
}
}
else {
cin >> sr >> sc >> gr >> gc;
A = vector<string>(r);
for(int i = 0; i < c; i++) {
cin >> A[i];
}
}
sr--, sc--, gr--, gc--;
// for(int i = 0; i < r; i++) {
// cerr << A[i] << "\n";
// }
// c < 2500
vector<vector<int>> dist(r, vector<int>(c, inf));
vector<vector<bool>> visited(r, vector<bool>(c));
vector<set<int>> checked(c);
deque<pii> deq;
vector<pii> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
auto transition = [&](int row, int s, int e, int d) {
// cerr << "transit: " << row << " " << s << " " << e << " " << d << "\n";
for(int i = s; i <= e; i++) {
// if(dist[row][i] <= d+1) break;
if(dist[row][i] > d+1) {
dist[row][i] = d+1;
deq.push_back({row, i});
}
}
for(int i = e; i >= s; i--) {
//if(dist[row][i] <= d+1) break;
if(dist[row][i] > d+1) {
dist[row][i] = d+1;
deq.push_back({row, i});
}
}
};
dist[sr][sc] = 0;
deq.push_back({sr, sc});
while(!deq.empty()) {
int i = deq.front().fi, j = deq.front().se;
deq.pop_front();
//cerr << i << " " << j << "?\n";
if(visited[i][j]) continue;
//cerr << i << " " << j << "!\n";
visited[i][j] = true;
for(auto d : dir) {
int ii = i+d.fi, jj = j+d.se;
if(ii < 0 || ii >= r || jj < 0 || jj >= c) continue;
if(A[ii][jj] == '.' && dist[ii][jj] > dist[i][j]) {
dist[ii][jj] = dist[i][j];
deq.push_front({ii, jj});
}
}
int li = max(0, i-(n-1)), ri = min(n-1, i+(n-1));
if(!checked[j].empty()) {
auto it = checked[j].lower_bound(i);
if(it == checked[j].end()) {
it = prev(it);
li = max(li, (*it)+n);
}
else {
ri = min(ri, (*it)-n);
if(it != checked[j].begin()) {
it = prev(it);
li = max(li, (*it)+n);
}
}
}
checked[j].insert(i);
if(li <= ri) {
for(int row = li; row <= ri; row++) {
transition(row, max(0, j-n), min(c-1, j+n), dist[i][j]);
}
}
if(i-n >= 0) {
transition(i-n, max(0, j-n+1), min(c-1, j+n-1), dist[i][j]);
}
if(i+n < r) {
transition(i+n, max(0, j-n+1), min(c-1, j+n-1), dist[i][j]);
}
}
cout << dist[gr][gc] << "\n";
return 0;
}
# | 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... |