結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-19 22:07:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 3,000 ms |
コード長 | 5,117 bytes |
コンパイル時間 | 1,484 ms |
コンパイル使用メモリ | 141,740 KB |
最終ジャッジ日時 | 2025-02-21 04:21:26 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <string.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template <typename T> using vc = vector<T>;template <typename T> using vvc = vector<vector<T>>;template <typename T> using vvvc = vector<vector<vector<T>>>;template<class T> using pq = priority_queue<T,vector<T>,greater<T>>;template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }#define overload5(a, b, c, d, e, name, ...) name#define overload4(a, b, c, d, name, ...) name#define endl '\n'#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)#define REP1(i, n) for(ll i = 0; i < (n); ++i)#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)#define setbits(j, n) for(ll iiiii = (n), j = lowbit(iiiii); iiiii; iiiii ^= 1 << j, j = lowbit(iiiii))#define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));)#define fi first#define se second#define pb push_back#define ppb pop_back#define ppf pop_front#define drop(s) cout << #s << endl, exit(0)#define si(c) (int)(c).size()#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))#define rng(v, l, r) v.begin() + (l), v.begin() + (r)#define all(c) begin(c), end(c)#define rall(c) rbegin(c), rend(c)#define SORT(v) sort(all(v))#define REV(v) reverse(all(v))#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())#define MIN(v) *min_element(all(v))#define MAX(v) *max_element(all(v))#define overload2(_1, _2, name, ...) name#define vec(type, name, ...) vector<type> name(__VA_ARGS__)#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))int dx4[4] = {0,1,0,-1};int dy4[4] = {1,0,-1,0};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int h,w;cin >> h >> w;vvc<int> a(h,vc<int>(w));vvc<int> f(h,vc<int>(w,-1));rep(i,h) {rep(j,w) {cin >> a[i][j];}}pq<array<int,3>>pq1,pq0;pq1.push({a[0][1],0,1});pq1.push({a[1][0],1,0});pq0.push({a[h-1][w-2],h-1,w-2});pq0.push({a[h-2][w-1],h-2,w-1});f[0][0] = 1;f[h-1][w-1] = 0;int ans = 0;rep(i,h*w) {ans++;if(i%2 == 0) {while(!pq1.empty()) {auto x = pq1.top();pq1.pop();if(f[x[1]][x[2]] != -1) continue;f[x[1]][x[2]] = 1;rep(j,4) {int nx = x[1]+dx4[j];int ny = x[2]+dy4[j];if(nx >= 0 && nx < h && ny >= 0 && ny < w) {if(f[nx][ny] == -1) {pq1.push({a[nx][ny],nx,ny});}if(f[nx][ny] == 0) {cout << ans << "\n";return 0;}}}break;}}else {while(!pq0.empty()) {auto x = pq0.top();pq0.pop();if(f[x[1]][x[2]] != -1) continue;f[x[1]][x[2]] = 0;rep(j,4) {int nx = x[1]+dx4[j];int ny = x[2]+dy4[j];if(nx >= 0 && nx < h && ny >= 0 && ny < w) {if(f[nx][ny] == -1) {pq0.push({a[nx][ny],nx,ny});}if(f[nx][ny] == 1) {cout << ans << "\n";return 0;}}}break;}}}}