当前位置：首页 > backend >正文

【数据结构入门训练DAY-35】棋盘问题

backend 2025/5/16 7:15:14

本次训练聚焦于使用深度优先搜索（DFS）算法解决棋盘上的棋子摆放问题。题目要求在一个可能不规则的n×n棋盘上摆放k个棋子，且任意两个棋子不能位于同一行或同一列。输入包括棋盘大小n和棋子数k，以及棋盘的形状（用#表示可放置区域，.表示空白）。输出为所有可行的摆放方案数C。解题思路是通过DFS遍历棋盘，标记已放置棋子的行和列，递归寻找所有可能的摆放方案，并在回溯时恢复标记。代码实现中，使用二维数组表示棋盘，并通过两个一维数组标记行和列的状态。训练强调了编码习惯的养成和解题思维的训练，为后续学习广度优先搜索（BFS）算法打下基础。

文章目录

前言
一、题目
二、解题思路
总结

前言

本次训练内容

训练DFS处理棋盘问题。
对编码习惯的养成。
训练解题思维。

一、题目

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案 C。

输入格式

输入含有多组测试数据。
每组数据的第一行是两个正整数n,k，用一个空格隔开，表示了将在一个n×n的矩阵内描述棋盘，以及摆放棋子的数目。 (n≤8,k≤n)
当为−1−1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域，. 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目C（数据保证C<231）。

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

二、解题思路

今天的题目是一道基础的DFS题，题目就是让我遍历棋盘，找到可以放置棋子的位置并放置对应的棋子，这步倒好做，直接定义标记点即可；然后就是让它递归回溯，标记时要注意正负的顺序。具体实现代码如下：

#include <bits/stdc++.h>
using namespace std;
#define Max 10000
int n,k;
int sum=0;
char Array[Max][Max];
bool check[Max],check1[Max];//创建标记函数void DFS(int x) {if (x==0) {sum++;//计数器return;}for (int i=0;i<n;i++) {for (int j=0;j<n;j++) {if (Array[i][j]=='#'&&check[i]&&check1[j]) {//判断是否可以放置棋子check[i]=check1[j]=false;//标记棋子Array[i][j]='.';//标记位置为不可用DFS(x-1);//递归check[i]=check1[j]=true;//回溯}}}
}
int main() {while (cin>>n>>k&&n!=-1&&k!=-1) {sum=0;for (int i=0;i<n;i++) {for (int j=0;j<n;j++) {cin>>Array[i][j];check[i]=true;//初始都可用check1[j]=true;}}DFS(k);cout<<sum<<endl;}}

while那里表示循环输入，因为题中说明是通过-1来判断是否结束。