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;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
vi d[MAXN];
vector<bool> mt[MAXN];
int n, m, kv;
vii zadnje, nove;
bool izvan(int r, int s){
if(r < 1 or s < 1 or r > n or s > m) return 1;
return 0;
}
void expand_na_bijele(int ud){
queue<ii> q;
for(auto &x : zadnje) q.push(x);
while(!q.empty()){
int r, s;
tie(r, s) = q.front();
q.pop();
for(int k=0; k<4; k++){
int nr = r + dx[k], ns = s + dy[k];
if(izvan(nr, ns)) continue;
if(mt[nr][ns]) continue;
if(d[nr][ns] != -1) continue;
d[nr][ns] = ud;
nove.PB({nr, ns});
q.push({nr, ns});
}
}
}
void expand_kvadrat(int ud){
queue<pair<ii, int>> q;
for(auto &x : zadnje) q.push({x, kv - 1});
while(!q.empty()){
int r, s, ost;
tie(r, s) = q.front().X;
ost = q.front().Y;
q.pop();
if(ost == 0) continue;
for(int k=0; k<8; k++){
int nr = r + dx[k], ns = s + dy[k];
if(izvan(nr, ns)) continue;
if(d[nr][ns] != -1) continue;
d[nr][ns] = ud;
nove.PB({nr, ns});
q.push({{nr, ns}, ost - 1});
}
}
}
void expand_u_4(int ud){
for(auto &x : zadnje){
for(int k=0; k<4; k++){
int nr = x.X + dx[k], ns = x.Y + dy[k];
if(izvan(nr, ns)) continue;
if(d[nr][ns] != -1) continue;
d[nr][ns] = ud;
nove.PB({nr, ns});
}
}
}
void solve(){
int sx, sy, ex, ey;
cin >> n >> m >> kv >> sx >> sy >> ex >> ey;
for(int i=1; i<=n; i++){
d[i].resize(m + 1, -1);
mt[i].resize(m + 1, 1);
for(int j=1; j<=m; j++){
char x;
cin >> x;
if(x == '.') mt[i][j] = 0;
}
}
zadnje.PB({sx, sy});
d[sx][sy] = 0;
expand_na_bijele(0);
for(auto &x : nove) zadnje.PB(x);
nove.clear();
for(int i=1; i<=n + m; i++){
expand_kvadrat(i);
swap(zadnje, nove);
nove.clear();
expand_u_4(i);
for(auto &x : nove) zadnje.PB(x);
nove.clear();
expand_na_bijele(i);
swap(zadnje, nove);
nove.clear();
}
cout << d[ex][ey] << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while(tt--) solve();
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... |