package main import ( "bufio" "fmt" "os" "strconv" ) func getScanner(fp *os.File) *bufio.Scanner { scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) return scanner } func getNextString(scanner *bufio.Scanner) string { scanner.Scan() return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextUint64(scanner *bufio.Scanner) uint64 { i, _ := strconv.ParseUint(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout cnt := 0 if os.Getenv("MASPY") == "ますピ" { fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT")) cnt = 2 } if os.Getenv("MASPYPY") == "ますピッピ" { wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10")) } scanner := getScanner(fp) writer := bufio.NewWriter(wfp) solve(scanner, writer) for i := 0; i < cnt; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } writer.Flush() } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { aa := makeGrid(4, 4) y := -1 x := -1 for i := 0; i < 4; i++ { for j := 0; j < 4; j++ { aa[i][j] = getNextInt(scanner) if aa[i][j] == 0 { y = i x = j } } } used := make([]int, 16) if dfs(y, x, aa, used) { fmt.Fprintln(writer, "Yes") return } fmt.Fprintln(writer, "No") } func dfs(y, x int, aa [][]int, used []int) bool { if check(aa) { return true } dy := [4]int{-1, 0, 0, 1} dx := [4]int{0, -1, 1, 0} for i := 0; i < 4; i++ { yy := y + dy[i] xx := x + dx[i] if yy < 0 || yy >= 4 { continue } if xx < 0 || xx >= 4 { continue } if used[aa[yy][xx]] == 1 { continue } used[aa[yy][xx]] = 1 aa[y][x], aa[yy][xx] = aa[yy][xx], aa[y][x] if dfs(yy, xx, aa, used) { return true } aa[y][x], aa[yy][xx] = aa[yy][xx], aa[y][x] used[aa[yy][xx]] = 0 } return false } func check(aa [][]int) bool { for i := 0; i < 16; i++ { y := i / 4 x := i % 4 if aa[y][x] != (i+1)%16 { return false } } return true } func makeGrid(h, w int) [][]int { index := make([][]int, h, h) data := make([]int, h*w, h*w) for i := 0; i < h; i++ { index[i] = data[i*w : (i+1)*w] } return index }