DFS(3)——poj1321棋盘问题
2024-08-26 12:32:04
一、题目回顾
题目链接:棋盘问题
Description
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
Output
对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1
题意:棋子摆放的位置只能是#,且不能同行和同列。问摆放棋子的方案数。
二、解题思路
- DFS
- 复习题
我采用的是按行递增的顺序来搜索的,因此不可能出现同行的情况,对于同列的情况,我设置了一个数组col[],来保存列的访问状态,对于之前访问过的列,棋子是不能再放在这一列上的。
dfs(cow) 代表将首枚棋子放在第row行。
三、代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std; int n,k,m; //k:要放置的棋子数 m:棋盘上已放置的棋子数
int ans; //方案数
char a[][];
int col[]; //记录第几列是否被访问
void dfs(int row) //第一枚棋子放在第row行
{
if(k==m){ //棋子全放在棋盘上
ans++;
return;
}
if(row>n) return;
for(int j=;j<=n;j++){
if(a[row][j]=='#' && !col[j]){
col[j] = ;
m++;
dfs(row+);
col[j] = ; //改回来方便下一行的判断
m--; }
}
dfs(row+); //一种方案结束,开始下一种方案
} int main()
{
while(scanf("%d%d",&n,&k)){
if(n==- && k==-) break;
for(int i=;i<=n;i++){
getchar();
for(int j=;j<=n;j++){
scanf("%c",&a[i][j]);
}
}
getchar();
memset(col,,sizeof(col));
ans = ;
m = ;
dfs(); //第一种方案将首枚棋子放在第一行
printf("%d\n",ans);
}
return ;
}
最新文章
- C# 6.0新特性---语法糖
- 分享一个异步任务在遇到IO异常时支持递归回调的辅助方法
- zw版【转发&#183;台湾nvp系列Delphi例程】HALCON FillUpShape2
- JQ获取当前是第几个元素,以及直接选取第几个元素的方法
- MongoDB - Introduction to MongoDB, BSON Types
- C++默认参数不能是一个引用
- csss3 2D转换
- JSON 解析器。JSON.stringify和JSON.parse
- 但从谈论性能点SQL Server选择聚集索引键
- 一步一步的理解C++STL迭代器
- 在国内使用maven下载jar包非常慢的解决方法
- python-ansible api2.0 多进程执行不同的playbook
- Android studio 一些技术添加依赖,依赖库
- 11-05-sdust-个人赛赛后随想
- GIT里的一些名词
- using的几种用法
- ios开发怎样才能做到代码和界面彻底分离,方便换肤?
- Eclipse下进行SVN提交时报“svn: 过期”错误的解决办法
- 多维标度法(MDS)的Python实现
- SQLServer SELECT @@IDENTITY 遇到的坑