UVa 601 The PATH

题目描述“PATH\texttt{PATH}PATH” 是一款在N×NN \times NN×N棋盘上进行的双人游戏NNN为正整数。棋盘使用字符矩阵表示其中W表示白棋B表示黑棋U表示空格。白棋的目标是从棋盘左边缘第一列到右边缘最后一列形成一条连续的路径黑棋的目标是从棋盘上边缘第一行到下边缘最后一行形成一条连续的路径。两个位置相邻当且仅当它们上下左右紧邻。一条路径由若干个相邻的己方棋子组成且路径中位置互不相同。如果一方已经形成获胜路径则另一方不可能同时获胜因为路径会互相阻断。当所有格子均被棋子填满时要么没有获胜路径要么恰好一方存在获胜路径。本题中你扮演裁判需要根据给定的棋盘局面判断当前胜负情况以及白方下一步能否一步获胜或者黑方能否一步获胜前提是白方不能一步获胜。输入格式输入包含多组数据。每组数据第一行为一个整数NNN0N810 N 810N81表示棋盘大小。接下来有一个空行然后连续NNN行每行包含NNN个字符B、W、U表示从顶行到底行的棋盘状态。每组数据后有一个空行分隔。输入以一行单独一个0结束。输出格式对于每组棋盘输出以下五种可能结果之一按优先级顺序White has a winning path.Black has a winning path.White can win in one move.Black can win in one move.There is no winning path.输出优先级如下若当前棋盘已有白方获胜路径则输出第一项否则若已有黑方获胜路径输出第二项否则若白方可以通过放置一枚白棋在某个空格上形成获胜路径则输出第三项否则若黑方可以通过放置一枚黑棋在某个空格上形成获胜路径则输出第四项否则输出第五项。样例输入7 WBBUUUU WBUWWW UWBBBWB BBWBWB BBWBWB UBWwBU UBBBW 3 WBB WWU WBB 0输出White has a winning path. White can win in one move.题目分析游戏的核心是判断是否存在从指定边缘到对边的、由同色棋子组成的四连通路径。棋盘规模最大为80×8080 \times 8080×80棋子数最多640064006400使用深度优先搜索DFS\texttt{DFS}DFS即可在O(N2)O(N^2)O(N2)时间内判断任一方是否已有获胜路径。本题的难点在于“一步获胜”的判断白方下一步可以放置一枚白棋在任意空格U上然后判断是否存在白方获胜路径黑方同理。由于NNN最大为808080空格数量最多640064006400若对每个空格都执行一次完整的DFS\texttt{DFS}DFS最坏情况为6400×6400≈4×1076400 \times 6400 \approx 4 \times 10^76400×6400≈4×107次操作仍然可行实际代码在UVa OJ\texttt{UVa OJ}UVa OJ上运行时间为0.0000.0000.000秒。但需要注意判断黑方一步获胜时必须确保白方不能一步获胜这与输出规则一致。此外题目保证如果当前局面有一方已有获胜路径则另一方不可能同时获胜因此检查顺序可以按优先级依次进行。解题思路存储棋盘使用二维字符数组grid[90][90]存储原始棋盘field[90][90]作为副本供搜索修改。判断白方获胜函数checkW复制原始棋盘到field。遍历第一列白方若某个位置为W则从该位置开始执行DFS\texttt{DFS}DFS将所有连通的W标记为1。检查最后一列是否存在标记为1的位置若存在则白方获胜。判断黑方获胜函数checkB复制原始棋盘到field。遍历第一行黑方 home edge若某个位置为B则执行DFS\texttt{DFS}DFS将所有连通的B标记为1。检查最后一行是否存在标记为1的位置若存在则黑方获胜。主判断流程函数check先判断当前是否有白方获胜路径若有则输出对应结果并返回。再判断当前是否有黑方获胜路径若有则输出对应结果并返回。然后枚举所有空格尝试在该位置放置白棋调用checkW判断是否白方一步获胜。若找到任意一个空格放置白棋后白方获胜则输出White can win in one move.并返回。若白方不能一步获胜再枚举所有空格尝试放置黑棋调用checkB判断是否黑方一步获胜。若存在则输出Black can win in one move.并返回。若以上均不满足则输出There is no winning path.。注意事项每次调用checkW或checkB前必须使用duplicate()将原始棋盘复制到field避免修改原始数据。DFS\texttt{DFS}DFS采用递归实现由于棋盘最大80×8080 \times 8080×80递归深度最多640064006400在C\texttt{C}C中不会栈溢出。复杂度分析判断一方是否已有获胜路径DFS\texttt{DFS}DFS遍历所有同色连通块时间复杂度O(N2)O(N^2)O(N2)。一步获胜判断枚举所有空格每次复制棋盘并执行一次DFS\texttt{DFS}DFS时间复杂度O(N2⋅N2)O(N4)O(N^2 \cdot N^2) O(N^4)O(N2⋅N2)O(N4)。当N80N 80N80时8044.096×10780^4 4.096 \times 10^78044.096×107在合理范围内。空间复杂度O(N2)O(N^2)O(N2)用于存储棋盘和递归栈。代码实现// The PATH// UVa ID: 601// Verdict: Accepted// Submission Date: 2016-08-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[90][90],field[90][90];intn;voidduplicate(){for(inti0;in;i)for(intj0;jn;j)field[i][j]grid[i][j];}voidfillW(inti,intj){if(i0inj0jnfield[i][j]W){field[i][j]1;fillW(i1,j);fillW(i-1,j);fillW(i,j1);fillW(i,j-1);}}voidfillB(inti,intj){if(i0inj0jnfield[i][j]B){field[i][j]1;fillB(i1,j);fillB(i-1,j);fillB(i,j1);fillB(i,j-1);}}boolcheckW(){// White has a winning path.booledgedfalse;for(inti0;in;i)if(field[i][0]W){edgedtrue;fillW(i,0);}if(edged)for(inti0;in;i)if(field[i][n-1]1)returntrue;returnfalse;}boolcheckB(){// Black has a winning path.booledgedfalse;for(inti0;in;i)if(field[0][i]B){edgedtrue;fillB(0,i);}if(edged)for(inti0;in;i)if(field[n-1][i]1)returntrue;returnfalse;}voidcheck(){duplicate();if(checkW()){coutWhite has a winning path.\n;return;}duplicate();if(checkB()){coutBlack has a winning path.\n;return;}// White can win in one move.for(inti0;in;i)for(intj0;jn;j)if(grid[i][j]U){duplicate();field[i][j]W;if(checkW()){coutWhite can win in one move.\n;return;}}// Black can win in one move.for(inti0;in;i)for(intj0;jn;j)if(grid[i][j]U){duplicate();field[i][j]B;if(checkB()){coutBlack can win in one move.\n;return;}}coutThere is no winning path.\n;}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][j];check();}return0;}总结本题是一道典型的连通性判断问题通过DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS即可高效解决。关键点在于明确白方和黑方的目标边缘方向白左→右黑上→下。一步获胜判断需要枚举所有空格并在复制棋盘上尝试落子不能修改原棋盘。注意输出优先级先判断已有路径再判断白方一步获胜最后判断黑方一步获胜。由于棋盘较小O(N4)O(N^4)O(N4)的枚举在N≤80N \le 80N≤80时仍可接受代码简洁且易于实现。本题也提示我们当问题规模不大时暴力枚举结合连通性检查是可行的若NNN进一步增大则可能需要更高效的动态连通性维护或并查集优化。