結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-19 22:24:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 245 ms / 3,000 ms |
コード長 | 2,335 bytes |
コンパイル時間 | 2,812 ms |
コンパイル使用メモリ | 210,420 KB |
最終ジャッジ日時 | 2025-02-21 04:36:43 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>// #include <atcoder/all>using namespace std;// using namespace atcoder;#define rep(i, n) for (int i = 0; i < (n); i++)#define rep1(i, n) for (int i = 1; i <= (n); i++)#define rrep(i, n) for (int i = n - 1; i >= 0; i--)#define rrep1(i, n) for (int i = n; i >= 1; i--)#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define eb emplace_back#define fi first#define se second#define sz(x) (int)(x).size()template <class T> using V = vector<T>;template <class T> using VV = V<V<T>>;typedef long long int ll;// typedef modint998244353 mint;void speedUpIO() {cin.tie(nullptr);ios::sync_with_stdio(false);}template <class T> bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T> bool chmin(T &a, const T &b) {if (b < a) {a = b;return true;}return false;}/*--------------------------------------------------*/typedef pair<int, int> P;typedef pair<P, P> PP;const int INF = 1e9;const ll LINF = 1e18;const int MX = 1e5;V<int> dx = {1, 0, -1, 0};V<int> dy = {0, -1, 0, 1};void solve() {int h, w;cin >> h >> w;VV<int> a(h, V<int>(w));rep(i, h) rep(j, w) cin >> a[i][j];V<set<PP>> st(2);V<string> col(h, string(w, '.'));st[0].insert({{a[0][0], '0'}, {0, 0}});st[1].insert({{a[h - 1][w - 1], '1'}, {h - 1, w - 1}});int i = 0;while (true) {auto [p, p2] = *st[i % 2].begin();auto [_, c] = p;auto [x, y] = p2;col[x][y] = c;st[i % 2].erase(st[i % 2].begin());rep(d, 4) {int nx = x + dx[d];int ny = y + dy[d];if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;if (col[nx][ny] != '.' && col[nx][ny] != col[x][y]) {cout << i - 1 << "\n";return;}if (col[nx][ny] != '.') continue;st[i % 2].insert({{a[nx][ny], c}, {nx, ny}});}i++;}}int main() {speedUpIO();int t = 1;// cin >> t;while (t--) {solve();// cout << solve() << "\n";// cout << (solve() ? "Yes" : "No") << "\n";// cout << fixed << setprecision(15) << solve() << "\n";}return 0;}