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>
#define forin(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 6e6 + 10;
int r, c, n, x, y, u, v, dp;
int row[4] = {0, -1, 0, 1};
int col[4] = {1, 0, -1, 0};
string s[N];
vector<vector<int>> f, par1, par2, vis, red;
queue<pair<int, int>> tmp;
void create(vector<vector<int>> &a) {
a.resize(r + 2);
forin(i,1,r + 1) a[i].resize(c + 2);
}
int root1(int i, int j) {
return (par1[i][j] == j) ? j : par1[i][j] = root1(i, par1[i][j]);
}
int root2(int i, int j) {
return (par2[i][j] == i) ? i : par2[i][j] = root2(par2[i][j], j);
}
bool check(int i, int j) {
if(i < 1 || r < i || j < 1 || c < j) return 0;
return 1;
}
void up(int x, int y) {
if(!check(x, y)) return;
if(f[x][y]) return;
f[x][y] = dp + 1;
par1[x][y] = y + 1;
par2[x][y] = x + 1;
tmp.push({x, y});
}
void bfs(int x, int y, queue<pair<int, int>> &p) {
queue<pair<int, int>> q;
q.push({x, y});
while(!q.empty()) {
int x1, y1; tie(x1, y1) = q.front(); q.pop();
f[x1][y1] = dp;
forin(k,0,3) {
int u1 = x1 + row[k];
int v1 = y1 + col[k];
if(!check(u1, v1) || red[u1][v1]) continue;
bool ok = 0;
ok |= (s[u1][v1] == '.');
ok |= (f[u1][v1] == dp);
if(!ok) continue;
red[u1][v1] = 1;
if(s[u1][v1] == '.') up(u1, v1);
p.push({u1, v1});
q.push({u1, v1});
}
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("Task.inp","r")) {
freopen("Task.inp","r",stdin);
freopen("WA.out","w",stdout);
}
cin>>r>>c>>n;
create(f);
create(vis);
create(red);
cin>>x>>y;
cin>>u>>v;
forin(i,1,r) {
cin>>s[i];
s[i] = " " + s[i];
}
create(par1);
create(par2);
forin(i,1,r + 1) forin(j,1,c + 1) {
par1[i][j] = j;
par2[i][j] = i;
}
up(x, y);
while(true) {
dp++;
queue<pair<int, int>> q;
while(!tmp.empty()) {
int x1, y1; tie(x1, y1) = tmp.front(); tmp.pop();
if(red[x1][y1]) continue;
red[x1][y1] = 1;
q.push({x1, y1});
bfs(x1, y1, q);
}
while(!q.empty()) {
int x1, y1; tie(x1, y1) = q.front(); q.pop();
vis[x1][y1] = 1;
vector<int> vt;
forin(k,0,3) {
int u1 = x1 + row[k];
int v1 = y1 + col[k];
if(!check(u1, v1) || !vis[u1][v1]) continue;
vt.push_back(k);
}
if(vt.empty()) {
forin(i,-n,n) forin(j,-n,n) if(!(abs(i) == n && abs(j) == n) && check(x1 + i, y1 + j)) {
up(x1 + i, y1 + j);
}
}
else if(vt.size() == 1) {
int k = vt[0];
int t = - (row[k] + col[k]);
if(row[k]) {
up(x1 + t * (n - 1), y1 + n);
up(x1 + t * (n - 1), y1 - n);
int u1 = x1 + t * n;
int v1 = max(1, y1 - n + 1);
if(!check(u1, v1)) continue;
while(true) {
v1 = root1(u1, v1);
if(v1 > min(c, y1 + n - 1)) break;
up(u1, v1);
}
}
else {
up(x1 + n, y1 + t * (n - 1));
up(x1 - n, y1 + t * (n - 1));
int u1 = max(1, x1 - n + 1);
int v1 = y1 + t * n;
if(!check(u1, v1)) continue;
while(true) {
u1 = root2(u1, v1);
if(u1 > min(r, x1 + n - 1)) break;
up(u1, v1);
}
}
}
else if((vt[0] - vt[1]) % 2) {
if(vt[0] % 2) swap(vt[0], vt[1]);
int t1 = - (row[vt[1]] + col[vt[1]]);
int t2 = - (row[vt[0]] + col[vt[0]]);
up(x1 + t1 * (n - 1), y1 + n);
up(x1 + t1 * (n - 1), y1 - n);
up(x1 + n, y1 + t2 * (n - 1));
up(x1 - n, y1 + t2 * (n - 1));
}
}
if(f[u][v]) return cout<<f[u][v] - 1, 0;
}
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | freopen("Task.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | freopen("WA.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |