BZOJ2719 - Click Here
Description
Input
Output
Solutions
这题是昨天NOIP模拟赛的压轴题。原本能切掉的，但是对于状态数有点虚，不敢上记忆化，然后就GG了。
对于一个棋子而言，在没有吃棋子的状况下，它只能移动3格。
因此可以将这$N \times M$的网格分成
1 2 3
4 5 6
7 8 9
共9个格子，网格内所有格子都可以从9个格子的其中一个格子到达。
这样子，就将$N \times M$压缩成了一个$3 \times 3$的方格。
接着再来考虑一下吃棋子的情况。
将吃棋子放到这$3 \times 3$方格上来分析，不难看出，其实吃棋子等价于将两个棋子合并成一个棋子。而且这三个棋子必定是在同一行、列或对角线。
如果把这个$3 \times 3$的格子看做一个状态的话，很容易可以转移，而且由于每次合并后，棋子都会减少，因此又保证了无后效性，直接记忆化搜索即可。
CODE
CODE - Click Here