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 int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector <pi> adj[10000005];
int cnt, n, q;
struct node{
int s, e, m;
int nd, nd2;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
nd = cnt++;
nd2 = cnt++;
if(s == e){
adj[s].push_back({nd2, 0});
adj[nd].push_back({s, 0});
}
else{
l = new node(s, m);
r = new node(m+1, e);
adj[nd].push_back({l->nd, 0});
adj[nd].push_back({r->nd, 0});
adj[r->nd2].push_back({nd2, 0});
adj[l->nd2].push_back({nd2, 0});
}
}
void upd(int a, int b, int u, int v){
if(s == a && b == e){
adj[u].push_back({nd, v});
return;
}
if(b <= m)l->upd(a, b, u, v);
else if(a > m)r->upd(a, b, u, v);
else l->upd(a, m, u, v), r->upd(m+1, b, u, v);
}
void upd2(int a, int b, int u, int v){
if(s == a && b == e){
adj[nd2].push_back({u, v});
return;
}
if(b <= m)l->upd2(a, b, u, v);
else if(a > m)r->upd2(a, b, u, v);
else l->upd2(a, m, u, v), r->upd2(m+1, b, u, v);
}
}*root;
char A[6000005]; int r, c;
inline int conv(int x, int y){
return (x - 1) * c + y;
}
int ptr[10000005];
int dist[10000005];
void solve(){
cin >> r >> c >> n;
int a, b, cc, d; cin >> a >> b >> cc >> d;
cnt = r * c + 1;
root = new node(1, r * c);
if(r > c){
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++)cin >> A[conv(j, i)];
}
swap(r, c);
}
else for(int i = 1; i <= r; i++)for(int j = 1; j <= c; j++)cin >> A[conv(i, j)];
for(int i = 1; i <= r * c; i++){
if(i > c && A[i - c] == '.')adj[i].push_back({i - c, 0});
if(i <= c * (r - 1) && A[i + c] == '.')adj[i].push_back({i + c, 0});
if(i % c != 1 && A[i - 1] == '.')adj[i].push_back({i - 1, 0});
if(i % c && A[i + 1] == '.')adj[i].push_back({i + 1, 0});
int aaa = (i - 1) / c + 1, bbb = (i - 1) % c + 1;
for(int j = max(-n, -aaa + 1); j <= min(n, r - aaa); j++){
if((i - 1) / c + 1 + j <= 0 || (i - 1) / c + 1 + j > r)continue;
if(j == -n || j == n){
int lft = max(1, bbb - n + 1);
int rgt = min(c, bbb + n - 1);
root->upd(conv(aaa + j, lft), conv(aaa + j, rgt), i, 1);
}
else{
int lft = max(1, bbb - n);
int rgt = min(c, bbb + n);
root->upd(conv(aaa + j, lft), conv(aaa + j, rgt), i, 1);
}
}
}
for(int i = 1; i <= cnt; i++)dist[i] = 2e9;
dist[conv(a, b)] = 0;
//for(auto [i, j] : adj[conv(a, b)])cout << i << ' ' << j << '\n';
deque <int> dq;
const int os = (int)5e6;
ptr[os] = conv(a, b);
int cur = os - 1, cur2 = os;
//dq.push_back(conv(a, b));
while(1){
//int x = dq.front(); dq.pop_front();
int x = ptr[++cur];
if(cur > cur2)break;
for(auto [i, j] : adj[x]){
if(dist[i] > dist[x] + j){
dist[i] = dist[x] + j;
//if(j)dq.push_back(i);
//else dq.push_front(i);
if(j)ptr[++cur2] = i;
else ptr[cur--] = i;
}
}
}
//for(int i = 1; i <= cnt; i++)cout << dist[i] << ' ';
cout << dist[conv(cc, d)];
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message (stderr)
Main.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
127 | main(){
| ^~~~
# | 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... |