package main import ( "fmt" ) type point struct { x, y int } type node struct { d int p point } type nodeStack []*node func (s *nodeStack) push(n *node) { *s = append(*s, n) } func (s *nodeStack) pop() *node { n := (*s)[len(*s)-1] *s = (*s)[:len(*s)-1] return n } var went = make(map[point]bool) func dfs(m [][]int, w, h, x, y int) bool { if _, ok := went[point{x: x, y: y}]; ok { return false } r := []point{{0, -1}, {1, 0}, {-1, 0}, {0, 1}} c := m[y][x] var s nodeStack s = append(s, &node{d: -1, p: point{x: x, y: y}}) for len(s) > 0 { n := s.pop() if m[n.p.y][n.p.x] == c { if _, ok := went[point{x: n.p.x, y: n.p.y}]; ok { return true } went[point{x: n.p.x, y: n.p.y}] = true for i, d := range r { if i == n.d { // 直前に移動してきた方向には帰らない continue } nx := n.p.x + d.x ny := n.p.y + d.y if nx < 0 || w <= nx { continue } if ny < 0 || h <= ny { continue } s.push(&node{ d: 3 - i, p: point{ x: n.p.x + d.x, y: n.p.y + d.y, }, }) } } } return false } func main() { var w, h int fmt.Scan(&w, &h) m := make([][]int, h) for y := 0; y < h; y++ { m[y] = make([]int, w) for x := 0; x < w; x++ { fmt.Scan(&m[y][x]) } } for y := 0; y < h; y++ { for x := 0; x < w; x++ { if dfs(m, w, h, x, y) { fmt.Println("possible") return } } } fmt.Println("impossible") return }