自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 21:15:00，当前版本为作者最后更新于2023-06-08 20:06:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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";	

不过，这样的代码依旧冗长，也容易出错，想一想有没有更好的优化方案呢？

当然是有的。首先，四个方向是我们不得不寻找的，不能减少方向，否则会出错。那么不如从这四个方向来分析。可以观察到，在一个方向上，连续的棋子的坐标之间的差值是固定的。我们可以轻松地找出这些差值。

拿左-右方向举例：设当前的坐标为 $(i,j)$，则从左往右的坐标分别是 $(i,j+1),(i,j+2),(i,j+3),(i,j+4)$。相邻两个坐标的横坐标之差为 0，纵坐标之差为 1。其它三个方向大家可以自己动手比划。

这样的话，我们可以开两个数组 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;
			} 
		}		
	}
} 

视频讲解