# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1046888 | lozergam | Maze (JOI23_ho_t3) | C++17 | 0 ms | 348 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.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll int
#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>
#define insert emplace
vector<vector<bool>> a, vis;
arr(2) s, e;
ll n, m, k;
ll ans;
vector<arr(2)> v, g;
inline void bfs()
{
while(!v.empty())
{
auto x = v.back();
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);
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;
}
v.pb(s);
vis[s[0]][s[1]] = 1;
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, 1);
r[1] = min(x[0] + k - 1, n);
c[0] = max(x[1] - k + 1, 1);
c[1] = min(x[1] + k - 1, m);
if(e[0] >= r[0] and e[0] <= r[1] and e[1] >= c[0] and e[1] <= c[1])
{
cout << ans + 1 << endl;
return 0;
}
For(i, 2)
For(j, 2)
if(!vis[r[i]][c[j]])
{
v.pb({r[i], c[j]});
vis[r[i]][c[j]] = 1;
}
For(i, 20)
{
ll t = rand() % (c[1] - c[0]) + c[0];
For(j, 2)
if(!vis[r[j]][t])
{
v.pb({r[j], t});
vis[r[j]][t] = 1;
}
}
For(i, 20)
{
ll t = rand() % (r[1] - r[0]) + r[0];
For(j, 2)
if(!vis[t][c[j]])
{
v.pb({t, c[j]});
vis[t][c[j]] = 1;
}
}
}
g.clear();
ans++;
}
cout << ans << endl;
}
Compilation message (stderr)
# | 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... |