結果
問題 | No.608 God's Maze |
ユーザー |
![]() |
提出日時 | 2017-12-08 10:06:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 2,498 ms |
コンパイル使用メモリ | 211,444 KB |
最終ジャッジ日時 | 2025-01-05 04:56:46 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1 << 30;int solve(string S, int N){int right = -1, ret = 0;for(int i = N; i >= 0; i--) {if(S[i] == '#') right = i;}if(right == -1) return (INF);for(int i = N - 1; i >= right; i--) {S[i] = ".#"[S[i] == '.'];++ret;}S += ".";int rest = count(begin(S), end(S), '#');while(rest > 0) {++right;assert(right < S.size());++ret;S[right] = ".#"[S[right] == '.'];if(S[right] == '.') rest--;else rest++;if(S[right - 1] == '#') {--right;++ret;S[right] = ".#"[S[right] == '.'];if(S[right] == '.') rest--;else rest++;}}return (ret);}int main(){int N;string S, T;cin >> N;cin >> S;if(S.size() >= 30) {T = S;reverse(begin(T), end(T));cout << min(solve(S, N - 1), solve(T, (int) S.size() - N)) << endl;return (0);}--N;queue< pair< int, string > > que;map< string, int > min_cost[S.size()];min_cost[N][S] = 0;que.emplace(N, S);while(!que.empty()) {int idx;string s;tie(idx, s) = que.front();que.pop();if(count(begin(s), end(s), '#') == 0) {cout << min_cost[idx][s] << endl;break;}for(int i = -1; i <= 1; i++) {if(i == 0) continue;if(idx + i < 0 || idx + i >= S.size()) continue;string p = s;p[idx + i] = ".#"[p[idx + i] == '.'];if(min_cost[idx + i].count(p)) continue;min_cost[idx + i][p] = min_cost[idx][s] + 1;que.emplace(idx + i, p);}}}