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

• 問題: No.3504 Insert Maze
• ユーザー: amano-amane
• 提出日時: 2026-04-18 23:30:17
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 290 ms / 2,000 ms
• コード長: 4,909 bytes
• コンパイル時間: 4,934 ms
• コンパイル使用メモリ: 380,472 KB
• 実行使用メモリ: 39,168 KB
• 最終ジャッジ日時: 2026-04-18 23:30:32
• 合計ジャッジ時間: 13,418 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

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

ソースコード

// 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]]
std::vector<std::vector<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 },{ 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;
}

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;
    auto dist_s = GridBFS(c, {0, 0}); // from S
    auto dist_g = GridBFS(c, {w-1, h-1}); // from G
    int goal_dist = dist_s[h-1][w-1];
    if (goal_dist != -1) {
        ans = h + w - 2;
        cout << ans << endl;
        return 0;
    }
    
    // rep(i,h) {
    //     rep(j,w) cout << dist_g[i][j];
    //     cout << endl;
    // }

    rep(i, h-1){
        bool ok = false;
        rep(j, w) {
            if (dist_s[i][j] == i + j) ok = true;
        }
        rep(j, w) {
            if (dist_g[i+1][j] == (h-i-1)-1 + (w-j-1)) {
                if(ok) {
                    ans = h + w - 1;
                    cout << ans << endl;
                    return 0;
                }
            }
        }
    }

    rep(j, w-1){
        bool ok = false;
        rep(i, h) {
            if (dist_s[i][j] == i + j) ok = true;
        }
        rep(i, h) {
            if (dist_g[i][j+1] == (h-i-1) + (w-j-1)-1) {
                if(ok) {
                    ans = h + w - 1;
                    cout << ans << endl;
                    return 0;
                }
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}