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

• 問題: No.3504 Insert Maze
• ユーザー: amano-amane
• 提出日時: 2026-04-18 21:38:05
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,572 bytes
• コンパイル時間: 4,938 ms
• コンパイル使用メモリ: 386,652 KB
• 実行使用メモリ: 7,644 KB
• 最終ジャッジ日時: 2026-04-18 21:39:29
• 合計ジャッジ時間: 20,688 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 27 TLE * 1 -- * 57

ソースコード

// Compile: g++ -std=c++20 -O2 -Wall -I$HOME/ctf/tools/ac-library -DLOCAL -o sol sol.cpp
// Or:      make sol   (uses Makefile in this dir)
// Run:     ./sol < in.txt
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define rep(i,n) for(ll i=0;i<(ll)(n);++i)
#define rep2(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((ll)(x).size())

template<class T> bool chmin(T&a,const T&b){if(b<a){a=b;return true;}return false;}
template<class T> bool chmax(T&a,const T&b){if(a<b){a=b;return true;}return false;}

#ifdef LOCAL
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl
#else
#define dbg(x)
#endif

using mint = modint998244353;
// using mint = modint1000000007;


/*from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/grid-bfs*/
/// @brief 二次元座標
struct Point
{
	int x, y;
};

/// @brief グリッド上の幅優先探索を行い、スタート地点から各マスまでの最短距離を求めます。
/// @param grid グリッド（'#' は壁、それ以外は通路）
/// @param start スタート地点の座標
/// @return スタート地点から各マスまでの最短距離を記録した二次元配列（-1 は未訪問）
/// @note 出典:『競プロのための標準 C++』
[[nodiscard]]
int GridBFS(const std::vector<std::string>& grid, const Point& start)
{
	// グリッドの行数 (高さ)
	const int H = static_cast<int>(grid.size());

	// グリッドの列数 (幅)
	const int W = static_cast<int>(grid[0].size());
    
	// 各マスまでの最短距離（-1 は未訪問）
	std::vector<std::vector<int>> distances(H, std::vector<int>(W, -1));
	// スタート地点の距離は 0 とする
	distances[start.y][start.x] = 0;
	// 幅優先探索のキュー
	std::queue<Point> q;
	// スタート地点をキューに追加する
	q.push(start);
	// 上下左右のマスへのオフセット
	constexpr Point Offsets[] = { { 0, 1 },{ 1, 0 } };
	while (!q.empty())
	{
            // キューの先頭のマスの座標（現在地）
            const Point current = q.front();
            q.pop();

            // 上下左右の各マスを調べる
            for (const auto& offset : Offsets) {
                // 新たなマスの座標
                const int nx = (current.x + offset.x);
                const int ny = (current.y + offset.y);

                // 範囲外の場合はスキップする
                if ((nx < 0) || (W <= nx) || (ny < 0) || (H <= ny)) {
                    continue;
                }

                // 壁の場合はスキップする
                if (grid[ny][nx] == '#') {
                    continue;
                }

                // すでに訪れている場合はスキップする
                if (distances[ny][nx] != -1) {
                    continue;
                }
                
                if(distances[current.y][current.x] + 1 <= H+W){
                    // 新たなマスまでの距離を記録する
                    distances[ny][nx] = (distances[current.y][current.x] + 1);
    
                    // 新たなマスをキューに追加する
                    q.emplace(nx, ny);
                }
            }
	}

	return distances[H-1][W-1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h,w;
    cin >> h >> w;
    vector<string> c(h);
    rep(i, h) cin >> c[i];
    int ans = h+w;
    int goal_dist = GridBFS(c, {0, 0});
    if (goal_dist != -1) chmin(ans, goal_dist);

    string ins_str = string(w, '.');
    vector<string> new_c = c;
    rep(i, h-1) {
        new_c = c;
        new_c.insert(new_c.begin() + i + 1, ins_str);
        int goal_dist = GridBFS(new_c, {0, 0});
        if (goal_dist != -1) chmin(ans, goal_dist);
        // cout << goal_dist << endl;
    }
    
    rep(j, w-1) {
        new_c = c;
        rep(i, h){
            new_c[i].insert(new_c[i].begin() + j + 1, '.');
        }
        int goal_dist = GridBFS(new_c, {0, 0});
        if (goal_dist != -1) chmin(ans, goal_dist);
        // cout << goal_dist << endl;
    }

    // rep(i, h) {
    //     rep(j, w) {
    //         cout << c[i][j];
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    cout << ans << endl;
    return 0;
}