UVa 601 The PATH-洪萨配资

题目描述

“PATH\texttt{PATH}PATH” 是一款在N×NN \times NN×N棋盘上进行的双人游戏（NNN为正整数）。棋盘使用字符矩阵表示，其中W表示白棋，B表示黑棋，U表示空格。白棋的目标是从棋盘左边缘（第一列）到右边缘（最后一列）形成一条连续的路径，黑棋的目标是从棋盘上边缘（第一行）到下边缘（最后一行）形成一条连续的路径。两个位置相邻当且仅当它们上下左右紧邻。一条路径由若干个相邻的己方棋子组成，且路径中位置互不相同。如果一方已经形成获胜路径，则另一方不可能同时获胜（因为路径会互相阻断）。当所有格子均被棋子填满时，要么没有获胜路径，要么恰好一方存在获胜路径。

本题中，你扮演裁判，需要根据给定的棋盘局面，判断当前胜负情况，以及白方下一步能否一步获胜，或者黑方能否一步获胜（前提是白方不能一步获胜）。

输入格式

输入包含多组数据。每组数据第一行为一个整数NNN（0<N<810 < N < 810<N<81），表示棋盘大小。接下来有一个空行，然后连续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)。当N=80N = 80N=80时，804=4.096×10780^4 = 4.096 \times 10^7804=4.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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;chargrid[90][90],field[90][90];intn;voidduplicate(){for(inti=0;i<n;i++)for(intj=0;j<n;j++)field[i][j]=grid[i][j];}voidfillW(inti,intj){if(i>=0&&i<n&&j>=0&&j<n&&field[i][j]=='W'){field[i][j]='1';fillW(i+1,j);fillW(i-1,j);fillW(i,j+1);fillW(i,j-1);}}voidfillB(inti,intj){if(i>=0&&i<n&&j>=0&&j<n&&field[i][j]=='B'){field[i][j]='1';fillB(i+1,j);fillB(i-1,j);fillB(i,j+1);fillB(i,j-1);}}boolcheckW(){// White has a winning path.booledged=false;for(inti=0;i<n;i++)if(field[i][0]=='W'){edged=true;fillW(i,0);}if(edged)for(inti=0;i<n;i++)if(field[i][n-1]=='1')returntrue;returnfalse;}boolcheckB(){// Black has a winning path.booledged=false;for(inti=0;i<n;i++)if(field[0][i]=='B'){edged=true;fillB(0,i);}if(edged)for(inti=0;i<n;i++)if(field[n-1][i]=='1')returntrue;returnfalse;}voidcheck(){duplicate();if(checkW()){cout<<"White has a winning path.\n";return;}duplicate();if(checkB()){cout<<"Black has a winning path.\n";return;}// White can win in one move.for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(grid[i][j]=='U'){duplicate();field[i][j]='W';if(checkW()){cout<<"White can win in one move.\n";return;}}// Black can win in one move.for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(grid[i][j]=='U'){duplicate();field[i][j]='B';if(checkB()){cout<<"Black can win in one move.\n";return;}}cout<<"There is no winning path.\n";}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cin>>n,n){for(inti=0;i<n;i++)for(intj=0;j<n;j++)cin>>grid[i][j];check();}return0;}