#include #include #include #include int main(int, char**) { int W, H; std::cin >> W >> H; std::vector> vec(H, std::vector(W, 0)); std::vector> 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; std::stack stack; stack.emplace(i, j); int last{}; int const unknown{}, up{1}, right{2}, down{3}, left{4}; std::set 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; }