結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-19 21:55:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 712 ms / 3,000 ms |
コード長 | 1,818 bytes |
コンパイル時間 | 1,172 ms |
コンパイル使用メモリ | 85,496 KB |
最終ジャッジ日時 | 2025-02-21 04:12:35 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<iostream>#include<vector>#include<queue>using namespace std;int main(){int h,w;cin >> h >> w;vector<vector<int>>num(h,vector<int>(w));for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin >> num[i][j];priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>prq1;priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>prq2;vector<vector<int>>color(h,vector<int>(w,-1));prq1.push({0,0,0});prq2.push({0,h-1,w-1});int cnt=1,ans=0;while(true){ans++;if(cnt==1){int a,b;while(true){vector<int>hako=prq1.top();prq1.pop();a=hako[1];b=hako[2];if(color[a][b]==-1)break;}color[a][b]=1;if(a-1>=0){if(color[a-1][b]==0)break;else if(color[a-1][b]==-1)prq1.push({num[a-1][b],a-1,b});}if(b+1<w){if(color[a][b+1]==0)break;else if(color[a][b+1]==-1)prq1.push({num[a][b+1],a,b+1});}if(a+1<h){if(color[a+1][b]==0)break;else if(color[a+1][b]==-1)prq1.push({num[a+1][b],a+1,b});}if(b-1>=0){if(color[a][b-1]==0)break;else if(color[a][b-1]==-1)prq1.push({num[a][b-1],a,b-1});}cnt=0;}else{int a,b;while(true){vector<int>hako=prq2.top();prq2.pop();a=hako[1];b=hako[2];if(color[a][b]==-1)break;}color[a][b]=0;if(a-1>=0){if(color[a-1][b]==1)break;else if(color[a-1][b]==-1)prq2.push({num[a-1][b],a-1,b});}if(b+1<w){if(color[a][b+1]==1)break;else if(color[a][b+1]==-1)prq2.push({num[a][b+1],a,b+1});}if(a+1<h){if(color[a+1][b]==1)break;else if(color[a+1][b]==-1)prq2.push({num[a+1][b],a+1,b});}if(b-1>=0){if(color[a][b-1]==1)break;else if(color[a][b-1]==-1)prq2.push({num[a][b-1],a,b-1});}cnt=1;}}cout << ans-2 << endl;}