結果
問題 | No.2731 Two Colors |
ユーザー |
👑 ![]() |
提出日時 | 2024-03-14 17:56:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 509 ms / 3,000 ms |
コード長 | 1,652 bytes |
コンパイル時間 | 1,057 ms |
コンパイル使用メモリ | 86,876 KB |
最終ジャッジ日時 | 2025-02-20 04:23:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <algorithm>#include <iostream>#include <queue>#include <vector>using namespace std;using ll = long long;using pll = pair<ll, ll>;int main() {ll H, W;cin >> H >> W;vector<vector<ll>> A(H, vector<ll>(W));for (ll i = 0; i < H; i++) {for (ll j = 0; j < W; j++) {cin >> A[i][j];}}vector<vector<ll>> color(H, vector<ll>(W, -1));vector<priority_queue<pll, vector<pll>, greater<pll>>> pque(2);pque[0].push(pll(A[0][0], 0));pque[1].push(pll(A[H - 1][W - 1], (H - 1) * W + (W - 1)));vector<ll> dx = {1, 0, -1, 0};vector<ll> dy = {0, 1, 0, -1};ll cnt = 0;while (true) {bool finish = false;ll cnt_mod = cnt % 2;pll p = pque[cnt_mod].top();pque[cnt_mod].pop();ll px = p.second / W;ll py = p.second % W;if (color[px][py] != -1) {continue;}color[px][py] = cnt_mod;for (ll i = 0; i < 4; i++) {if (px + dx[i] >= 0 && px + dx[i] < H && py + dy[i] >= 0 &&py + dy[i] < W) {ll new_c = color[px + dx[i]][py + dy[i]];if (new_c != -1) {if (new_c != color[px][py]) {finish = true;break;}} else {pque[cnt_mod].push(pll(A[px + dx[i]][py + dy[i]],(px + dx[i]) * W + (py + dy[i])));}}}cnt++;if (finish) {break;}}cout << cnt - 2 << endl;}