棋盘问题 ( POJ -1321 )(简单DFS)
2024-09-05 06:10:00
转载请注明出处:https://blog.csdn.net/Mercury_Lc/article/details/82684942作者:Mercury_Lc
题解:dfs入门,就是每个点都搜索一下,什么时候够了k个就ans++。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n,k;
int ans = 0;
int step = 0;
char mp[55][55];
bool vis[55];
void dfs(int x)
{
int i;
if(step == k)
{
ans ++;
return ;
}
if(x >= n)
return ;
for(i = 0; i < n; i ++)
{
if(!vis[i] && mp[x][i] == '#')
{
step ++;
vis[i] = true;
dfs(x + 1);
vis[i] = false;
step --;
}
}
dfs(x + 1);
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
if(n == -1 && k == -1)
return 0;
for(int i = 0; i < n; i ++)
{
getchar();
scanf("%s",&mp[i]);
}
ans = 0;
step = 0;
memset(vis,0,sizeof(vis));
dfs(0);
printf("%d\n",ans);
}
return 0;
}
problem
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。Output
对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1Sample Output
2
1
最新文章
- sql
- 【DP】HDU 1176
- 如何解决xx列不在表中
- centos6.8部署vnc服务
- flex 加载arcgis 的地图json
- Vusual C++连接Mysql和从MySql中取出数据的API介绍
- 【转】Mac 上 java 究竟在哪里,本文彻底让你搞清楚!
- [原创] CSS总结!! 有关HTML第二篇 !!
- SQL 各种连接:内连接,外连接(左外,右外,完全外)
- 如何用python语句获得Python的安装目录
- iOS 多线程学习笔记 —— NSThread
- 使用 HT 单片机芯片做触摸按键的试验:触摸按键实践一
- jquery节点查询
- jQuery ajax() 参数,回调函数,数据类型,发送数据到服务器,高级选项
- 看漫画学Flux
- 03_SQL server数据类型
- 在线播放Video/PDF/JPG
- ArcGIS案例学习笔记-CAD数据自动拓扑检查
- 六 json&;pickle模块
- unigui作中间件使用