题单练习 深度优先搜索

A6274 | 五子棋对弈

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

“在五子棋的对弈中,友谊的小船说翻就翻?” 并不一定。

对于 Welcome24ever 和 fangz 来说,五子棋不仅是棋盘上的较量,更是心与心之间的沟通。这两位挚友秉承着 “友谊第一,比赛第二” 的宗旨,决定在一块 $5 \times 5$ 的棋盘上,用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落,于是决定用一场 和棋(平局) 作为彼此友谊的见证。

比赛遵循以下规则:

1. 棋盘规模
比赛在一个 $5 \times 5$ 的方格棋盘上进行,共有 $25$ 个格子供下棋使用。

2. 棋子类型
有两种棋子:黑棋与白棋。约定 Welcome24ever 持白棋,fangz 持黑棋。

3. 先手规则
白棋(Welcome24ever)先手,即在棋盘完全为空时,率先落子。

4. 轮流落子
两位玩家轮流在棋盘的空格上放置各自颜色的棋子:
- 每回合只能在一个空格中落下一枚棋子;
- 不允许在已经有棋子的格子上重复落子。

5. 胜利条件
若某一方在棋盘上率先在 横向、纵向或斜向 的某一条直线上形成 连续 5 个同色棋子,则该方立即获胜,对局结束。

6. 平局条件
当棋盘上 $25$ 个格子全部被棋子占满,且双方都没有在任意一条直线上形成连续 5 子,则对局结果为平局(和棋)。

---

在上述规则下,Welcome24ever 和 fangz 想知道:

有多少种 不同的终局棋局 满足:

  • 棋盘已经完全下满(即 $25$ 个格子全部被棋子占据);
  • 对局结果为 平局(没有任何一方出现连续 5 子的获胜局面);
  • 只看最终局面,不区分落子顺序
- 如果两个对局的最终棋盘布置在每一个格子上的棋子颜色都完全相同,则视为同一种棋局情况
- 如果存在至少一个格子上棋子的颜色不同,则视为不同的棋局情况

请你计算满足条件的、不同终局棋局的总数。

输入格式

你只需要根据题意自行分析、计算出最终结果。

输出格式

请输出一个整数,表示在 $5 \times 5$ 棋盘上,棋盘下满且对局为平局的 不同终局棋局数目

提交答案时,只需填写这个整数本身,不能附加多余的符号、空格或说明文字。
C++ 编辑器
输入
输出