제출 #394848

#제출 시각아이디문제언어결과실행 시간메모리
394848Sara포탈들 (BOI14_portals)C++14
0 / 100
15 ms24012 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; int n, m; string s; bool A[N][N]; int id[N][N], ind = 1; vector < pair <int, int> > g[N * N]; pair <int, int> st, en; int le[N][N], ri[N][N]; int up[N][N], dw[N][N]; inline void pre(){ for (int i = 0; i <= n + 1; i ++){ for (int j = 0; j <= m + 1; j ++){ if (A[i][j]){ le[i][j] = j; up[i][j] = i; } else { le[i][j] = le[i][j - 1]; up[i][j] = up[i - 1][j]; } } } for (int i = n + 1; i >= 0; i --){ for (int j = m + 1; j >= 0; j --){ if (A[i][j]){ ri[i][j] = j; dw[i][j] = i; } else { ri[i][j] = ri[i][j + 1]; dw[i][j] = dw[i + 1][j]; } } } return; } int dis[N * N]; inline void add_edges(){ for (int i = 1; i <= n; i ++){ for (int j = 1; j <= m; j ++){ if (A[i][j]) continue; int w = min({j - le[i][j], ri[i][j] - j, i - up[i][j], dw[i][j] - i}); int x, y; x = i, y = le[i][j] + 1; if (!A[x][y]){ g[id[i][j]].pb({id[x][y], w}); } x = i, y = ri[i][j] - 1; if (!A[x][y]){ g[id[i][j]].pb({id[x][y], w}); } x = up[i][j] + 1, y = j; if (!A[x][y]){ g[id[i][j]].pb({id[x][y], w}); } x = dw[i][j] - 1, y = j; if (!A[x][y]){ g[id[i][j]].pb({id[x][y], w}); } if (!A[i][j - 1]){ g[id[i][j]].pb({id[i][j - 1], 1}); } if (!A[i][j + 1]){ g[id[i][j]].pb({id[i][j - 1], 1}); } if (!A[i - 1][j]){ g[id[i][j]].pb({id[i - 1][j], 1}); } if (!A[i + 1][j]){ g[id[i][j]].pb({id[i + 1][j], 1}); } } } return; } bool mark[N * N]; priority_queue < pair <int, 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; } } dis[id[st.F][st.S]] = 0; pq.push({0, id[st.F][st.S]}); while (pq.size()){ int v = pq.top().S; pq.pop(); if (mark[v]) continue; mark[v] = 1; for (auto it : g[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 >> s; s = ' ' + s; if (s[j] == 'S'){ st = {i, j}; } else if (s[j] == 'C'){ en = {i, j}; } A[i][j] = (s[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] = ind; ind ++; } } pre(); add_edges(); 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...