結果
問題 | No.20 砂漠のオアシス |
ユーザー | xuzijian629 |
提出日時 | 2018-11-02 22:21:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 1,873 bytes |
コンパイル時間 | 1,800 ms |
コンパイル使用メモリ | 205,144 KB |
最終ジャッジ日時 | 2025-01-06 15:27:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; int main() { int n, v, ox, oy; cin >> n >> v >> oy >> ox; ox--; oy--; vvi b(n, vi(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> b[i][j]; } } int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; auto ok = [&](int a, int b) { return 0 <= a && a < n && 0 <= b && b < n; }; vvi d(n, vi(n, -1)); d[0][0] = v; using ii = pair<int, int>; queue<ii> que; que.push(ii(0, 0)); while (que.size()) { ii t = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int x = t.first + dx[i]; int y = t.second + dy[i]; if (ok(x, y)) { int vv = d[t.first][t.second] - b[x][y]; if (vv > 0 && d[x][y] < vv) { d[x][y] = vv; que.push(ii(x, y)); } } } } if (d[n - 1][n - 1] != -1) { cout << "YES" << endl; return 0; } if ((ox == -1 && oy == -1) || d[ox][oy] == -1) { cout << "NO" << endl; return 0; } v = d[ox][oy] * 2; d = vvi(n, vi(n, -1)); d[ox][oy] = v; using ii = pair<int, int>; que.push(ii(ox, oy)); while (que.size()) { ii t = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int x = t.first + dx[i]; int y = t.second + dy[i]; if (ok(x, y)) { int vv = d[t.first][t.second] - b[x][y]; if (vv > 0 && d[x][y] < vv) { d[x][y] = vv; que.push(ii(x, y)); } } } } cout << (d[n - 1][n - 1] == -1 ? "NO" : "YES") << endl; }