結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-20 18:37:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 689 ms / 3,000 ms |
コード長 | 1,724 bytes |
コンパイル時間 | 934 ms |
コンパイル使用メモリ | 84,172 KB |
最終ジャッジ日時 | 2025-02-21 07:11:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<iostream>#include<vector>#include<queue>using color_t = int;constexpr int NONE = 2;struct pos_t {int r;int c;int value;friend bool operator<(pos_t l, pos_t r){return l.value < r.value;}friend bool operator>(pos_t l, pos_t r){return l.value > r.value;}};int main(){int h, w;std::cin>>h>>w;std::vector<std::vector<int>> a(h);for(int i = 0; i < h; i++){for(int j = 0; j < w; j++){int x;std::cin>>x;a[i].push_back(x);}}std::vector<std::vector<color_t>> colors(h, std::vector<color_t>(w, NONE));colors[0][0] = 1;colors[h-1][w-1] = 0;std::priority_queue<pos_t, std::vector<pos_t>, std::greater<pos_t>> que[2];auto valid = [&](int r, int c){return 0 <=r && r < h && 0 <= c && c < w;};auto neighbors = [&](int r, int c){pos_t direction[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};std::vector<pos_t> res;for(auto d: direction){d.r += r;d.c += c;if(valid(d.r, d.c)){d.value = a[d.r][d.c];res.push_back(d);}}return res;};for(auto pos: neighbors(0,0)){que[1].push(pos);}for(auto pos: neighbors(h-1, w-1)){que[0].push(pos);}int ans = 0;while(true){int color = ++ans % 2;bool clear = false;while(que[color].size()){pos_t pos = que[color].top(); que[color].pop();if(colors[pos.r][pos.c] != NONE){continue;}// std::cerr << pos.r << " " << pos.c << std::endl;colors[pos.r][pos.c] = color;for(auto pos:neighbors(pos.r, pos.c)){if(colors[pos.r][pos.c] == (color ^ 1)){// std::cerr << colors[pos.r][pos.c] << std::endl;clear = true;}que[color].push(pos);}break;}if(clear){break;}}std::cout << ans << std::endl;}