結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-27 16:16:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,333 ms / 3,000 ms |
コード長 | 2,848 bytes |
コンパイル時間 | 2,791 ms |
コンパイル使用メモリ | 210,832 KB |
最終ジャッジ日時 | 2025-02-21 09:15:43 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i=0; i<n; i++)#define debug 0#define YES cout << "Yes" << endl;#define NO cout << "No" << endl;using ll = long long;using ld = long double;const int mod = 998244353;const int MOD = 1000000007;const double pi = atan2(0, -1);const int inf = 1 << 31 - 1;const ll INF = 1LL << 63-1;#include <time.h>#include <chrono>//vectorの中身を空白区切りで出力template<typename T>void print1(vector<T> v) {for (int i = 0; i < v.size(); i++) {cout << v[i];if (i < v.size() - 1) {cout << " ";}}}//vectorの中身を改行区切りで出力template<typename T>void print2(vector<T> v) {for (auto x : v) {cout << x << endl;}}//二次元配列を出力template<typename T>void printvv(vector<vector<T>> vv) {for (vector<T> v : vv) {print1(v);cout << endl;}}//vectorを降順にソートtemplate<typename T>void rsort(vector<T> &v) {sort(v.begin(), v.end());reverse(v.begin(), v.end());}//昇順priority_queueを召喚template<typename T>struct rpriority_queue {priority_queue<T, vector<T>, greater<T>> pq;void push(T x) {pq.push(x);}void pop() {pq.pop();}T top() {return pq.top();}size_t size() {return pq.size();}bool empty() {return pq.empty();}};int main() {int H ,W;cin >> H >> W;vector<vector<int>> num(H, vector<int>(W));rep(i, H) {rep(j, W) {cin >> num[i][j];}}vector<vector<int>> col(H, vector<int>(W, -1));col[0][0] = 1;col[H - 1][W - 1] = 0;map<int, vector<int>> mp;rep(i, H) {rep(j, W) {mp[num[i][j]] = { i,j };}}set<int> z, o;o.insert(num[1][0]);o.insert(num[0][1]);z.insert(num[H - 1][W - 2]);z.insert(num[H - 2][W - 1]);int cnt = 0;while (1) {bool ed = false;if (cnt % 2 == 0) {int n = *begin(o);int x = mp[n][0];int y = mp[n][1];col[x][y] = 0;if (z.count(n)) {ed = true;}else {o.erase(n);if (x > 0 && col[x - 1][y] == -1) {o.insert(num[x - 1][y]);}if (x < H - 1 && col[x+1][y]==-1) {o.insert(num[x + 1][y]);}if (y > 0 && col[x][y - 1] == -1) {o.insert(num[x][y - 1]);}if (y < W - 1 && col[x][y + 1] == -1) {o.insert(num[x][y + 1]);}}}else {int n = *begin(z);int x = mp[n][0];int y = mp[n][1];col[x][y] = 1;if (o.count(n)) {ed = true;}else {z.erase(n);if (x > 0 && col[x - 1][y] == -1) {z.insert(num[x - 1][y]);}if (x < H - 1 && col[x + 1][y] == -1) {z.insert(num[x + 1][y]);}if (y > 0 && col[x][y - 1] == -1) {z.insert(num[x][y - 1]);}if (y < W - 1 && col[x][y + 1] == -1) {z.insert(num[x][y + 1]);}}}cnt++;if (ed) {break;}}cout << cnt << endl;}