結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 23:16:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 949 ms / 3,000 ms |
コード長 | 1,833 bytes |
コンパイル時間 | 4,890 ms |
コンパイル使用メモリ | 258,092 KB |
最終ジャッジ日時 | 2025-02-21 05:33:11 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using ll = long long;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define all(v) v.begin(), v.end()vector<pair<int, int>> dxy = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int main() {int H, W;cin >> H >> W;vector<vector<int>> A(H, vector<int>(W));vector<vector<int>> visited(H, vector<int>(W, -1));vector<priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>> hq(2);for (int i = 0; i < H; ++i) {for (int j = 0; j < W; ++j) {cin >> A[i][j];}}visited[0][0] = 0;visited[H - 1][W - 1] = 1;for (int i = 0; i < 2; ++i) {int x = (i == 0) ? 0 : H - 1;int y = (i == 0) ? 0 : W - 1;for (auto& [dx, dy] : dxy) {int _x = x + dx;int _y = y + dy;if (_x < 0 || _x >= H || _y < 0 || _y >= W) {continue;}hq[i].push({A[_x][_y], _x, _y});}}int i = 0;while (true) {int ii = i % 2;vector<int> tmp = hq[ii].top();int a = tmp[0];int x = tmp[1];int y = tmp[2];hq[ii].pop();if (visited[x][y] != -1) {continue;}visited[x][y] = ii;for (auto& [dx, dy] : dxy) {int _x = x + dx;int _y = y + dy;if (_x < 0 || _x >= H || _y < 0 || _y >= W) {continue;}if (visited[_x][_y] == ii) {continue;}if (visited[_x][_y] == (ii + 1) % 2) {cout << i + 1 << endl;return 0;}hq[ii].push({A[_x][_y], _x, _y});}i++;}return 0;}