結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-22 21:17:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 499 ms / 3,000 ms |
コード長 | 1,628 bytes |
コンパイル時間 | 1,844 ms |
コンパイル使用メモリ | 179,092 KB |
実行使用メモリ | 16,000 KB |
最終ジャッジ日時 | 2024-10-14 21:05:26 |
合計ジャッジ時間 | 11,577 ms |
ジャッジサーバー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 < (int)n; i++)using ll = long long int;using vi = vector<int>;using vvi = vector<vi>;using pii = pair<int, int>;#define INF 1000000001bool comp(int a, int b) {return a > b;}int main() {int H, W;cin >> H >> W;vvi A(H, vi (W));vvi color(H, vi (W, -1));rep(i, H) rep(j, W)cin >> A[i][j];color[0][0] = 1;color[H-1][W-1] = 0;pii s = {0, 0};pii t = {H-1, W-1};vector<int> dx = {0, 1, 0, -1};vector<int> dy = {1, 0, -1, 0};auto f = [&](int x, int y, int i) {return (x + dx[i] >= 0 && x + dx[i] < H &&y + dy[i] >= 0 && y + dy[i] < W);};auto f2 = [&](int x, int y, set<pair<int, pii>> &v) {rep(i, 4) {if (!f(x, y, i))continue;int x1 = x + dx[i];int y1 = y + dy[i];if (color[x1][y1] != -1)continue;v.insert({A[x1][y1], {x1, y1}});}};auto f3 = [&](int x, int y, int n) {rep(i, 4) {if (!f(x, y, i)) continue;if (color[x + dx[i]][y + dy[i]] == n)return true;}return false;};set<pair<int, pii>> sv, tv;int i = 0;while (1) {if (i % 2 == 0) {f2(s.first, s.second, sv);auto it = sv.begin();s = it->second;sv.erase(it);color[s.first][s.second] = 1;i++;if (f3(s.first, s.second, 0))break;} else {f2(t.first, t.second, tv);auto it = tv.begin();t = it->second;tv.erase(it);color[t.first][t.second] = 0;i++;if (f3(t.first, t.second, 1))break;}}cout << i << endl;return 0;}