結果
問題 | No.2913 二次元距離空間 |
ユーザー |
|
提出日時 | 2024-10-04 22:52:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 1,082 bytes |
コンパイル時間 | 2,179 ms |
コンパイル使用メモリ | 203,216 KB |
最終ジャッジ日時 | 2025-02-24 15:31:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main () {int H, W;cin >> H >> W;char A[555][555];for (int i = 0; i <= H + 1; i ++) {for (int j = 0; j <= W + 1; j ++) {if (0 < i && i <= H && 0 < j && j <= W) {cin >> A[i][j];} else {A[i][j] = '#';}}}using P = pair<int, int>;P D[555][555];for (auto& a : D) {for (auto& [p, q] : a) {q = p = 1e9 + 7;}}using PP = tuple<P, int, int>;priority_queue<PP, std::vector<PP>, greater<PP>> pque;D[1][1] = P{0, 0};pque.emplace(D[1][1], 1, 1);while (!pque.empty()) {auto [l, ui, uj] = pque.top();pque.pop();for (int d = -1; d < 2; d += 2) {int vi = ui + d;P l2 = l;l2.second ++;if (A[vi][uj] == '.' && D[vi][uj] > l2) {D[vi][uj] = l2;pque.emplace(l2, vi, uj);}l2.second --;l2.first ++;int vj = uj + d;if (A[ui][vj] == '.' && D[ui][vj] > l2) {D[ui][vj] = l2;pque.emplace(l2, ui, vj);}}}auto& [p, q] = D[H][W];if (p > H * W * 2) {puts("No");} else {cout << "Yes\n" << p << " " << q << endl;}}