結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 23:28:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 380 ms / 3,000 ms |
コード長 | 2,191 bytes |
コンパイル時間 | 3,474 ms |
コンパイル使用メモリ | 259,272 KB |
実行使用メモリ | 15,360 KB |
最終ジャッジ日時 | 2024-10-11 18:07:05 |
合計ジャッジ時間 | 9,998 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>using namespace std;const int INF = 1<<30;const int MOD = 998244353;//const long long INF = 1LL<<60;using graph = vector<vector<int>>;using ll = long long;int dx[] = {1, 0, -1, 0};int dy[] = {0, -1, 0, 1};void print(vector<vector<int>> & vec, int h, int w){for (int i=0; i < h; i++){for (int j=0; j < w; j++){cout << vec[i][j];}cout << endl;}}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<vector<int>> region1(h, vector<int>(w)), region0(h, vector<int>(w));priority_queue<tuple<int, int, int>> pq1, pq0;pq1.push(make_tuple(-a[0][0], 0, 0));pq0.push(make_tuple(-a[h-1][w-1], h-1, w-1));for (int i=1; i <= h*w; i++){if (i % 2 == 1){int v, x, y;tie(v, x, y) = pq1.top();pq1.pop();if (region0[x][y] != 0){cout << i-2 << endl;return 0;}region1[x][y] = 2;for (int j=0; j < 4; j++){int nx = x + dx[j];int ny = y + dy[j];if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue;if (region1[nx][ny] == 0){region1[nx][ny] = 1;pq1.push(make_tuple(-a[nx][ny], nx, ny));}continue;}}if (i % 2 == 0){int v, x, y;tie(v, x, y) = pq0.top();pq0.pop();region0[x][y] = 2;//cout << i << x << y << v << endl;if (region1[x][y] != 0){cout << i-2 << endl;return 0;}for (int j=0; j < 4; j++){int nx = x + dx[j];int ny = y + dy[j];if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue;if (region0[nx][ny] == 0){region0[nx][ny] = 1;pq0.push(make_tuple(-a[nx][ny], nx, ny));}}}}}