제출 #675124

#제출 시각아이디문제언어결과실행 시간메모리
675124tamthegod포탈들 (BOI14_portals)C++14
31 / 100
2 ms596 KiB
// Make the best become better // No room for laziness #include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e2 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int r, c; string a[maxN]; pair<int, int> s, t; int d[maxN][maxN]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; vector<int> row[maxN], col[maxN]; struct TPQRect { int x, y, dlab; bool operator < (const TPQRect& other) const { return other.dlab < dlab; } bool Valid() const { return d[x][y] == dlab; } }; void ReadInput() { cin >> r >> c; for(int i=1; i<=r; i++) { row[i].pb(0); row[i].pb(c + 1); } for(int i=1; i<=c; i++) { col[i].pb(0); col[i].pb(r + 1); } for(int i=1; i<=r; i++) { cin >> a[i]; a[i] = ' ' + a[i]; for(int j=1; j<=c; j++) { if(a[i][j] == 'S') s = {i, j}; if(a[i][j] == 'C') t = {i, j}; if(a[i][j] == '#') { row[i].pb(j); col[j].pb(i); } } } for(int i=1; i<=r; i++) sort(row[i].begin(), row[i].end()); for(int i=1; i<=c; i++) sort(col[i].begin(), col[i].end()); } void Dijkstra() { priority_queue<TPQRect> pq; memset(d, 3, sizeof d); d[s.fi][s.se] = 0; pq.push({s.fi, s.se, 0}); while(!pq.empty()) { TPQRect R = pq.top(); pq.pop(); if(!R.Valid()) continue; int x = R.x, y = R.y; for(int i=0; i<4; i++) { int u = x + dx[i], v = y + dy[i]; if(u < 1 || u > r || v < 1 || v > c || a[u][v] == '#') continue; if(d[u][v] > d[x][y] + 1) { d[u][v] = d[x][y] + 1; pq.push({u, v, d[u][v]}); } } vector<pair<int, int>> vc; int id = lower_bound(row[x].begin(), row[x].end(), y) - row[x].begin(); vc.pb({x, row[x][id] - 1}); id--; vc.pb({x, row[x][id] + 1}); id = lower_bound(col[y].begin(), col[y].end(), x) - col[y].begin(); vc.pb({col[y][id] - 1, y}); id--; vc.pb({col[y][id] + 1, y}); for(int i=0; i<4; i++) for(int j=0; j<4; j++) { int w = abs(x - vc[j].fi) + abs(y - vc[j].se) + 1; if(d[vc[i].fi][vc[i].se] > d[x][y] + w) { d[vc[i].fi][vc[i].se] = d[x][y] + w; pq.push({vc[i].fi, vc[i].se, d[vc[i].fi][vc[i].se]}); } } } } void Solve() { Dijkstra(); cout << d[t.fi][t.se]; } int32_t main() { //freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
#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...