[语言月赛202306] 棋 题解
Source & Knowledge
2023 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。
题目大意
给你一张五子棋的棋盘，请你判断其棋局：判断谁获胜，或判断轮到谁落子。
题目分析
本题考察字符串的处理及代码实现能力。
首先，判断谁先下比较简单，只需记录 * 和 $ 的数量，如果相等，则说明一个回合恰好结束，应该轮到先手即「她」落子。反之，* 的数量等于 $ 的数量加一，应该轮到后手即 zyl 落子。
接下来就是麻烦的部分了：判断胜方。可以观察到，数据范围非常小，我们可以枚举每一个位置。这样，如果存在五子相连，我们肯定会找到它的端点。这样就能得到最朴素的做法：枚举每一个位置，如果枚举到的位置有棋子，则判断八个方向是否存在与当前位置相同的连续五个棋子。如果有就输出胜方，并直接结束程序。
然而，这样要写一大堆的判断语句，即不美观，也不方便，容易出错。接下来就是一些优化代码的方案。
首先，我们可以思考，看起来我们要找整整八个方向，但事实上，方向只有四个——上-下方向，左-右方向，左下-右上方向，左上-右下方向（自己画一画试一试）。我们只考虑靠左的端点（上-下方向中靠下）的端点，也能保证不会出错，这样的话，代码量少了一半。这种优化的核心代码如下：
char c[35][35];
for(int i=1;i<=n;i++)cin >>(c[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(c[i][j]=='~')continue;
l+=c[i][j]=='*',r+=c[i][j]=='$';
if(j<=m-4){
if(c[i][j]==c[i][j+1]&&c[i][j]==c[i][j+2]&&c[i][j]==c[i][j+3]&&c[i][j]==c[i][j+4]){//这是左-右方向
if(c[i][j]=='*')cout <<"Pleasing!";
else cout <<"zylwins!";
return 0;
}
if(i>=5){
if(c[i][j]==c[i-1][j+1]&&c[i][j]==c[i-2][j+2]&&c[i][j]==c[i-3][j+3]&&c[i][j]==c[i-4][j+4]){//这是左下-右上方向
if(c[i][j]=='*')cout <<"Pleasing!";
else cout <<"zylwins!";
return 0;
}
}
if(i<=n-4){
if(c[i][j]==c[i+1][j+1]&&c[i][j]==c[i+2][j+2]&&c[i][j]==c[i+3][j+3]&&c[i][j]==c[i+4][j+4]){//这是左上-右下方向
if(c[i][j]=='*')cout <<"Pleasing!";
else cout <<"zylwins!";
return 0;
}
}
}
if(i>=5){
if(c[i][j]==c[i-1][j]&&c[i][j]==c[i-2][j]&&c[i][j]==c[i-3][j]&&c[i][j]==c[i-4][j]){//这是上-下方向
if(c[i][j]=='*')cout <<"Pleasing!";
else cout <<"zylwins!";
return 0;
}
}
}
if(l==r)cout <<"W";//数量相同，输出先手
else cout <<"Z";
不过，这样的代码依旧冗长，也容易出错，想一想有没有更好的优化方案呢？
当然是有的。首先，四个方向是我们不得不寻找的，不能减少方向，否则会出错。那么不如从这四个方向来分析。可以观察到，在一个方向上，连续的棋子的坐标之间的差值是固定的。我们可以轻松地找出这些差值。
拿左-右方向举例：设当前的坐标为
这样的话，我们可以开两个数组 dx 和 dy 分别存储每个方向相邻棋子对应的横、纵坐标的差值。判断胜负时，我们每次将坐标加上这两个差值，看新坐标的棋子是否和原坐标上的棋子一样，重复 4 遍。这些就可以用循环来处理了，冗长的代码就变的非常简短。这就是数组和循环语句的好处了：将重复的工作合并，优化代码，这种优化的核心代码如下：
const int dx[4]={0,*,*,*};//*的部分自己推导试一试
const int dy[4]={1,*,*,*};//*的部分自己推导试一试
int l,r;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(c[i][j] == '~')continue;
l += c[i][j]=='*',r += c[i][j]=='#';
for(int k = 0;k < 4;k++){//枚举四个方向
int x = i,y = j;
bool f = 1;//判断这个方向有没有连续五个相同棋子，先默认有
for(int d = 1;d <= 4;d++){
x += dx[k],y += dy[k];
if(x<1||y<1||x>n||y>m){
f=0;
break;
}//小心越界
if(c[x][y] != c[i][j]){
f = 0;
break;
}
}
if(f){//找到了胜方
if(c[i][j]=='*')cout <<"Pleasing!";
else cout <<"zylwins!";
return 0;
}
}
}
}