题目描述在国际象棋中车可以沿水平或垂直方向移动任意步数。本题考虑不超过4×44 \times 44×4的小棋盘棋盘上可能包含墙用X表示墙可以阻挡车的攻击。要求放置尽可能多的车使得任意两车不在同一行或同一列除非它们之间至少有一堵墙相隔。给定一个棋盘布局计算最多能放置的车数。输入格式输入包含一个或多个棋盘描述每行一个正整数nnnn≤4n \le 4n≤4表示棋盘大小随后nnn行每行nnn个字符.表示空位X表示墙。输入以单独一行0结束。输出格式对于每个测试用例输出一行整数表示最多能放置的车数。样例输入4 .X.. .... XX.. .... 2 XX .X 3 .X. X.X .X. 3 ... .XX .XX 4 .... .... .... .... 0输出5 1 5 2 4题目分析棋盘大小n≤4n \le 4n≤4总格子数最多161616因此可以用回溯法DFS\texttt{DFS}DFS枚举所有可能的放置方案。每个空格有两种状态放车或不放车。在搜索过程中每放置一个车后立即检查当前棋盘是否合法即任意两车是否相互攻击若不合法则剪枝。由于nnn很小即使不剪枝也能在极短时间内完成。合法性检查对于每个已放置的车分别向上、下、左、右四个方向扫描若遇到另一个车且中间没有墙则非法若遇到墙则停止该方向扫描。解题思路将棋盘展平为一维数组grid方便按位置索引。定义check()函数复制当前棋盘到backup遍历所有格子若该格子为r表示放置了车则调用floodFill(position)检查四个方向是否有其他车未被墙隔开。若发现冲突返回false否则true。定义backtrack(position, rooks)参数position表示当前考虑到的格子索引用于避免重复组合rooks为当前已放车数。更新全局最优解max_rooks max(max_rooks, rooks)。从position到n×n−1n \times n - 1n×n−1枚举下一个尝试放置车的位置i。若grid[i] .则临时将其改为r然后调用check()检查合法性。若合法则递归调用backtrack(i 1, rooks 1)。回溯恢复grid[i] .。主函数读入每组数据初始化max_rooks 0调用backtrack(0, 0)输出结果。复杂度分析状态空间为2n22^{n^2}2n2n≤4n \le 4n≤4最多216655362^{16} 6553621665536种每次检查复杂度O(n2)O(n^2)O(n2)总时间很小。空间复杂度O(n2)O(n^2)O(n2)。代码实现// Dont Get Rooked// UVa ID: 639// Verdict: Accepted// Submission Date: 2016-08-25// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[20],backup[20];intn,max_rooks;boolfloodFill(intposition){intiposition/n,jposition%n;for(intnext_ii1;next_in;next_i)if(backup[next_i*nj]r)returnfalse;elseif(backup[next_i*nj]X)break;for(intnext_ii-1;next_i0;next_i--)if(backup[next_i*nj]r)returnfalse;elseif(backup[next_i*nj]X)break;for(intnext_jj1;next_jn;next_j)if(backup[i*nnext_j]r)returnfalse;elseif(backup[i*nnext_j]X)break;for(intnext_jj-1;next_j0;next_j--)if(backup[i*nnext_j]r)returnfalse;elseif(backup[i*nnext_j]X)break;returntrue;}boolcheck(){copy(grid,grid20,backup);for(inti0;in*n;i)if(backup[i]r!floodFill(i))returnfalse;returntrue;}voidbacktrack(intposition,introoks){max_rooksmax(max_rooks,rooks);for(intiposition;in*n;i){if(grid[i].){grid[i]r;if(check())backtrack(position1,rooks1);grid[i].;}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinn,n){for(inti0;in;i)for(intj0;jn;j)cingrid[i*nj];max_rooks0;backtrack(0,0);coutmax_rooks\n;}return0;}总结本题通过回溯法枚举所有可能的放置方案并利用墙阻挡攻击的特性进行合法性检查。由于棋盘规模极小暴力搜索完全可行。关键点在于正确实现方向扫描和冲突检测以及利用剪枝放置后立即检查减少无效搜索。该解法清晰易懂适用于n≤4n \le 4n≤4的小规模棋盘问题。若棋盘增大则需考虑更高效的算法如二分图匹配但本题无需。