Submission #769533

#TimeUsernameProblemLanguageResultExecution timeMemory
769533danikoynovMaze (JOI23_ho_t3)C++14
0 / 100
418 ms781568 KiB
#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]; 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 (i % (2 * h - 1) != 0) 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 (i % (2 * h - 1) != 0) 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}); } } } } int is_div[maxn]; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...