結果

問題 No.3504 Insert Maze
コンテスト
ユーザー dayo ZOI
提出日時 2026-04-19 00:08:05
言語 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
結果
RE  
実行時間 -
コード長 2,665 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,086 ms
コンパイル使用メモリ 189,408 KB
実行使用メモリ 170,112 KB
最終ジャッジ日時 2026-04-19 00:09:13
合計ジャッジ時間 23,501 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 RE * 8 TLE * 1 -- * 57
権限があれば一括ダウンロードができます

ソースコード

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<ll> dist(H * W, INF);
    dist[0] = 0;
    rep(x, H) {
        rep(d, x+1) {
            ll idx = ptoi({x-d, d});
            for(auto c : g[idx]) {
                dist[c] = min(dist[c], dist[idx] + 1);
            }
        }
    }
    rep(y, W) {
        rep(d, W-y) {
            ll idx = ptoi({H-1-d, y+d});
            for(auto c : g[idx]) {
                dist[c] = min(dist[c], dist[idx] + 1);
            }
        }
    }
    cout << (dist.back() == INF ? -1 : dist.back()) << endl;
}
0