POJ 2311-Cutting Game（Nim博弈-sg函数/记忆化搜索）

比眉伴天荒 2022-07-24 04:09 164阅读 0赞

# Cutting Game #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 3632</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 1352</td> 
  </tr> 
 </tbody> 
</table>

Description

Urej loves to play various types of dull games. He usually asks other people to play with him. He says that playing those games can show his extraordinary wit. Recently Urej takes a great interest in a new game, and Erif Nezorf becomes the victim. To get away from suffering playing such a dull game, Erif Nezorf requests your help. The game uses a rectangular paper that consists of W\*H grids. Two players cut the paper into two pieces of rectangular sections in turn. In each turn the player can cut either horizontally or vertically, keeping every grids unbroken. After N turns the paper will be broken into N+1 pieces, and in the later turn the players can choose any piece to cut. If one player cuts out a piece of paper with a single grid, he wins the game. If these two people are both quite clear, you should write a problem to tell whether the one who cut first can win or not.

Input

The input contains multiple test cases. Each test case contains only two integers W and H (2 <= W, H <= 200) in one line, which are the width and height of the original paper.

Output

For each test case, only one line should be printed. If the one who cut first can win the game, print "WIN", otherwise, print "LOSE".

Sample Input

2 2
    3 2
    4 2

Sample Output

LOSE
    LOSE
    WIN

Source

[POJ Monthly][],CHEN Shixi(xreborner)

## 题目意思： ##

有一张被分成w\*h的格子的长方形纸张，两人轮流沿着格子的边界水平或垂直切割，将纸张分割成两部分。切割了n次之后就得到了n+1张纸，每次都可以选择切得的某一张纸再进行切割。最先切出只有一个格子的纸张（即有1\*1格子的）的一方获胜。当双方都采取最优策略时，先手必胜还是必败？

## 解题思路： ##

初始只有一张纸，纸张的数量随着切割而增加。  
当一张w\*h的纸被分成两张时，假设所得的两张纸的sg值分别为sg1和sg2，  
则它们对应的状态的sg值可以表示为sg1 XOR sg2。  
在Nim中，不论有几堆石子、初始状态是怎样的，只要XOR的结果相同，那么对胜负是没有影响的。这里也一样，只要SG值相同，即使发生分割，只要堆分割后的各部分取XOR，就可以利用这一个SG值来代表几个游戏复合而成的状态，SG值也可以同样地计算。  
了解了会发生分割的游戏的处理方法之后，只要像以前的问题一样，枚举所有一步能够到达的状态的SG值，就能够计算SG值了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <set>
    #include <algorithm>
    using namespace std;
    const int MAXN=202;
    int mem[MAXN][MAXN];//记忆化搜索用的数组
    int grundy(int w,int h)
    {
        if(mem[w][h]!=-1) return mem[w][h];//之前已经搜索过了，可以直接返回记忆的值
        set<int>s;
        //保证边长至少为2
        for(int i=2; w-i>=2; ++i)//剪w边
            s.insert(grundy(i,h)^grundy(w-i,h));
        for(int i=2; h-i>=2; ++i)//剪h边
            s.insert(grundy(w,i)^grundy(w,h-i));
        int res=0;
        while(s.count(res))
            ++res;
        return mem[w][h]=res;
    }
    int main()
    {
        int w,h;
        memset(mem,-1,sizeof(mem));//初始化
        while(~scanf("%d%d",&w,&h))//输入格子长宽
        {
            if(grundy(w,h)) puts("WIN");
            else puts("LOSE");
        }
        return 0;
    }

[POJ Monthly]: http://poj.org/searchproblem?field=source&key=POJ+Monthly