#include #include #include #include #include #include struct Coord { int r, c; Coord(int r_, int c_) : r(r_), c(c_) {} }; Coord operator + (Coord x, Coord y) { return Coord(x.r + y.r, x.c + y.c); } struct GridIte { GridIte(int h_, int w_, int r_, int c_) : hl(h_), wl(w_), r(r_), c(c_) {} int hl, wl; int r, c; GridIte& operator ++ () { c += 1; if( c == wl ) { r += 1; c = 0; } return *this; } Coord operator * () { return Coord(r, c); } bool operator != (const GridIte& right) { return r != right.r or c != right.c; } }; template struct Grid { type v[size][size]; int h, w; type& operator[] (Coord x) { return v[x.r][x.c]; } GridIte begin() { return GridIte(h, w, 0, 0); } GridIte end() { return GridIte(h, w, h, 0); } }; template void load(Grid& grid, std::string format) { for(int i = 0; i < (int)format.size(); ++i) { if( format[i] == 'w' ) scanf("%d", &grid.w); if( format[i] == 'h' ) scanf("%d", &grid.h); } for(int r = 0; r < grid.h; ++r) { for(int c = 0; c < grid.w; ++c) { scanf("%d", &grid[Coord(r, c)]); // if( typeid(a).name() == typeid(int).name() ) scanf("%d", &grid[Coord(r, c)]); // if( typeid(a) == typeid(char) ) grid[Coord(r, c)] = getchar(); // else assert(0); } while( getchar() != '\n' ) ; } } const Coord d4[] = {Coord(1, 0), Coord(0, 1), Coord(-1, 0), Coord(0, -1)}; struct inRange_ { int h, w; inRange_(int h_, int w_) : h(h_), w(w_) {} template inRange_(Grid grid) : h(grid.h), w(grid.w) {} bool operator()(Coord x) { return 0 <= x.r and x.r < h and 0 <= x.c and x.c < w; } }; template int fillGridCC(Grid& grid, Coord x, a to) { inRange_ inRange(grid); std::queue q; a from = grid[x]; q.push(x); int count = 0; grid[x] = to; while( not q.empty() ) { Coord y = q.front(); q.pop(); for(int k = 0; k < 4; ++k) { Coord z = y + d4[k]; if( not inRange(z) ) continue; if( grid[z] != from ) continue; grid[z] = to; count += 1; q.push(z); } } return count + 1; } // verified : http://yukicoder.me/problems/no/13 template bool fillGridCCandCheckLoop(Grid& grid, Coord x, a to) { inRange_ inRange(grid); std::queue q; a from = grid[x]; q.push(x); grid[x] = to; bool res = false; while( not q.empty() ) { Coord y = q.front(); q.pop(); int count = 0; for(int k = 0; k < 4; ++k) { Coord z = y + d4[k]; if( not inRange(z) ) continue; if( grid[z] == to ) count += 1; if( grid[z] != from ) continue; grid[z] = to; q.push(z); } if( count >= 2 ) res = true; } return res; } Grid grid; int main() { load(grid, "wh"); int w = grid.w, h = grid.h; bool res = 0; for(Coord p : grid) { if( grid[p] > 0 ) { res = res or fillGridCCandCheckLoop(grid, p, -grid[p]); } } // for(int r = 0; r < h; ++r) { // for(int c = 0; c < w; ++c) { // Coord p(r, c); // if( grid[p] > 0 ) { // res = res or fillGridCCandCheckLoop(grid, p, -grid[p]); // } // } // } puts(res ? "possible" : "impossible"); return 0; }