結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 21:39:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 281 ms / 3,000 ms |
コード長 | 1,563 bytes |
コンパイル時間 | 2,992 ms |
コンパイル使用メモリ | 216,096 KB |
最終ジャッジ日時 | 2025-02-21 03:55:07 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int H,W; cin >> H >> W;vector<vector<int>> A(H,vector<int>(W));for(int i=0; i<H; i++) for(int k=0; k<W; k++) cin >> A.at(i).at(k);vector<vector<bool>> alr(H,vector<bool>(W)),alb = alr;priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> qr,qb;bool end = false;int answer = -2;qr.push({0,0,0}),qb.push({0,H-1,W-1});vector<pair<int,int>> dxy = {{-1,0},{0,1},{1,0},{0,-1}};while(true){auto[a,x,y] = qr.top(); qr.pop();while(alr.at(x).at(y)){tie(a,x,y) = qr.top(); qr.pop();}alr.at(x).at(y) = true;answer++;for(auto &[dx,dy] : dxy){int nx = x+dx,ny = y+dy;if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;if(alr.at(nx).at(ny)) continue;if(alb.at(nx).at(ny)){end = true; break;}qr.push({A.at(nx).at(ny),nx,ny});}if(end) break;tie(a,x,y) = qb.top(); qb.pop();while(alb.at(x).at(y)){tie(a,x,y) = qb.top(); qb.pop();}alb.at(x).at(y) = true;answer++;for(auto &[dx,dy] : dxy){int nx = x+dx,ny = y+dy;if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;if(alb.at(nx).at(ny)) continue;if(alr.at(nx).at(ny)){end = true; break;}qb.push({A.at(nx).at(ny),nx,ny});}if(end) break;}cout << answer << endl;}