結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-19 21:48:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 691 ms / 3,000 ms |
コード長 | 1,509 bytes |
コンパイル時間 | 2,733 ms |
コンパイル使用メモリ | 215,504 KB |
最終ジャッジ日時 | 2025-02-21 04:05:10 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9 + 10;const ll INFL = 4e18;const vector<int> dx = {0, 1, 0, -1};const vector<int> dy = {1, 0, -1, 0};int main() {int H, W;cin >> H >> W;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];}}vector<priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>> pq(2);pq[0].push({A[0][0], 0, 0});pq[1].push({A[H - 1][W - 1], H - 1, W - 1});vector<vector<vector<bool>>> vst(2, vector<vector<bool>>(H, vector<bool>(W, false)));int ans = 0;bool fin = false;int i = 0;while (true) {auto [a, x, y] = pq[i % 2].top();pq[i % 2].pop();if (vst[i % 2][x][y]) {continue;}vst[i % 2][x][y] = true;for (int j = 0; j < 4; j++) {int nx = x + dx[j];int ny = y + dy[j];if (nx < 0 || nx >= H || ny < 0 || ny >= W) {continue;}if (vst[i % 2][nx][ny]) {continue;}if (vst[(i + 1) % 2][nx][ny]) {ans = i - 1;fin = true;break;}pq[i % 2].push({A[nx][ny], nx, ny});}if (fin) {break;}i++;}cout << ans << endl;}