結果
問題 |
No.1949 足し算するだけのパズルゲーム(2)
|
ユーザー |
![]() |
提出日時 | 2022-05-20 21:43:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 3,000 ms |
コード長 | 1,341 bytes |
コンパイル時間 | 2,122 ms |
コンパイル使用メモリ | 183,624 KB |
実行使用メモリ | 7,536 KB |
最終ジャッジ日時 | 2024-09-20 07:42:00 |
合計ジャッジ時間 | 4,617 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> dx = {1, 0, -1, 0}; vector<int> dy = {0, 1, 0, -1}; int main(){ int H, W, Y, X; cin >> H >> W >> Y >> X; Y--; X--; vector<vector<int>> A(H, vector<int>(W)); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ cin >> A[i][j]; } } long long C = A[Y][X]; vector<vector<bool>> used(H, vector<bool>(W, false)); used[Y][X] = true; priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; for (int i = 0; i < 4; i++){ int x = Y + dx[i]; int y = X + dy[i]; if (0 <= x && x < H && 0 <= y && y < W){ pq.push(make_tuple(A[x][y], x, y)); } } bool ok = true; while (!pq.empty()){ long long P = get<0>(pq.top()); int x = get<1>(pq.top()); int y = get<2>(pq.top()); pq.pop(); if (!used[x][y]){ used[x][y] = true; if (P >= C){ ok = false; } else { C += P; for (int i = 0; i < 4; i++){ int x2 = x + dx[i]; int y2 = y + dy[i]; if (0 <= x2 && x2 < H && 0 <= y2 && y2 < W){ if (!used[x2][y2]){ pq.push(make_tuple(A[x2][y2], x2, y2)); } } } } } } if (ok){ cout << "Yes" << endl; } else { cout << "No" << endl; } }