Guest User

robs CAOS 3 codechef

a guest
Oct 14th, 2013
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 1.50 KB | None | 0 0
  1. //gets wrong answer.
  2.  
  3. package main
  4.  
  5. import (
  6.     "fmt"
  7. )
  8.  
  9. var m [20]string
  10. var monsters [20][20]bool
  11. var cache [21][21][21][21]int
  12. var cache_level [21][21][21][21]int
  13. var level = 0
  14.  
  15. func main() {
  16.     var T int
  17.     fmt.Scan(&T)
  18.     for ; T > 0; T-- {
  19.         level++
  20.         var R, C int
  21.         fmt.Scan(&R)
  22.         fmt.Scanf("%d\n", &C)
  23.         for i := 0; i < R; i++ {
  24.             fmt.Scanln(&m[i])
  25.         }
  26.         solve(R, C)
  27.     }
  28. }
  29.  
  30.  
  31. func solve(R, C int) {
  32.     for i := 0; i < 20; i++ {
  33.         for j := 0; j < 20; j++ {
  34.             monsters[i][j] = false
  35.         }
  36.     }
  37.     find_monsters(R, C)
  38.  
  39.     if win(0, 0, R, C) != 0 {
  40.         fmt.Println("Asuna")
  41.     } else {
  42.         fmt.Println("Kirito")
  43.     }
  44. }
  45.  
  46. func win(i1, j1, i2, j2 int) int {
  47.     if cache_level[i1][j1][i2][j2] == level {
  48.         return cache[i1][j1][i2][j2]
  49.     }
  50.     grundy_numbers := make(map[int]bool)
  51.     for i := i1; i < i2; i++ {
  52.         for j := j1; j < j2; j++ {
  53.             if monsters[i][j] {
  54.                 game1 := win(i1, j1, i, j)
  55.                 game2 := win(i1, j + 1, i, j2)
  56.                 game3 := win(i + 1, j1, i2, j)
  57.                 game4 := win(i + 1, j + 1, i2, j2)
  58.                 grundy := game1 ^ game2 ^ game3 ^ game4
  59.                 grundy_numbers[grundy] = true
  60.             }
  61.         }
  62.     }
  63.     mex := 0
  64.     for grundy_numbers[mex] {
  65.         mex++
  66.     }
  67.     cache_level[i1][j1][i2][j2] = level
  68.     cache[i1][j1][i2][j2] = mex
  69.     return mex
  70. }
  71.  
  72. func find_monsters(R, C int) {
  73.     for i := 2; i + 2 < R; i++ {
  74.         for j := 2; j + 2 < C; j++ {
  75.             ok := true
  76.             for dx := -2; dx <= 2; dx++ {
  77.                 if (m[i+dx][j] == '#') || (m[i][j+dx] == '#') {
  78.                     ok = false
  79.                 }
  80.             }
  81.             if ok {
  82.                 monsters[i][j] = true
  83.             }
  84.         }
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment