제출 #250607

#제출 시각아이디문제언어결과실행 시간메모리
250607opukittpceno_hhr포탈들 (BOI14_portals)C++17
0 / 100
1 ms384 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <chrono> #include <random> #include <functional> using namespace std; const int N = 10; const int INF = 1e9 + 239; const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; int n, m; int a[N][N]; int d[N * N]; vector<pair<int, int>> g[N * N]; int ok(int i, int j) { return 0 <= i && i < n && 0 <= j && j < m && !a[i][j]; } int get(int i, int j) { return i * m + j; } void dij(int st) { fill(d, d + n * m, INF); d[st] = 0; set<pair<int, int>> s; s.insert({d[st], st}); while (!s.empty()) { int v = s.begin()->second; s.erase(s.begin()); for (auto [u, w] : g[v]) { if (d[u] > d[v] + w) { s.erase({d[u], u}); d[u] = d[v] + w; s.insert({d[u], u}); } } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { a[i][j] = 1; } } int si = -1; int sj = -1; int ci = -1; int cj = -1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char c; cin >> c; a[i][j] = (c == '#'); if (c == 'S') { si = i; sj = j; } if (c == 'C') { ci = i; cj = j; } } } n++; m++; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j]) continue; int cu = -1; int cd = -1; int cl = -1; int cr = -1; { cu = 0; while (!a[i - (cu + 1)][j]) { cu++; } } { cd = 0; while (!a[i + (cd + 1)][j]) { cd++; } } { cl = 0; while (!a[i][j - (cl + 1)]) { cl++; } } { cr = 0; while (!a[i][j + (cr + 1)]) { cr++; } } int mn = min({cu, cd, cl, cr}); g[get(i, j)].push_back({get(i - cu, j), 1 + mn}); g[get(i, j)].push_back({get(i + cd, j), 1 + mn}); g[get(i, j)].push_back({get(i, j - cl), 1 + mn}); g[get(i, j)].push_back({get(i, j + cr), 1 + mn}); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int k = 0; k < 4; k++) { if (ok(i, j) && ok(i + dx[k], j + dy[k])) { g[get(i, j)].push_back({get(i + dx[k], j + dy[k]), 1}); } } } } dij(get(si, sj)); cout << d[get(ci, cj)] << endl; }
#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...