#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
int inf = 1e9;
int dl[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int r,c,n;
int xs,ys,xf,yf;
vector<vector<char>>a;
vector<vector<int>>d;
pair<short int,int> new_cells[6000005],cells[6000005];
int ncs,cs;
vector<vector<int>>s;
vector<vector<short int>>ss;
vector<int>ts;
vector<short int>tss;
int lgc,lgr;
vector<vector<bool>> luat;
void updates(int unde,int pos)
{
ts[unde]--;
#pragma GCC ivdep
for (int i = pos; i <= c; i += (i & -i))
s[unde][i]--;
}
void updatess(int unde,int pos)
{
tss[unde]--;
#pragma GCC ivdep
for (int i = pos; i <= r; i += (i & -i))
ss[unde][i]--;
}
int querys(int x,int y)
{
int rsp = 0;
#pragma GCC ivdep
for (int i = y; i > 0; i -= (i & -i))
rsp += s[x][i];
return rsp;
}
int queryss(int x,int y)
{
int rsp = 0;
#pragma GCC ivdep
for (int i = y; i > 0; i -= (i & -i))
rsp += ss[x][i];
return rsp;
}
int s_findnext(int x,int y)
{
int vv = querys(x,y - 1);
if (vv == ts[x])
return -1;
int sumaib = 0;
int st = 0,pas = 1 << lgc;
#pragma GCC ivdep
while (pas != 0)
{
if (st + pas <= c and sumaib + s[x][st + pas] <= vv)
{
st += pas;
sumaib += s[x][st];
}
pas >>= 1;
}
return st + 1;
}
int ss_findnext(int x,int y)
{
int vv = queryss(x,y - 1);
if (vv == tss[x])
return -1;
int sumaib = 0;
int st = 0,pas = 1 << lgr;
#pragma GCC ivdep
while (pas != 0)
{
if (st + pas <= r and sumaib + ss[x][st + pas] <= vv)
{
st += pas;
sumaib += ss[x][st];
}
pas >>= 1;
}
return st + 1;
}
void dfs(int x,int y)
{
//cout << "sus" << x << ' ' << y << endl;
for (int i = 0; i < 4; i++)
{
int nx = x + dl[i],ny = y + dc[i];
if (nx >= 1 and nx <= r and ny >= 1 and ny <= c and d[nx][ny] == inf and a[nx][ny] == '.')
{
d[nx][ny] = d[x][y];
//s[nx].erase(ny);
//ss[ny].erase(nx);
updates(nx,ny);
updatess(ny,nx);
cells[cs++] = {nx,ny};
dfs(nx,ny);
}
}
}
int dgl;
void orizontala(int x,int y1,int y2)
{
//cout << "h" << x << ' ' << y1 << ' ' << y2 << endl;
#pragma GCC ivdep
while (true)
{
/*auto it = s[x].lower_bound(y1);
if (it == s[x].end() or *it > y2)
return;
d[x][*it] = dgl;
new_cells.push_back({x,*it});
s[x].erase(*it);
ss[*it].erase(x);*/
int it = s_findnext(x,y1);
if (it == -1 or it > y2)
return;
d[x][it] = dgl;
new_cells[ncs++] = {x,it};
updates(x,it);
updatess(it,x);
}
}
void verticala(int y,int x1,int x2)
{
//cout << "v" << y << ' ' << x1 << ' ' << x2 << endl;
#pragma GCC ivdep
while (true)
{
/*auto it = ss[y].lower_bound(x1);
if (it == ss[y].end() or *it > x2)
return;
d[*it][y] = dgl;
new_cells.push_back({*it,y});
ss[y].erase(*it);
s[*it].erase(y);*/
int it = ss_findnext(y,x1);
if (it == -1 or it > x2)
return;
d[it][y] = dgl;
new_cells[ncs++] = {it,y};
updatess(y,it);
updates(it,y);
}
}
vector<int> dll;
vector<int> dcc;
void baga(int x,int y)
{
luat[x][y] = true;
//cout << "bagat" << ' ' << x << ' ' << y << endl;
dgl = d[x][y] + 1;
if (abs(x - xf) <= n and abs(y - yf) <= n and abs(x - xf) + abs(y - yf) < 2 * n)
{
d[xf][yf] = min(d[xf][yf],1 + d[x][y]);
return;
}
int x1 = x - n,x2 = x + n,y1 = y - n,y2 = y + n;
///teoretic pot tot patratul (x1,y1,x2,y2) fara colturi, daca ies din matrice ayaye
///pot sa iau intersectia dreptunghiurilor (x1,y1,x2,y2) cu matricea si daca e tai colturile
x1 = max(x1,1);
x2 = min(x2,r);
y1 = max(y1,1);
y2 = min(y2,c);
//cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
bool sus = false,jos = false,dreapta = false,stanga = false;
if (x != 1 and luat[x - 1][y])
sus = true;
if (x != r and luat[x + 1][y])
jos = true;
if (y != 1 and luat[x][y - 1])
stanga = true;
if (y != c and luat[x][y + 1])
dreapta = true;
if (!stanga and !dreapta)
{
if (x1 != x - n)
{
if (!sus)
orizontala(x1,y1,y2);
}
else
{
int y1r = y1,y2r = y2;
if (y1 == y - n)
y1r++;
if (y2 == y + n)
y2r--;
orizontala(x1,y1r,y2r);
}
if (x2 != x + n)
{
if (!jos)
orizontala(x2,y1,y2);
}
else
{
int y1r = y1,y2r = y2;
if (y1 == y - n)
y1r++;
if (y2 == y + n)
y2r--;
orizontala(x2,y1r,y2r);
}
}
if (!sus and !jos)
{
if (y1 != y - n)
{
if (!stanga)
verticala(y1,x1,x2);
}
else
{
int x1r = x1,x2r = x2;
if (x1 == x - n)
x1r++;
if (x2 == x + n)
x2r--;
verticala(y1,x1r,x2r);
}
if (y2 != y + n)
{
if (!dreapta)
verticala(y2,x1,x2);
}
else
{
int x1r = x1,x2r = x2;
if (x1 == x - n)
x1r++;
if (x2 == x + n)
x2r--;
verticala(y2,x1r,x2r);
}
}
for (int i = 0; i < 8; i++)
{
int nx = x + dll[i],ny = y + dcc[i];
if (nx < 1 or nx > r or ny < 1 or ny > c)
continue;
bool yea = true;
if ((i == 0 or i == 1) and (sus or stanga))
yea = false;
if ((i == 2 or i == 3) and (sus or dreapta))
yea = false;
if ((i == 4 or i == 5) and (jos or dreapta))
yea = false;
if ((i == 6 or i == 7) and (jos or stanga))
yea = false;
if (yea and d[nx][ny] == inf)
{
d[nx][ny] = dgl;
new_cells[ncs++] = {nx,ny};
updates(nx,ny);
updatess(ny,nx);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c >> n >> xs >> ys >> xf >> yf;
a.resize(r + 1);
s.resize(r + 1);
ss.resize(c + 1);
ts.resize(r + 1);
tss.resize(c + 1);
dll = {-(n - 1),-n,-n,-(n - 1),(n - 1),n,n,(n - 1)};
dcc = {-n,-(n - 1),n - 1,n,n,n - 1,-(n - 1),-n};
lgc = __lg(c);
lgr = __lg(r);
for (int i = 1; i <= r; i++)
ts[i] = c;
for (int i = 1; i <= c; i++)
tss[i] = r;
for (int i = 1; i <= r; i++)
s[i].resize(c + 1);
for (int i = 1; i <= c; i++)
ss[i].resize(r + 1);
luat.resize(r + 1);
for (int i = 1; i <= c; i++)
luat[i].resize(c + 1);
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
s[i][j] = (j & -j);
ss[j][i] = (i & -i);
}
}
for (int i = 1; i <= r; i++)
{
a[i].resize(c + 1);
for (int j = 1; j <= c; j++)
cin >> a[i][j];
}
d.resize(r + 1);
for (int i = 1; i <= r; i++)
d[i].resize(c + 1);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
d[i][j] = 1e9;
new_cells[ncs++] = {xs,ys};
d[xs][ys] = 0;
updates(xs,ys);
updatess(ys,xs);
while (true)
{
//cout << endl;
//for (auto it : new_cells)
// cout << "nc" << ' ' << it.first << ' ' << it.second << ' ' << d[it.first][it.second] << endl;
//cells = new_cells;
cs = ncs;
for (int i = 0; i < cs; i++)
cells[i] = new_cells[i];
for (int i = 0; i < ncs; i++)
dfs(new_cells[i].first,new_cells[i].second);
if (d[xf][yf] != inf)
break;
ncs = 0;
for (int i = 0; i < cs; i++)
baga(cells[i].first,cells[i].second);
if (d[xf][yf] != inf)
break;
}
cout << d[xf][yf];
return 0;
}
/**
din (i,j) pot merge ori intr-un vecin care e si el alb
as mai putea merge in patratul de latura 2n + 1 centrat in (i,j) fara colturile lui
acum, faza funny e ca nu prea ma intereseaza de mersul inauntrul formei ci doar pe marini, unless este celula de finish in interior
asa ca, ori e celula de finish in interior si zic direct gen "boss, dute in aia", ori pun cu cost + 1 celulele de pe margini
acum, ca sa gasesc celulele de pe margini nevizitate inca, trebuie doar sa vad pe niste bucati de linii / coloane care mai sunt alive
asta pot cu un set, dar cu constanta aia :skull: mai bine nu, deci bag aib si cb pe aib
Acum, cum imi fac dfs-ul ca sa nu iasa nimic dubios
In etape, cat timp n-am ajuns la finish, mai intai imi iau celulele cu care n-am trecut prin faza 1 si le dau fill cat au in jur 0
Iar in faza 2 iau celulele care n-au trecut prin faza asta si le fac kinda patratul, iau alea de pe margini etc
**/
///hocus pocus ca sa treaca
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
464 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
548 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
464 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
464 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
464 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
