The Sprague-Grundy theory
前言
The Sprague-Grundy theory是博弈论中解决公平游戏的一个重要定理。这里不对定理进行展开解释与证明，有兴趣的可以去看一下百度上Nim游戏对于定理的运用，也可以在下面解题中体会其中原理，这里直接给出定理：
Sprague-Grundy定理：
设gi为一个游戏Gi的Sprague-Grundy函数，则组合游戏G=G1+G2+…+Gn的Sprague-Grundy函数g(x)=g1(x1)^ g2(x2)^ …^gn(xn)。
题目(来源GCJ2019 1C Bacterial Tactics)
Problem
Becca and Terry are microbiologists who have a friendly rivalry. When they need a break from their research, they like to play a game together. The game is played on a matrix of unit cells with R rows and C columns. Initially, each cell is either empty, or contains radioactive material.
On each player's turn, if there are no empty cells in the matrix, that player loses the game. Otherwise, they choose an empty cell and place a colony of bacteria there. Bacteria colonies come in two types: H (for "horizontal") and V (for "vertical").
When a type H colony is placed into an empty cell, it occupies that cell (making it non-empty), and also tries to spread into the cell immediately to the west (if there is one) and the cell immediately to the east (if there is one).
When a type V colony is placed into an empty cell, it occupies that cell (making it non-empty), and also tries to spread into the cell immediately to the south (if there is one) and the cell immediately to the north (if there is one).
Whenever a colony (of either type) tries to spread into a cell:
If the cell contains radioactive material, the colony mutates and the player who placed the colony loses the game.
If that cell is empty, the colony occupies that cell (making it non-empty), and then the rule above is triggered again (i.e. the colony will try to spread further).
If the cell already contains bacteria (of any type), the colony does not spread into that cell.
Notice that it may be possible that all of a player's available moves would cause them to lose the game, and so they are doomed. See the sample case explanations below for examples of how the game works.
Becca makes the first move, and then the two players alternate moves until one of them loses the game. If both players play optimally, who will win? And, if Becca will win, how many distinct winning opening moves does she have? (Two opening moves are distinct if and only if they either use different cells, or different kinds of colony, or both.)
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing two integers R and C: the number of rows and columns, respectively, in the matrix. Then, there are R more rows of C characters each. The j-th character on the i-th of these lines represents the j-th column of the i-th row of the matrix. Each character is either . (an empty cell) or # (a cell with radioactive material).
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1), and y is an integer: either 0 if Becca will not win, or, if Becca will win, the number of distinct winning opening moves she can make, as described above.
Limits
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
Test set 1 (Visible)
1 ≤ R ≤ 4.
1 ≤ C ≤ 4.
Test set 2 (Hidden)
1 ≤ R ≤ 15.
1 ≤ C ≤ 15.
Sample
Input
5
2 2
..
.#
4 4
.#..
..#.
#...
...#
3 4
#.##
....
#.##
1 1
.
1 2
##
Output
Case #1: 0
Case #2: 0
Case #3: 7
Case #4: 2
Case #5: 0
In Sample Case #1, Becca cannot place an H colony in the southwest empty cell or a V colony in the northeast empty cell, because those would spread onto a radioactive cell and Becca would lose. She has only two possible strategies that do not cause her to lose immediately:
Place an H colony in the northwest or northeast empty cells. The colony will also spread to the other of those two cells.
Place a V colony in the northwest or southwest empty cell. The colony will also spread to the other of those two cells.
If Becca chooses strategy 1, Terry can place a V colony in the southwest empty cell. If Becca chooses strategy 2, Terry can place an H colony in the northeast empty cell. Either way, Becca has no empty cells to choose from on her next turn, so she loses and Terry wins.
In Sample Case #2, any of Becca's opening moves would cause a mutation.
In Sample Case #3, five of Becca's possible opening moves would cause a mutation, but the other seven are winning. She can place an H colony in any of the cells of the second row, or she can place a V colony in any of the cells of the second column. In either case, she leaves two disconnected sets of 1 or 2 cells each. In each of those sets, only one type of colony can be played, and playing it consumes all of the empty cells in that set. So, whichever of those sets Terry chooses to consume, Becca can consume the other, leaving Terry with no moves.
In Sample Case #4, both of Becca's two distinct possible opening moves are winning.
In Sample Case #5, Becca has no possible opening moves.
分析
题目大意是在R×C上的“棋盘”上，B和T轮流放置细菌，细菌有两种，V和H，V会在棋盘上上下去衍生，如果没有阻断最终填满整列，H会在棋盘上左右衍生，如果没有阻断最终填满整行。
这其中有限制，如果细菌衍生过程中会碰到放射性物质“#”，那么就不能放置该细菌。如果遇到其他细菌占领的位置，也不会继续衍生下去。
例如某行状态是...V..#，我在首位放置H，那么会变成HHHV..#然后停止。
最后，B和T谁没有办法放置新的细菌就输掉游戏。
根据题目解释，这个很明显是一个公平游戏，就会用到Sprague-Grundy theory。
解法：
首先，因为细菌只能左右、上下衍生，我们只需要观察某行、某列的放射性位置，来确实是否可以放置细菌。为何后面能快速确定是否可以放置细菌，我们提前记录放射性位置。
比如某行..#..#，我们记录这一行为[0,0,3,3,3,6]，这样当我们棋盘列缩小到4，5的时候，我们是可以放置H的，因为这行的4，5记录的放射元素位置在3，不在4，5列的范围内，是安全的。（当然这个操作不是必须的，你也可以每次去迭代去查询是否安全，对算法耗时影响较小）。
接下来，我们就要按SG定理来确定B先手能否获胜了，我们需要遍历行和列确定可以放置细菌的话，我们判断他分割下来的子棋盘T是否有机会获胜，如果不能获胜（SG(sub1)^SG(sub2) == 0），我们这个位置放置细菌就能赢（SG>1）。
例如样例输入3中：
3 4
#.##
....
#.##
如果我们在第一行第二列放置V，
那么棋盘就分割成左右两个，然后我们就可以迭代解决子问题。
# v ##
. v ..
# v ##
最后，为了能加快迭代效率，我们需要用Mark[20][20][20][20]记录每个子棋盘SG的值，这样就避免重复操作(初始值选-1，这里我开始用0结果超时，因为等于0其实也是有意义的没必要继续迭代)。当B能赢后，只需要再计算一下他可以初始放置的位置个数，这个过程很容易理解就不解释了。
解法代码
// 😊
// main.cpp
// Bacterial Tactics
//
// Created by Jiao Liu on 5/15/19.
// Copyright © 2019 ChangHong. All rights reserved.
//
#include <iostream>
#include <string.h>
#include <set>
using namespace std;
int t,r,c;
char grid[20][20];
int hFlag[20][20], vFlag[20][20], mark[20][20][20][20];
void initG()
{
memset(grid, 0, sizeof(grid));
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin>>grid[i][j];
}
}
}
void initFlag()
{
memset(hFlag, 0, sizeof(hFlag));
memset(vFlag, 0, sizeof(vFlag));
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (grid[i][j] == '.') {
hFlag[i][j] = hFlag[i][j-1];
} else {
hFlag[i][j] = j;
}
}
}
for (int j = 1; j <= c; j++) {
for (int i = 1; i <= r; i++) {
if (grid[i][j] == '.') {
vFlag[i][j] = vFlag[i-1][j];
} else {
vFlag[i][j] = i;
}
}
}
}
int mex(set<int> &t)
{
int a = 0;
while (t.count(a)) {
a++;
}
return a;
}
int solve(int left, int right, int top, int bot)
{
if (left > right || top > bot) {
return 0;
}
if (mark[left][right][top][bot] != -1) {
return mark[left][right][top][bot];
}
set<int> sg = {};
for (int i = top; i <= bot; i++) {
if (hFlag[i][right] < left) {
sg.insert(solve(left, right, top, i-1)^solve(left, right, i+1, bot));
}
}
for (int i = left; i <= right; i++) {
if (vFlag[bot][i] < top) {
sg.insert(solve(left, i-1, top, bot)^solve(i+1, right, top, bot));
}
}
mark[left][right][top][bot] = mex(sg);
return mark[left][right][top][bot];
}
int nMove()
{
int ans = 0;
for (int i = 1; i <= r; i++) {
if (hFlag[i][c] == 0) {
ans += c * ((solve(1, c, 1, i-1)^solve(1, c, i+1, r)) == 0);
}
}
for (int i = 1; i <= c; i++) {
if (vFlag[r][i] == 0) {
ans += r * ((solve(1, i-1, 1, r)^solve(i+1, c, 1, r)) == 0);
}
}
return ans;
}
int main(int argc, const char * argv[]) {
cin>>t;
for (int i = 1; i <= t; i++) {
cin>>r>>c;
initG();
initFlag();
memset(mark, -1, sizeof(mark));
cout<<"Case #"<<i<<": "<<(solve(1, c, 1, r) == 0 ? 0 : nMove())<<endl;
}
return 0;
}
