結果

問題 No.13 囲みたい！
ユーザー 久我山菜々久我山菜々
提出日時 2019-02-09 05:21:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 13 ms / 5,000 ms
コード長 3,611 bytes
コンパイル時間 1,038 ms
コンパイル使用メモリ 93,568 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 11:52:25
合計ジャッジ時間 1,685 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 11 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 13 ms
6,948 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 5 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 4 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 3 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

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::vector<Point> stack;
      stack.emplace_back(i, j);
      int last{};
      int const up{1}, right{2}, down{3}, left{4};
      std::vector<int> stack_of_last{last};

      while(!stack.empty()) {
        Point const current{stack.back()};
        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 = find(begin(stack), end(stack),std::make_pair(h - 1, w));
            if(it != end(stack)) {
              found = true;
              goto exit;
            }
            if(!map[h - 1][w]) {
              stack.emplace_back(h - 1, w);
              stack_of_last.push_back(last);
              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 = find(begin(stack), end(stack),std::make_pair(h, w + 1));
            if(it != end(stack)) {
              found = true;
              goto exit;
            }
            if(!map[h][w + 1]) {
              stack.emplace_back(h, w + 1);
              stack_of_last.push_back(last);
              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 = find(begin(stack), end(stack),std::make_pair(h + 1, w));
            if(it != end(stack)) {
              found = true;
              goto exit;
            }
            if(!map[h + 1][w]) {
              stack.emplace_back(h + 1, w);
              stack_of_last.push_back(last);
              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 = find(begin(stack), end(stack),std::make_pair(h, w - 1));
            if(it != end(stack)) {
              found = true;
              goto exit;
            }
            if(!map[h][w - 1]) {
              stack.emplace_back(h, w - 1);
              stack_of_last.push_back(last);
              map[h][w - 1] = true;
              last = right;
              continue;
            }
          }
        }
//        std::cout << "pop!" << std::endl;
        stack.pop_back();
        last = stack_of_last.back();
        stack_of_last.pop_back();
      }
//      std::cout << "next !!" << std::endl;
    }
  }
  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