原题地址http://poj.org/problem?id=2422
题目大意：
在一个n*m的棋盘上(n,m<=10), 有一些地方是不可进入的障碍物。棋盘上有3只狼和一只羊，按回合制移动，狼先动，羊后动。
狼和羊都不可以进入障碍物或重叠（狼和狼的重叠以及狼和羊的重叠都是不允许的）。
在狼的回合里，三只狼中选一只狼动一格（上下左右），除非3只狼都不能移动，否则不允许不动。
在羊的会合里，羊上下左右移动一格，如果羊移动后逃出了棋盘，则羊胜利。如果羊无法移动，则狼胜利。
如果羊有一种策略可以使游戏永远进行下去，则也算是羊胜利。
给定初始棋盘，如果两方都按最优策略移动，求胜利者。
算法：
这明显是一道博弈搜索题目。但这个博弈搜索不同于一般的博弈搜索。这个博弈搜索的状态转移是有环的。例如狼往左，羊往左，然后狼往右，羊往右。于是状态又绕回来了。这个也是这道题目的关键所在。
其实我们可以倒过来考虑。考虑羊被困死的所有状态。如果知道所有这样状态的，那么我们就可以倒推一步，得到一个“狼一步后胜利”的狼必胜态列表，再倒退一步，得到“羊一步后必然被困死”的必输态列表。这样反复倒推，最终可以得出起点的属态。
但获得一个羊被困死的所有状态是很困难的。其实有一个比较巧妙地解决方法。就是我们依然从起点正向博弈宽搜，但搜索时并不计算这个状态的属性。一旦发现某个状态羊不能移动了（或移出棋盘了），我们就得到了一个必输（必胜）态，然后沿着这个状态倒推回去，把一路上可以算出属性的状态全部算出属性（如果这个状态是必输态，则它的父母（可能有多达16个）都是必胜态；如果一个状态是必胜态，则把它的父母的孩子数量减一，如果一个父母的孩子数量变成0了，则这个父母状态为必输态（这里的必胜必输都是相对于正在走棋的人而言的））。这样就免去了计算所有必输（必胜）态的困难。
但这样，状态数依然是N^4M^4级别的，转移是34的（3只狼，4个方向），我们需要剪枝。注意到如果一个态的属性已经确定了，那么他所有的子态的属性也就确定了，而且如果起点在这个状态的子态中，那么也必然可以通过往前倒退到达起点。所以一旦一个状态属性被确定，就不需要扩展这个状态了。如果起点的属态确定了，那么就可以直接结束了。加上这个剪枝后实际上计算的状态数并不多，用hash表存储状态就没有问题了。
然后就是代码的问题了……细节很多，很恶心……要注意考虑到所有的情况。