結果
問題 |
No.2913 二次元距離空間
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; } }