#1158416 (C++23) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: zawakasu
• 提出日時: 2026-04-17 23:23:18
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 32 ms / 2,000 ms
• コード長: 4,245 bytes
• コンパイル時間: 1,701 ms
• コンパイル使用メモリ: 216,316 KB
• 実行使用メモリ: 8,648 KB
• 最終ジャッジ日時: 2026-04-17 23:23:50
• 合計ジャッジ時間: 9,395 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 85

ソースコード

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <random>
// #include "Src/Number/IntegerDivision.hpp"
// #include "Src/Utility/BinarySearch.hpp"
// #include "Src/Sequence/CompressedSequence.hpp"
// #include "Src/Sequence/RunLengthEncoding.hpp"
// #include "Src/Algebra/Group/AdditiveGroup.hpp"
// #include "Src/DataStructure/FenwickTree/FenwickTree.hpp"
// #include "Src/DataStructure/SegmentTree/SegmentTree.hpp"
// #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
// #include "Src/DataStructure/Heap/BinaryHeap.hpp"
namespace zawa {}
using namespace zawa;
// #include "atcoder/modint"
// using mint = atcoder::modint998244353;
// #include <array>
// #include <bit>
// #include <bitset>
// #include <climits>
// #include <cmath>
// #include <set>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <optional>
// #include <queue>
// #include <stack>
// #include <deque>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0 ; i < ssize(v) ; i++)
        os << v[i] << (i + 1 == ssize(v) ? "" : " ");
    return os;
}
/*
 * 1列目と2列目、H-1行目とH行目の間に操作をするとH+W回で移動できる
 * あきらかにH+W-2回が下界なので、H+W-2かH+W-1かを判定できれば良い
 * H+W-2は右下移動だけで到達可能かを判定すれば良くて、簡単。
 * H+W-1は？
 * - 迂回する経路はありえなくて、一回操作をすると右下移動だけでできる
 * - (H,W)から左上移動で到達できるマスも計算すると判定ができる
 */
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
#if !defined DEBUG
    int H,W;
    cin >> H >> W;
    vector<string> C(H,string(W,'.'));
    for (int i = 0 ; i < H ; i++)
        cin >> C[i];
    const auto dp = [&]() {
        vector res(H,vector<bool>(W));
        res[0][0] = 1;
        for (int i = 0 ; i < H ; i++)
            for (int j = 0 ; j < W ; j++)
                if (res[i][j]) {
                    if (i + 1 < H and C[i+1][j] != '#')
                        res[i+1][j] = 1;
                    if (j + 1 < W and C[i][j+1] != '#')
                        res[i][j+1] = 1;
                }
        return res;
    }();
    const auto ep = [&]() {
        vector res(H,vector<bool>(W));
        res[H-1][W-1] = 1;
        for (int i = H - 1 ; i >= 0 ; i--)
            for (int j = W - 1 ; j >= 0 ; j--)
                if (res[i][j]) {
                    if (i >= 1 and C[i-1][j] != '#')
                        res[i-1][j] = 1;
                    if (j >= 1 and C[i][j-1] != '#')
                        res[i][j-1] = 1;
                }
        return res;
    }();
    if (dp[H-1][W-1]) {
        cout << H + W - 2 << '\n';
        return 0;
    }
    vector<int> row1(H,W),row2(H,-1);
    vector<int> col1(W,H),col2(W,-1);
    for (int i = 0 ; i < H ; i++)
        for (int j = 0 ; j < W ; j++) {
            if (dp[i][j]) {
                row1[i] = min(row1[i],j);
                col1[j] = min(col1[j],i);
            }
            if (ep[i][j]) {
                row2[i] = max(row2[i],j);
                col2[j] = max(col2[j],i);
            }
        }
    bool can = 0;
    for (int i = 0 ; i + 1 < H ; i++)
        can |= row1[i] <= row2[i+1];
    for (int i = 0 ; i + 1 < W ; i++)
        can |= col1[i] <= col2[i+1];
    cout << (can ? H + W - 1 : H + W) << '\n';
#else
    mt19937_64 mt{random_device{}()};
    for (int testcase = 0 ; ; ) {
        cerr << "----------" << ++testcase << "----------" << endl;
        
        auto a = solve(), b = naive();
        if (a != b) {
            // print testcase

            cerr << "you: " << a << endl;
            cout << "correct: " << b << endl;
            exit(0);
        }
    }
#endif
}