棋局建模例题(2)-AcWing1324. 五子棋

出处

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 子连珠的可能区域，避免无效计算。

  1. 优化点
  • 每一步只检查当前落子点周围可能形成的五子连珠，可以进一步优化性能，但当前算法对于 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;
}

留下评论

您的邮箱地址不会被公开。 必填项已用 * 标注