結果

問題 No.3504 Insert Maze
コンテスト
ユーザー dayo ZOI
提出日時 2026-04-18 23:59:47
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,985 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,938 ms
コンパイル使用メモリ 194,580 KB
実行使用メモリ 984,064 KB
最終ジャッジ日時 2026-04-19 00:01:35
合計ジャッジ時間 17,374 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 3 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <cassert>
#include <queue>

using namespace std;
using ll = long long;

#define rep(i, n) for (int i = 0; i < n; ++i)

int main()
{
    ll h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    s[0][0] = '.';
    s[h-1][w-1] = '.';

    ll H = h * 2 - 1;
    ll W = w * 2 - 1;
    auto itop = [&](ll i) {
        return pair{i / W, i % W};
    };
    auto ptoi = [&](pair<ll, ll> p) {
        return p.first * W + p.second;
    };
    vector<vector<ll>> g(H * W);
    rep(i, h) {
        rep(j, w) {
            if(s[i][j] == '.') {
                if(j < w-1 && s[i][j+1] == '.') {
                    g[ptoi({i * 2, j * 2})].emplace_back(ptoi({i * 2, j * 2 + 2}));
                }
                if(i < h-1 && s[i+1][j] == '.') {
                    g[ptoi({i * 2, j * 2})].emplace_back(ptoi({i * 2 + 2, j * 2}));
                }
                if(i < h-1) {
                    g[ptoi({i * 2, j * 2})].emplace_back(ptoi({i * 2 + 1, j * 2}));
                }
                if(j < w-1) {
                    g[ptoi({i * 2, j * 2})].emplace_back(ptoi({i * 2, j * 2 + 1}));
                }
            }
        }
    }

    rep(i, h) {
        rep(j, w) {
            if(i != h-1) {
                g[ptoi({i * 2 + 1, j * 2})].emplace_back(ptoi({i * 2 + 2, j * 2}));
            }
            if(j != w-1) {
                g[ptoi({i * 2, j * 2 + 1})].emplace_back(ptoi({i * 2, j * 2 + 2}));
            }
            if(i != h-1 && j != w-1) {
                g[ptoi({i * 2 + 1, j * 2})].emplace_back(ptoi({i * 2 + 1, j * 2 + 1}));
                g[ptoi({i * 2 + 1, j * 2})].emplace_back(ptoi({i * 2 + 1, j * 2 + 2}));
                g[ptoi({i * 2, j * 2 + 1})].emplace_back(ptoi({i * 2 + 1, j * 2 + 1}));
                g[ptoi({i * 2, j * 2 + 1})].emplace_back(ptoi({i * 2 + 2, j * 2 + 1}));
                g[ptoi({i * 2 + 1, j * 2 + 1})].emplace_back(ptoi({i * 2 + 2, j * 2 + 1}));
                g[ptoi({i * 2 + 1, j * 2 + 1})].emplace_back(ptoi({i * 2 + 1, j * 2 + 2}));
            }
        }
    }
    const ll INF = 1LL<<60;
    vector<vector<ll>> dist(H, vector<ll>(W, INF));
    dist[0][0] = 0;
    queue<ll> q;
    q.emplace(0);
    while(!q.empty()) {
        auto v = q.front();
        q.pop();
        auto vp = itop(v);
        // cout << vp.first <<" " << vp.second << endl;
        auto cost = dist[vp.first][vp.second];
        cost++;
        for(auto c : g[v]) {
            auto p = itop(c);
            // cout << p.first << " " << p.second << endl;
            if(dist[p.first][p.second] > cost) {
                q.emplace(c);
                dist[p.first][p.second] = cost;
            }
        }
    // rep(i, H) {
    //     rep(j, W) {
    //         cout << dist[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << "---" << endl;
    }
    cout << (dist[H-1][W-1] == INF ? -1 : dist[H-1][W-1]) << endl;
}
0