POJ.2311 Cutting Game

 1.Problem

http://poj.org/problem?id=2311

2.Idea

Using Grundy number

3.Source

 int W, H;  
 int mem[220][220];  
 int grundy(int w, int h)  
 {  
      if (mem[w][h] != -1) return mem[w][h];  
      set<int> s;  
      for (int i = 2; w - i >= 2; i++) {  
           s.insert(grundy(i, h) ^ grundy(w - i, h));  
      }  
      for (int i = 2; h - i >= 2; i++) {  
           s.insert(grundy(w, i) ^ grundy(w, h - i));  
      }  
      int res = 0;  
      while (s.count(res)) res++;  
      return mem[w][h] = res;  
 }  
 void solve()  
 {  
      memset(mem, -1, sizeof mem);  
      while (scanf("%i%i", &W, &H) > 0) {  
           if (grundy(W, H) != 0) puts("WIN");  
           else puts("LOSE");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }