結果
問題 | No.608 God's Maze |
ユーザー |
|
提出日時 | 2017-12-08 01:50:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,087 bytes |
コンパイル時間 | 827 ms |
コンパイル使用メモリ | 72,136 KB |
最終ジャッジ日時 | 2025-01-05 04:54:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
#include <cstdio>#include <iostream>#include <algorithm>int solve(int p, std::string s) {int l = 0, n = s.size(), ret = 0;while (l < p && s[l] == '.') ++l;if (l != p) {for (int i = p - 1; i >= l; --i) {s[i] = '#' + '.' - s[i];++ret;}}while (n > 1 && s[n - 1] == '.') --n;for (int r; ;) {for (r = l; r < n && s[l] == s[r]; ++r);if (r == n) {if (s[l] == '#') {if (r - l == 1) ret += 3;else ret += 2 + (r - l - 2) * 3;}break;} else {if (s[l] == '#') {ret += (r - l) * 3;l = r;} else {if (r - l == 2) ret += 1, s[l + 1] = '#', ++l;else if ((r - l) % 2 == 0) ret += 2 * (r - l), l = r;else {ret += 1 + (r - l - 1) * 2;s[r] = '.';l = r;}}}}return ret;}int main() {int n;std::string s;std::cin >> n >> s;int ret = solve(n - 1, s);std::reverse(s.begin(), s.end());ret = std::min(ret, solve(s.size() - n, s));std::cout << ret << std::endl;return 0;}