Submission #394816

#TimeUsernameProblemLanguageResultExecution timeMemory
394816SaraPortals (BOI14_portals)C++14
100 / 100
933 ms184772 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define ll long long #define F first #define S second #define pb push_back #define md ((b + e) >> 1) const ll N = 1000 + 3; const ll LOG = 17; const ll INF = 1e9 + 5; const ll MOD = 1e9 + 7; short n, m; char mat[N][N]; pair <short, short> L[N][N], R[N][N]; pair <short, short> U[N][N], D[N][N]; pair <int, int> dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; vector <int> g[N * N]; vector < pair < int, int > > adj[N * N]; pair <short, short> st, en; bool A[N][N]; int id[N][N], ID = 1; inline bool in_sq(short x, short y){ return ((0 <= x) && (x <= n + 1) && (0 <= y) && (y <= m + 1)); } inline bool valid(short x, short y){ return (in_sq(x, y) && !A[x][y]); } inline void add_edges(){ for (short i = 0; i <= n + 1; i ++){ for (short j = 0; j <= m + 1; j ++){ for (short d = 0; d < 4; d ++){ short x = i + dir[d].F; short y = j + dir[d].S; if (valid(x, y)){ g[id[i][j]].pb(id[x][y]); } } } } return; } int dis[N * N]; queue <int> q; inline void bfs(){ for (short i = 0; i <= n + 1; i ++){ for (short j = 0; j <= m + 1; j ++){ dis[id[i][j]] = INF; } } for (short i = 0; i <= n + 1; i ++){ for (short j = 0; j <= m + 1; j ++){ if (A[i][j]){ dis[id[i][j]] = 0; q.push(id[i][j]); } } } while (q.size()){ int v = q.front(); q.pop(); for (auto u : g[v]){ if (dis[v] + 1 < dis[u]){ dis[u] = dis[v] + 1; q.push(u); } } } return; } inline void pre(){ for (short i = 0; i <= n + 1; i ++){ for (short j = 0; j <= m + 1; j ++){ if (A[i][j]){ L[i][j] = {i, j}; U[i][j] = {i, j}; } else { L[i][j] = L[i][j - 1]; U[i][j] = U[i - 1][j]; } } } for (short i = n + 1; i >= 0; i --){ for (short j = m + 1; j >= 0; j --){ if (A[i][j]){ R[i][j] = {i, j}; D[i][j] = {i, j}; } else { R[i][j] = R[i][j + 1]; D[i][j] = D[i + 1][j]; } } } return; } inline void add_edges2(){ for (short i = 0; i <= n + 1; i ++){ for (short j = 0; j <= m + 1; j ++){ if (!valid(i, j)) continue; if (valid(i + 1, j)){ short x = D[i + 1][j].F - 1; short y = D[i + 1][j].S; if (!valid(x, y)) continue; adj[id[i][j]].pb({id[x][y], dis[id[i][j]]}); } if (valid(i, j + 1)){ short x = R[i][j + 1].F; short y = R[i][j + 1].S - 1; if (!valid(x, y)) continue; adj[id[i][j]].pb({id[x][y], dis[id[i][j]]}); } if (valid(i - 1, j)){ short x = U[i - 1][j].F + 1; short y = U[i - 1][j].S; if (!valid(x, y)) continue; adj[id[i][j]].pb({id[x][y], dis[id[i][j]]}); } if (valid(i, j - 1)){ short x = L[i][j - 1].F; short y = L[i][j - 1].S + 1; if (!valid(x, y)) continue; adj[id[i][j]].pb({id[x][y], dis[id[i][j]]}); } for (short d = 0; d < 4; d ++){ short x = i + dir[d].F; short y = j + dir[d].S; if (valid(x, y)){ adj[id[i][j]].pb({id[x][y], 1}); } } } } return; } bool mark[N * N]; priority_queue < pair < ll, int > > pq; inline void dij(){ for (int i = 0; i <= n + 1; i ++){ for (int j = 0; j <= m + 1; j ++){ dis[id[i][j]] = INF; } } pq.push({0, id[st.F][st.S]}); dis[id[st.F][st.S]] = 0; while (pq.size()){ auto v = pq.top().S; pq.pop(); if (mark[v]) continue; mark[v] = 1; if (v == id[en.F][en.S]) break; for (auto it : adj[v]){ ll w = it.S; auto u = it.F; if (dis[v] + w < dis[u]){ dis[u] = dis[v] + w; pq.push({-dis[u], u}); } } } cout << dis[id[en.F][en.S]] << '\n'; return; } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i ++){ for (int j = 1; j <= m; j ++){ cin >> mat[i][j]; if (mat[i][j] == 'S'){ st = {i, j}; mat[i][j] = '.'; } if (mat[i][j] == 'C'){ en = {i, j}; mat[i][j] = '.'; } A[i][j] = (mat[i][j] == '#'); } } for (int i = 0; i <= n + 1; i ++){ A[i][0] = A[i][m + 1] = 1; } for (int j = 0; j <= m + 1; j ++){ A[0][j] = A[n + 1][j] = 1; } for (int i = 0; i <= n +1 ; i ++){ for (int j = 0; j <= m + 1; j ++){ id[i][j] = ID; ID ++; } } add_edges(); bfs(); pre(); add_edges2(); dij(); return 0; }
#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...