出处
AcWing1324. 五子棋：https://www.acwing.com/problem/content/1326
题目描述
小 A 和小 B 在下五子棋。
五子棋是在一个由网格构成的棋盘内进行的。
网格有 15 行 15 列，共有 225 个交叉点。
小 A 先手执黑棋，小 B 后手执白棋。
两人轮流下棋，每次下棋都将一个自己的棋子放在棋盘上一个空白的交叉点上。
然而，由于小 A 和小 B 都不知道五子棋的胜利条件，所以即使有一方已经胜利了，他们仍然会继续下棋。
现在想请你帮忙分析一下，所下的棋局是在第几步结束的。
当然，也有可能他们最终仍然没有分出胜负，这时请判定他们平局。
五子棋的胜利条件是这样的：当同一行或同一列或同一斜线（即与网格线成 45° 角的直线）上连续的五个或五个以上交叉点放有同色棋子的时候，立即判定使用该颜色棋子的玩家获得胜利，游戏结束。
输入格式
第一行输入一个正整数 n，表示双方总共下了多少步棋。
接下来 n 行，每行两个正整数。其中，第 i 行的两个数 x,y 表示第 i 步的棋子下在了第 x 条横线和第 y 条竖线的交叉点上。若 i 为奇数，则这个棋子是黑棋，否则是白棋。
输出格式
若没有人获得胜利，你需要输出“Tie”（不含引号）。
否则，若小 A 获胜，输出 “A”（不含引号），若小 B 获胜，输出 “B”（不含引号）；并输出一个正整数 w 表示第 w 步下完后游戏应当结束，字母与整数间用一个空格隔开。
数据范围
对于 20% 的数据，游戏结果是平局。
对于 30% 的数据，游戏在最后一手结束。
对于 100% 的数据，0≤n≤225，1≤x,y≤15。
输入样例
9
1 1
2 1
1 2
2 2
1 3
2 3
1 4
2 4
1 5
输出样例
A 9题解（模拟法）
1. 数据结构
- 使用一个二维数组
board[15][15]表示棋盘，初始值全为0，表示空位。1代表小 A（黑棋）-1代表小 B（白棋）
2. 模拟下棋过程
- 依次读取每一步的坐标，并根据当前步骤的奇偶性决定是黑棋还是白棋，将其放入棋盘对应位置。
- 每次落子后，调用
checkWin()函数检测当前棋盘是否有玩家获胜。 - 若检测到获胜方，立刻输出结果并结束程序。
- 若所有步骤都执行完且无人获胜，则输出
Tie。
3. 胜负判断函数 checkWin()
- 分别检查 行、列、主对角线、副对角线 四个方向上是否有连续 5 个或以上的相同棋子。
- 行的检查：遍历每一行，统计连续相同棋子的个数，达到 5 则返回当前棋子所属玩家。
- 列的检查：遍历每一列，同理统计。
- 主对角线（左上到右下）：遍历棋盘左上部分的 11×11 区域（因为再往右下就超出棋盘了），以每个点为起点，向右下检查是否有连续 5 个相同棋子。
- 副对角线（右上到左下）：遍历棋盘右上部分的区域，从第 0~10 行 和 第 4~14 列开始，向左下检查是否有连续 5 个相同棋子。
⚠️注意：为了提高效率，我们在每个方向上只检查能够形成 5 子连珠的可能区域，避免无效计算。
- 优化点
- 每一步只检查当前落子点周围可能形成的五子连珠，可以进一步优化性能，但当前算法对于
n <= 225的数据规模已经足够高效。
代码逐段解析
主函数 main
int main() {
int n;
scanf("%d", &n); // 总步数
for (int i = 1; i <= n; i++) { // 遍历每一步
int x, y;
scanf("%d %d", &x, &y); // 读取落子坐标
// 确定当前是 A (奇数，1) 还是 B (偶数，-1)
int player = i % 2 ? 1 : -1;
// 坐标转换为 0-based
put(x - 1, y - 1, player);
// 检查是否有人获胜
int winPlayer = checkWin();
if (winPlayer == 1) {
printf("A %d\n", i); // A 获胜，输出 A 和当前步数
exit(0);
} else if (winPlayer == -1) {
printf("B %d\n", i); // B 获胜，输出 B 和当前步数
exit(0);
}
}
// 所有步数走完无人获胜
printf("Tie\n");
return 0;
}落子函数 put
void put(int x, int y, int player) {
board[x][y] = player; // 直接在棋盘对应位置记录棋子
}胜负判断函数 checkWin
这是核心部分，用于检测是否有五子连珠：
int checkWin() {
// 检查每一行
for (int i = 0; i < 15; i++) {
int cnt = 1;
for (int j = 1; j < 15; j++) {
if (board[i][j] != 0 && board[i][j] == board[i][j - 1]) {
cnt++;
if (cnt == 5) {
return board[i][j]; // 返回当前玩家：1 or -1
}
} else {
cnt = 1;
}
}
}- 遍历每一行，从第 1 列开始与前一个比较，统计连续相同棋子数量，达到 5 则返回该棋子所属玩家。
// 检查每一列
for (int j = 0; j < 15; j++) {
int cnt = 1;
for (int i = 1; i < 15; i++) {
if (board[i][j] != 0 && board[i][j] == board[i - 1][j]) {
cnt++;
if (cnt == 5) {
return board[i][j];
}
} else {
cnt = 1;
}
}
}- 同理于行，但是逐列检查。
// 检查主对角线（左上到右下）
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (board[i][j] != 0) {
int win = 1;
for (int k = 1; k < 5; k++) {
if (board[i][j] != board[i + k][j + k]) {
win = 0;
break;
}
}
if (win) {
return board[i][j];
}
}
}
}- 遍历棋盘左上角 11×11 的区域（因为再往右下会越界），以每个点为起点，向右下方检查是否有连续 5 个相同棋子。
// 检查副对角线（右上到左下）
for (int i = 0; i < 11; i++) {
for (int j = 4; j < 15; j++) {
if (board[i][j] != 0) {
int win = 1;
for (int k = 1; k < 5; k++) {
if (board[i][j] != board[i + k][j - k]) {
win = 0;
break;
}
}
if (win) {
return board[i][j];
}
}
}
}- 遍历从第 0~10 行，第 4~14 列开始的点，向左下方检查是否有连续 5 个相同棋子。
🎯为什么 j 从 4 开始？因为要保证
j - k >= 0，即不越界。
return 0; // 没有获胜方
}示例分析（输入样例）
9
1 1
2 1
1 2
2 2
1 3
2 3
1 4
2 4
1 5- 小 A 按如下顺序落子：(1,1), (1,2), (1,3), (1,4), (1,5) → 形成一行 5 个黑棋。
- 在第 9 步时，检测到横行五连，因此输出
A 9。
复杂度分析
- 时间复杂度：每一步判断胜负的复杂度为 O(15×15) = O(225)，最坏情况下进行 225 步，总体是 O(225×225) = O(50625)，对于题目数据范围完全可接受。
- 空间复杂度：O(15×15) = O(225)，即棋盘大小。
C语言实现
#include <stdio.h>
#include <stdlib.h>
int board[15][15]; // 0（空），1（小A），-1（小B）
void put(int x, int y, int player); // 落子
int checkWin(); // 判断是否为终局，返回获胜方
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
int y;
scanf("%d %d", &x, &y);
// i 奇数是 小A 落子，偶数是 小B 落子
int player = i % 2 ? 1 : -1;
put(x - 1, y - 1, player);
int winPlayer = checkWin();
if (winPlayer == 1) {
printf("A %d\n", i);
exit(0);
} else if (winPlayer == -1) {
printf("B %d\n", i);
exit(0);
}
}
printf("Tie\n");
return 0;
}
// 落子
void put(int x, int y, int player) {
board[x][y] = player;
}
// 判断是否某一方获胜，若有一方获胜则返回获胜方，否则返回 0
int checkWin() {
// 检查每一行
for (int i = 0; i < 15; i++) {
int cnt = 1;
for (int j = 1; j < 15; j++) {
if (board[i][j] != 0 && board[i][j] == board[i][j - 1]) {
cnt++;
if (cnt == 5) {
return board[i][j];
}
} else {
cnt = 1;
}
}
}
// 检查每一列
for (int j = 0; j < 15; j++) {
int cnt = 1;
for (int i = 1; i < 15; i++) {
if (board[i][j] != 0 && board[i][j] == board[i - 1][j]) {
cnt++;
if (cnt == 5) {
return board[i][j];
}
} else {
cnt = 1;
}
}
}
// 检查主对角线（左上到右下）
for (int i = 0; i < 11; i++) { // 只需要检查到第10行
for (int j = 0; j < 11; j++) { // 只需要检查到第10列
if (board[i][j] != 0) {
int win = 1; // 1-赢，0-没赢
for (int k = 1; k < 5; k++) {
if (board[i][j] != board[i + k][j + k]) {
win = 0;
break;
}
}
if (win) {
return board[i][j];
}
}
}
}
// 检查副对角线（右上到左下）
for (int i = 0; i < 11; i++) { // 只需要检查到第10行
for (int j = 4; j < 15; j++) { // 从第4列开始检查
if (board[i][j] != 0) {
int win = 1; // 1-赢，0-没赢
for (int k = 1; k < 5; k++) {
if (board[i][j] != board[i + k][j - k]) {
win = 0;
break;
}
}
if (win) {
return board[i][j];
}
}
}
}
return 0;
}社团成员解法
模拟：https://www.codecopy.cn/post/xj6m6b（作者：chuali）
#include<iostream>
using namespace std;
int qipan[15][15];//这是棋盘
bool checkwin(int x, int y);
int main() {
int n;
cin >> n;
bool truewins = 0;
bool switch1 = 0;//0的时候a下，1的时候b下
int cnt = 0;
for (int i = 0; i < n; i++) {
int x;
int y;
cin >> x >> y;
x--;//非常重要！！！！！！！！！
y--;//重要！！！！！！！！！！！！！！！！
if (x < 0 || x >= 15 || y < 0 || y >= 15 || qipan[x][y] != 0) {
continue;
}//这个是我以为数据会下无效棋（其实就是查bug查急眼了瞎写的
if (!switch1) {
qipan[x][y] = 1;
cnt++;
switch1 = 1;
}
else {
qipan[x][y] = -1;
cnt++;
switch1 = 0;
}
if (checkwin(x, y)) {
if (qipan[x][y] == 1) {
cout << "A" << " " << cnt << endl;
return 0;
}
else {
cout << "B" << " " << cnt << endl;
return 0;
}
}
}
cout << "Tie"<< endl;
return 0;
}
bool checkwin(int x, int y) {
int direc[4][2] = { {1,1},{1,0},{0,1},{1,-1} };
int player = qipan[x][y];
for (int i = 0; i < 4; i++) {
int dx = direc[i][0];
int dy = direc[i][1];
int count1 = 1;
for (int j = 1; j <= 4; j++) {
int nx = x + dx * j;
int ny = y + dy * j;
if (nx < 0 || nx>14 || ny < 0 || ny>14 || qipan[nx][ny] != player) {
break;
}
count1++;
}
for (int j = 1; j <= 4; j++) {
int nx = x - dx * j;
int ny = y - dy * j;
if (nx < 0 || nx>14 || ny < 0 || ny>14 || qipan[nx][ny] != player) {
break;
}
count1++;
}
if (count1 >= 5) {
return 1;
}
}
return 0;
}