| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 769530 |
2023-06-29T18:16:12 Z |
danikoynov |
Maze (JOI23_ho_t3) |
C++14 |
|
473 ms |
799676 KB |
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 6e6 + 10, block = sqrt(maxn) + 10;
struct cell
{
int x, y;
cell(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
cell add(const cell &r) const
{
cell d;
d.x = x + r.x;
d.y = y + r.y;
return d;
}
};
cell neib[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int n, m, h;
vector < int > a[block], tr[block], tl[block];
vector < int > tu[block], td[block];
vector < int > ver_idx[block];
vector < pair < int, bool > > adj[3 * maxn];
int stx, sty, enx, eny;
int nxt;
int visit[3 * maxn], dist[3 * maxn];
bool is_div[maxn];
void add_edges_row(int row, int i, int j, int ver)
{
if (j - i + 1 == 2 * h - 1)
{
adj[ver].push_back({tr[row][i], 1});
adj[ver].push_back({tl[row][j], 1});
}
else
{
if (i == 1)
adj[ver].push_back({tl[row][j], 1});
else
{
int to = i;
if (!is_div[i])
to = 2 * h - 1 - i % (2 * h - 1) + i;
if (to >= j)
adj[ver].push_back({tr[row][i], 1});
else
{
adj[ver].push_back({tr[row][i], 1});
adj[ver].push_back({tl[row][j], 1});
}
}
}
}
void add_edges_col(int col, int i, int j, int ver)
{
if (j - i + 1 == 2 * h - 1)
{
adj[ver].push_back({td[i][col], 1});
adj[ver].push_back({tu[j][col], 1});
}
else
{
if (i == 1)
adj[ver].push_back({tu[j][col], 1});
else
{
int to = i;
if (!is_div[i])
to = 2 * h - 1 - i % (2 * h - 1) + i;
if (to >= j)
adj[ver].push_back({td[i][col], 1});
else
{
adj[ver].push_back({td[i][col], 1});
adj[ver].push_back({tu[j][col], 1});
}
}
}
}
void solve()
{
cin >> n >> m >> h;
cin >> stx >> sty;
cin >> enx >> eny;
for (int i = 1; i <= max(n, m); i ++)
{
if (i % (2 * h - 1) == 0)
is_div[i] = 1;
}
for (int i = 1; i <= n; i ++)
{
a[i].resize(m + 2);
tl[i].resize(m + 2);
tr[i].resize(m + 2);
td[i].resize(m + 2);
tu[i].resize(m + 2);
ver_idx[i].resize(m + 2);
string s;
cin >> s;
char c;
for (int j = 1; j <= m; j ++)
{
c = s[j - 1];
if (c == '.')
a[i][j] = 0;
else
a[i][j] = 1;
}
}
int cnt = 0;
nxt = n * m;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
ver_idx[i][j] = ++ cnt;
}
}
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
tr[i][j] = ++ nxt;
tl[i][j] = ++ nxt;
}
for (int j = 1; j <= m; j ++)
{
if (!is_div[j] && j != m)
adj[tr[i][j]].push_back({tr[i][j + 1], 0});
adj[tr[i][j]].push_back({ver_idx[i][j], 0});
if (!is_div[j - 1])
adj[tl[i][j]].push_back({tl[i][j - 1], 0});
adj[tl[i][j]].push_back({ver_idx[i][j], 0});
}
}
for (int j = 1; j <= m; j ++)
{
for (int i = 1; i <= n; i ++)
{
tu[i][j] = ++ nxt;
td[i][j] = ++ nxt;
}
for (int i = 1; i <= n; i ++)
{
if (!is_div[i] && i != n)
adj[td[i][j]].push_back({td[i + 1][j], 0});
adj[td[i][j]].push_back({ver_idx[i][j], 0});
if (!is_div[i - 1])
adj[tu[i][j]].push_back({tu[i - 1][j], 0});
adj[tu[i][j]].push_back({ver_idx[i][j], 0});
}
}
///exit(0);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
cell cur(i, j);
for (int d = 0; d < 4; d ++)
{
cell nb = cur.add(neib[d]);
if (nb.x > 0 && nb.x <= n && nb.y > 0 && nb.y <= m)
if (a[nb.x][nb.y] == 0)
{
adj[ver_idx[cur.x][cur.y]].push_back({ver_idx[nb.x][nb.y], 0});
}
}
int st_row = max(1, i - h), en_row = min(n, i + h);
int st_col = max(1, j - h), en_col = min(m, j + h);
int fs_row = st_row, ds_row = en_row;
if (fs_row == i - h)
fs_row ++;
if (ds_row == i + h)
ds_row --;
bool f1 = false, f2 = false;
if (st_row == i - h)
{
if (st_col == j - h)
st_col ++, f1 = true;
if (en_col == j + h)
en_col --, f2 = true;
}
add_edges_row(st_row, st_col, en_col, ver_idx[i][j]);
if (st_row == i - h)
{
if (f1)
st_col --;
if (f2)
en_col ++;
}
/// down row
f1 = f2 = false;
if (en_row == i + h)
{
if (st_col == j - h)
st_col ++, f1 = true;
if (en_col == j + h)
en_col --, f2 = true;
}
////cout << i << " " << j << " range " << st_col << " " << en_col << endl;
///add_edges(row_root[en_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
add_edges_row(en_row, st_col, en_col, ver_idx[i][j]);
if (en_row == i + h)
{
if (f1)
st_col --;
if (f2)
en_col ++;
}
/// left col
f1 = f2 = false;
if (st_col == j - h)
{
if (st_row == i - h)
st_row ++, f1 = true;
if (en_row == i + h)
en_row --, f2 = true;
}
///add_edges(col_root[st_col], 1, n, st_row, en_row, ver_idx[i][j], 1);
add_edges_col(st_col, st_row, en_row, ver_idx[i][j]);
if (st_col == j - h)
{
if (f1)
st_row --;
if (f2)
en_row ++;
}
/// right col
f1 = f2 = false;
if (en_col == j + h)
{
if (st_row == i - h)
st_row ++, f1 = true;
if (en_row == i + h)
en_row --, f2 = true;
}
///cout << i << " " << j << " " << "range " << st_row << " " << en_row << " col " << en_col << endl;
///add_edges(col_root[en_col], 1, n, st_row, en_row, ver_idx[i][j], 1);
add_edges_col(en_col, st_row, en_row, ver_idx[i][j]);
if (en_col == j + h)
{
if (f1)
st_row --;
if (f2)
en_row ++;
}
/**for (int row = st_row; row <= en_row; row ++)
{
if (row == i - h || row == i + h)
{
st_col ++, en_col --;
add_edges(row_root[row], 1, m, st_col, en_col, ver_idx[i][j], 1);
st_col --, en_col ++;
}
else
{
adj[ver_idx[cur.x][cur.y]].push_back({fict[row][cur.y], 1});
}
}*/
}
for (int i = 1; i <= nxt; i ++)
dist[i] = 1e9;
deque < int > dq;
dq.push_back(ver_idx[stx][sty]);
dist[ver_idx[stx][sty]] = 0;
while(!dq.empty())
{
int cur = dq.front();
dq.pop_front();
if (cur == ver_idx[enx][eny])
{
cout << dist[cur] << endl;
return;
}
for (pair < int, int > nb : adj[cur])
{
int u = nb.first;
int w = nb.second;
if (dist[u] > dist[cur] + w)
{
dist[u] = dist[cur] + w;
if (w == 0)
dq.push_front(u);
else
dq.push_back(u);
}
}
}
/**for (int i = 1; i <= n; i ++, cout << endl)
for (int j = 1; j <= m; j ++)
cout << dist[ver_idx[i][j]] << " ";*/
int ans = dist[ver_idx[enx][eny]];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (abs(i - enx) <= h && abs(j - eny) <= h)
{
if (abs(i - enx) + abs(j - eny) != 2 * h)
{
ans = min(ans, dist[ver_idx[i][j]] + 1);
}
}
}
cout << ans << endl;
}
int main()
{
///freopen("test.txt", "r", stdin);
speed();
solve();
return 0;
}
/**
3 3 2
1 1
3 3
.#.
##.
...
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
466 ms |
799616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
473 ms |
799676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
453 ms |
799656 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
473 ms |
799676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
473 ms |
799676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
466 ms |
799616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
466 ms |
799616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
466 ms |
799616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
