結果
問題 | No.157 2つの空洞 |
ユーザー | rogi52 |
提出日時 | 2022-09-29 21:33:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,036 bytes |
コンパイル時間 | 2,054 ms |
コンパイル使用メモリ | 215,380 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-02 02:09:02 |
合計ジャッジ時間 | 2,702 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 1 ms
6,944 KB |
testcase_13 | AC | 1 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 1 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; // g <- pair < v , cost > template < class T > vector< T > bfs(vector<vector<pair<int, T>>> &graph, int s) { T INF = numeric_limits< T >::max(); vector<T> dist(graph.size(), INF); queue<pair<T,int>> q; q.push({dist[s] = T(0), s}); while(!q.empty()){ auto [uc, ui] = q.front(); q.pop(); if(uc != dist[ui]) continue; for(auto [vi, vc] : graph[ui]) if(dist[vi] > uc + vc) q.push({dist[vi] = uc + vc, vi}); } return dist; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int W,H; cin >> W >> H; vector<string> C(H); rep(i,H) cin >> C[i]; vector<pair<int,int>> S, T; int di[] = {0, 1, 0, -1}; int dj[] = {1, 0, -1, 0}; auto f = [&](vector<pair<int,int>> &V, char X) { rep(i,H)rep(j,W) if(C[i][j] == '.') { queue<pair<int,int>> q; q.push({i, j}); V.push_back({i, j}); C[i][j] = X; while(!q.empty()) { auto [ci, cj] = q.front(); q.pop(); rep(d,4) { int ni = ci + di[d], nj = cj + dj[d]; if(0 <= ni && ni < H && 0 <= nj && nj < W && C[ni][nj] == '.') { C[ni][nj] = X; V.push_back({ni, nj}); q.push({ni, nj}); } } } return; } }; f(S, 'S'); f(T, 'T'); vector<vector<pair<int,int>>> G(H * W + 2); auto h = [&](int i, int j){ return i * W + j; }; rep(i,H)rep(j,W)rep(d,4) { int ni = i + di[d], nj = j + dj[d]; if(0 <= ni && ni < H && 0 <= nj && nj < W) { G[h(i, j)].push_back({h(ni, nj), 1}); } } int s = H * W, t = s + 1; for(auto [i, j] : S) G[s].push_back({h(i, j), 0}); for(auto [i, j] : T) G[h(i, j)].push_back({t, 0}); cout << bfs(G, s)[t] - 1 << endl; }