前言
The Sprague-Grundy theory是博弈論中解決公平游戲的一個(gè)重要定理。這里不對(duì)定理進(jìn)行展開解釋與證明，有興趣的可以去看一下百度上Nim游戲對(duì)于定理的運(yùn)用，也可以在下面解題中體會(huì)其中原理，這里直接給出定理：
Sprague-Grundy定理：
設(shè)gi為一個(gè)游戲Gi的Sprague-Grundy函數(shù)，則組合游戲G=G1+G2+…+Gn的Sprague-Grundy函數(shù)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輪流放置細(xì)菌，細(xì)菌有兩種，V和H，V會(huì)在棋盤上上下去衍生，如果沒有阻斷最終填滿整列，H會(huì)在棋盤上左右衍生，如果沒有阻斷最終填滿整行。
這其中有限制，如果細(xì)菌衍生過程中會(huì)碰到放射性物質(zhì)“#”，那么就不能放置該細(xì)菌。如果遇到其他細(xì)菌占領(lǐng)的位置，也不會(huì)繼續(xù)衍生下去。
例如某行狀態(tài)是...V..#，我在首位放置H，那么會(huì)變成HHHV..#然后停止。
最后，B和T誰沒有辦法放置新的細(xì)菌就輸?shù)粲螒颉?br> 根據(jù)題目解釋，這個(gè)很明顯是一個(gè)公平游戲，就會(huì)用到Sprague-Grundy theory。
解法：
首先，因?yàn)榧?xì)菌只能左右、上下衍生，我們只需要觀察某行、某列的放射性位置，來確實(shí)是否可以放置細(xì)菌。為何后面能快速確定是否可以放置細(xì)菌，我們提前記錄放射性位置。
比如某行..#..#，我們記錄這一行為[0,0,3,3,3,6]，這樣當(dāng)我們棋盤列縮小到4，5的時(shí)候，我們是可以放置H的，因?yàn)檫@行的4，5記錄的放射元素位置在3，不在4，5列的范圍內(nèi)，是安全的。（當(dāng)然這個(gè)操作不是必須的，你也可以每次去迭代去查詢是否安全，對(duì)算法耗時(shí)影響較?。?。
接下來，我們就要按SG定理來確定B先手能否獲勝了，我們需要遍歷行和列確定可以放置細(xì)菌的話，我們判斷他分割下來的子棋盤T是否有機(jī)會(huì)獲勝，如果不能獲勝（SG(sub1)^SG(sub2) == 0），我們這個(gè)位置放置細(xì)菌就能贏（SG>1）。
例如樣例輸入3中：
3 4
#.##
....
#.##
如果我們?cè)诘谝恍械诙蟹胖肰，
那么棋盤就分割成左右兩個(gè)，然后我們就可以迭代解決子問題。
# v ##
. v ..
# v ##
最后，為了能加快迭代效率，我們需要用Mark[20][20][20][20]記錄每個(gè)子棋盤SG的值，這樣就避免重復(fù)操作(初始值選-1，這里我開始用0結(jié)果超時(shí)，因?yàn)榈扔?其實(shí)也是有意義的沒必要繼續(xù)迭代)。當(dāng)B能贏后，只需要再計(jì)算一下他可以初始放置的位置個(gè)數(shù)，這個(gè)過程很容易理解就不解釋了。
解法代碼
// ??
// 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;
}
