結果

問題 No.2913 二次元距離空間
コンテスト
ユーザー Tatsu_mr
提出日時 2024-10-04 22:08:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 1,415 bytes
コンパイル時間 2,832 ms
コンパイル使用メモリ 261,108 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-10-04 22:08:59
合計ジャッジ時間 3,956 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for(long long i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;

using lint = long long;

vector<int> di = {-1, 0, 1, 0};
vector<int> dj = {0, 1, 0, -1};

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> s(h, vector<char>(w));
    rep(i, h) rep(j, w) {
        cin >> s[i][j];
    }
    auto inc = [&](int i, int j) {
        return (0 <= i && i < h && 0 <= j && j < w);
    };
    vector<vector<pair<int, int>>> d(h, vector<pair<int, int>>(w, {1e9, 1e9}));
    d[0][0] = {0, 0};
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        auto [lr, ud] = d[i][j];
        rep(k, 4) {
            int ni = i + di[k], nj = j + dj[k];
            if (!inc(ni, nj)) {
                continue;
            }
            if (s[ni][nj] == '#') {
                continue;
            }
            int nlr = (k % 2 == 0 ? lr : lr + 1);
            int nud = (k % 2 == 0 ? ud + 1 : ud);
            pair<int, int> np = {nlr, nud};
            if (d[ni][nj] > np) {
                d[ni][nj] = np;
                q.emplace(ni, nj);
            }
        }
    }
    auto [lr, ud] = d[h - 1][w - 1];
    if (lr == 1e9 && ud == 1e9) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        cout << lr << " " << ud << endl;
    }
}
0