結果

問題 No.13 囲みたい！
ユーザー 久我山菜々久我山菜々
提出日時 2019-02-09 04:39:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,668 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 97,404 KB
最終ジャッジ日時 2025-01-06 21:05:07
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <stack>

int main(int, char**) {
  int W, H;
  std::cin >> W >> H;

  std::vector<std::vector<int>> vec(H, std::vector(W, 0));
  std::vector<std::vector<bool>> map(H, std::vector(W, false));
  for(int i{}; i < H; ++i) {
    for(int j{}; j < W; ++j) {
      std::cin >> vec[i][j];
    }
  }

  bool found{};
  for(int i{}; i < H; ++i) {
    for(int j{}; j < W; ++j) {
      if(map[i][j]) continue;

      map[i][j] = true;
      int const m{vec[i][j]};
      using Point = std::pair<int, int>;
      std::stack<Point> stack;
      stack.emplace(i, j);
      int last{};
      int const unknown{}, up{1}, right{2}, down{3}, left{4};
      std::set<Point> chain;
      chain.emplace(i, j);

      while(!stack.empty()) {
        Point const current{stack.top()};
        int const h = current.first;
        int const w = current.second;
//        std::cout << "## " << h << ' ' << w << std::endl;

        if(last != up && h != 0) {
          if(vec[h - 1][w] == m) {
 //           std::cout << h - 1 << ' ' << w << std::endl;
            auto it = chain.find(std::make_pair(h - 1, w));
            if(it != end(chain)) {
              found = true;
              goto exit;
            }
            if(!map[h - 1][w]) {
              chain.emplace(h - 1, w);
              stack.emplace(h - 1, w);
              map[h - 1][w] = true;
              last = down;
              continue;
            }
          }
        }
        if(last != right && w + 1 != W) {
                                        if(vec[h][w + 1] == m) {
  //          std::cout << h << ' ' << w + 1 << std::endl;
                                                auto it = chain.find(std::make_pair(h, w + 1));
            if(it != end(chain)) {
              found = true;
              goto exit;
            }
            if(!map[h][w + 1]) {
              chain.emplace(h, w + 1);
              stack.emplace(h, w + 1);
              map[h][w + 1] = true;
              last = left;
              continue;
            }
                                        }
        }
        if(last != down && h + 1 != H) {
          if(vec[h + 1][w] == m) {
   //         std::cout << h + 1 << ' ' << w << std::endl;
                                                auto it = chain.find(std::make_pair(h + 1, w));
            if(it != end(chain)) {
              found = true;
              goto exit;
            }
            if(!map[h + 1][w]) {
              chain.emplace(h + 1, w);
              stack.emplace(h + 1, w);
              map[h + 1][w] = true;
              last = up;
              continue;
            }
          }
        }
        if(last != left && w != 0) {
                                        if(vec[h][w - 1] == m) {
    //        std::cout << h << ' ' << w - 1 << std::endl;
                                                auto it = chain.find(std::make_pair(h, w - 1));
            if(it != end(chain)) {
              found = true;
              goto exit;
            }
            if(!map[h][w - 1]) {
              chain.emplace(h, w - 1);
              stack.emplace(h, w - 1);
              map[h][w - 1] = true;
              last = right;
              continue;
            }
                                        }
        }
     //   std::cout << "pop!" << std::endl;
        stack.pop();
        chain.clear();
        last = unknown;
      }
    }
  }
  exit:

  std::cout << (found ? "possible" : "impossible") << std::endl;

//  for(int i{}; i < H; ++i) {
//    for(int j{}; j < W; ++j) {
//      std::cout << vec[i][j] << ' ';
//    }
//    std::cout << std::endl;
//  }
//
  return 0;
}
0