結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-05-11 19:14:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,739 ms / 3,000 ms |
コード長 | 1,526 bytes |
コンパイル時間 | 2,318 ms |
コンパイル使用メモリ | 210,392 KB |
最終ジャッジ日時 | 2025-02-21 13:43:49 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using Matrix = vector<vector<ll>>;const int inf = 1000000000;const ll INF = 1000000000000000000;const ll mod = 998244353;const ull mod_hash = (1UL << 61) - 1;const vector<int> dx = {0, 1, 0, -1, 1, 1, -1, -1};const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};int main(){int H,W;cin>>H>>W;vector<vector<ll>> G(H,vector<ll>(W));for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin>>G[i][j];set<ll> seen;set<pair<ll,ll>> zero, one;one.insert({G[0][1], 1});one.insert({G[1][0], W});zero.insert({G[H-1][W-2], (H-1)*W + W - 2});zero.insert({G[H-2][W-1], (H-2)*W + W - 1});seen.insert(0);seen.insert((H - 1) * W + W - 1);int turn = 1;int ans = 0;while(true){pair<ll,ll> ne;if(turn&1){ne = *one.begin();one.erase(one.begin());}else{ne = *zero.begin();zero.erase(zero.begin());}ans++;if(turn&1){if(zero.count(ne))break;}else{if(one.count(ne))break;}seen.insert(ne.second);int x = ne.second/W;int y = ne.second%W;for (int d = 0; d < 4; d++) {int xx = x + dx[d];int yy = y + dy[d];if(xx< 0 || xx >= H || yy < 0 || yy >= W)continue;if(seen.count(xx*W+yy))continue;if(turn&1){one.insert({G[xx][yy], xx*W+yy});}else{zero.insert({G[xx][yy], xx*W+yy});}}turn ^= 1;}cout << ans << endl;return 0;}