基本分析
棋盘状态是一个三元组（老鼠位置，猫的位置，轮到谁走）。如果一个状态a走一步，能到下一个状态b，那么就画一条边a->b。这样所有棋局状态构成一个有向图。
老鼠赢的条件是老鼠位置在0。猫赢的条件是猫和老鼠在同一格（猫不能走到0）。
思路：广度优先。从这些输赢已定的棋盘状态倒推，标注每一个状态的输赢情况。
怎么倒推？
以轮到老鼠走的节点看，
- 如果下一个状态有一个已经被标注为老鼠赢。老鼠当然会选择走那一步。并且肯定将来能赢了。
- 如果下一步所有状态都是猫赢，那么虽然这一步是轮到老鼠走，但是没得选——走投无路了。
- 否则就是胜负未分。
如果当前节点是轮到猫走，就反过来：
- 下一状态只要有一个是猫赢，这个状态就是猫赢，因为猫肯定会选最好的步。
- 如果所有下一状态都是老鼠赢，那么猫怎么选都是输。
- 否则就是胜负未分。
难点是什么时候停止算法？
暂时想不清楚。把致胜道路从后往前传。对于每个节点如果有新的致胜信息就继续往后传。传不动了整个图的胜负标注就稳定了。
从一个状态出发，下一步能走到哪些状态？
取决于轮到谁走，比如轮到老鼠走，下一步就是老鼠所在的原图节点有哪些相邻节点。（前面说节点是指棋局transposition状态三元组，这里是指棋盘board）。猫的位置不变。
以下是官网的solution的倒推部分：
// What nodes could play their turn to
// arrive at node (m, c, t) ?
public List<int[]> parents(int[][] graph, int m, int c, int t) {
List<int[]> ans = new ArrayList();
if (t == 2) {
for (int m2: graph[m])
ans.add(new int[]{m2, c, 3-t});
} else {
for (int c2: graph[c]) if (c2 > 0)
ans.add(new int[]{m, c2, 3-t});
}
return ans;
}
如果轮到猫走以此类推。（除了猫不允许走到0，轮到猫走的时候，棋盘没有0号节点）
官网solution给的答案
它的queue存放了4元组，除了(鼠，猫，轮到谁）还存了颜色——就是胜负状态。其实没必要存，查表能查到吧？
color(0, i, t) == MOUSE
就往队列存放(0, i ,t, MOUSE)，完全可以在出队的时候拿着0,i,t去查询数组呀？
Queue<int[]> queue = new LinkedList();
for (int i = 0; i < N; ++i)
for (int t = 1; t <= 2; ++t) {
color[0][i][t] = MOUSE;
queue.add(new int[]{0, i, t, MOUSE});
if (i > 0) {
color[i][i][t] = CAT;
queue.add(new int[]{i, i, t, CAT});
}
}
