結果

問題 No.13 囲みたい！
コンテスト
ユーザー warashi
提出日時 2016-04-29 20:11:33
言語 Go
(1.23.4)
結果
AC  
実行時間 49 ms / 5,000 ms
コード長 1,458 bytes
コンパイル時間 14,690 ms
コンパイル使用メモリ 237,972 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 10:53:14
合計ジャッジ時間 15,708 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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
}
0