| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1046188 | lozergam | Maze (JOI23_ho_t3) | C++17 | 0 ms | 0 KiB |
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 ll long long#define pb push_back#define For(i, n) for(int (i) = 0; (i) < (n); (i)++)#define debug(x) cout << #x << " : " << x << endl << flush#define endl '\n'#define sz(x) (ll)x.size()#define arr(x) array<ll, x>const ll INF = 1e18;vector<vector<bool>> a, vis;arr(2) s, e;ll n, m, k;ll ans;vector<arr(2)> v, g;vector<set<ll>> row, col;ll cnt;void bfs(){ cnt++; // debug(cnt); while(!v.empty()) { auto x = v.back(); // debug(x[0]); // debug(x[1]); v.pop_back(); if(x[0] != 1 and !vis[x[0] - 1][x[1]]) { if(a[x[0] - 1][x[1]]) g.pb({x[0] - 1, x[1]}); else { vis[x[0] - 1][x[1]] = 1; v.pb({x[0] - 1, x[1]}); } } if(x[0] != n and !vis[x[0] + 1][x[1]]) { if(a[x[0] + 1][x[1]]) g.pb({x[0] + 1, x[1]}); else { v.pb({x[0] + 1, x[1]}); vis[x[0] + 1][x[1]] = 1; } } if(x[1] != 1 and !vis[x[0]][x[1] - 1]) { if(a[x[0]][x[1] - 1]) g.pb({x[0], x[1] - 1}); else { v.pb({x[0], x[1] - 1}); vis[x[0]][x[1] - 1] = 1; } } if(x[1] != m and !vis[x[0]][x[1] + 1]) { if(a[x[0]][x[1] + 1]) g.pb({x[0], x[1] + 1}); else { v.pb({x[0], x[1] + 1}); vis[x[0]][x[1] + 1] = 1; } } }}int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m >> k;
a.resize(n + 1);
vis.resize(n + 1);
row.resize(n + 1);
col.resize(m + 1);
For(i, n + 1)
{
a[i].resize(m + 1, 0);
vis[i].resize(m + 1, 0);
For(j, m + 1)
vis[i][j] = 0;
}
cin >> s[0] >> s[1];
cin >> e[0] >> e[1];
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
{
char c;
cin >> c;
if(c == '.')
a[i][j] = 0;
else
a[i][j] = 1;
row[i].insert(j);
col[j].insert(i);
}
For(i, n + 1)
row[i].insert(INF);
For(i, m + 1)
col[i].insert(INF);
v.pb(s);
vis[s[0]][s[1]] = 1;
// 2 4 2
// 1 1
// 2 4
// .###
// ###.
while(1)
{
bfs();
if(vis[e[0]][e[1]])
break;
for(auto x : g)
{
arr(2) r, c;
r[0] = max(x[0] - k + 1, 1ll);
r[1] = min(x[0] + k - 1, n);
c[0] = max(x[1] - k + 1, 1ll);
c[1] = min(x[1] + k - 1, m);
// debug(x[0]);
// debug(x[1]);
// debug(r[0]);
// debug(r[1]);
// debug(c[0]);
// debug(c[1]);
// debug(endl);
auto it = row[r[0]].lower_bound(c[0]);
while((*it) <= c[1])
{
if(!vis[r[0]][(*it)])
{
vis[r[0]][(*it)] = 1;
v.pb({r[0], (*it)});
}
row[r[0]].erase(it);
it = row[r[0]].lower_bound(c[0]);
}
it = row[r[1]].lower_bound(c[0]);
while((*it) <= c[1])
{
if(!vis[r[1]][(*it)])
{
vis[r[1]][(*it)] = 1;
v.pb({r[1], (*it)});
}
row[r[1]].erase(it);
it = row[r[1]].lower_bound(c[0]);
}
it = col[c[0]].lower_bound(r[0]);
while((*it) <= r[1])
{
if(!vis[(*it)][c[0]])
{
vis[(*it)][c[0]] = 1;
v.pb({(*it), c[0]});
}
col[c[0]].erase(it);
it = col[c[0]].lower_bound(r[0]);
}
it = col[c[1]].lower_bound(r[0]);
while((*it) <= r[1])
{
if(!vis[(*it)][c[1]])
{
vis[(*it)][c[1]] = 1;
v.pb({(*it), c[1]});
}
col[c[1]].erase(it);
it = col[c[1]].lower_bound(r[0]);
}
v.pb(x);
vis[x[0]][x[1]] = 1;
if(e[0] >= r[0] and e[0] <= r[1] and e[1] >= c[0] and e[1] <= c[1])
vis[e[0]][e[1]] = 1;
}
g.clear();
ans++;
}
cout << ans << endl;
}