Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //gets wrong answer.
- package main
- import (
- "fmt"
- )
- var m [20]string
- var monsters [20][20]bool
- var cache [21][21][21][21]int
- var cache_level [21][21][21][21]int
- var level = 0
- func main() {
- var T int
- fmt.Scan(&T)
- for ; T > 0; T-- {
- level++
- var R, C int
- fmt.Scan(&R)
- fmt.Scanf("%d\n", &C)
- for i := 0; i < R; i++ {
- fmt.Scanln(&m[i])
- }
- solve(R, C)
- }
- }
- func solve(R, C int) {
- for i := 0; i < 20; i++ {
- for j := 0; j < 20; j++ {
- monsters[i][j] = false
- }
- }
- find_monsters(R, C)
- if win(0, 0, R, C) != 0 {
- fmt.Println("Asuna")
- } else {
- fmt.Println("Kirito")
- }
- }
- func win(i1, j1, i2, j2 int) int {
- if cache_level[i1][j1][i2][j2] == level {
- return cache[i1][j1][i2][j2]
- }
- grundy_numbers := make(map[int]bool)
- for i := i1; i < i2; i++ {
- for j := j1; j < j2; j++ {
- if monsters[i][j] {
- game1 := win(i1, j1, i, j)
- game2 := win(i1, j + 1, i, j2)
- game3 := win(i + 1, j1, i2, j)
- game4 := win(i + 1, j + 1, i2, j2)
- grundy := game1 ^ game2 ^ game3 ^ game4
- grundy_numbers[grundy] = true
- }
- }
- }
- mex := 0
- for grundy_numbers[mex] {
- mex++
- }
- cache_level[i1][j1][i2][j2] = level
- cache[i1][j1][i2][j2] = mex
- return mex
- }
- func find_monsters(R, C int) {
- for i := 2; i + 2 < R; i++ {
- for j := 2; j + 2 < C; j++ {
- ok := true
- for dx := -2; dx <= 2; dx++ {
- if (m[i+dx][j] == '#') || (m[i][j+dx] == '#') {
- ok = false
- }
- }
- if ok {
- monsters[i][j] = true
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment