开发者社区> 华山青竹> 正文

棋盘问题 POJ 1321

简介: 总时间限制:  1000ms 内存限制:  65536kB 描述 在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
+关注继续查看
总时间限制: 
1000ms
内存限制: 
65536kB
描述
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
输入
输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
输出
对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
样例输入
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
样例输出
2
1
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <set>
 7 #include <queue>
 8 #include <stack>
 9 
10 using namespace std;
11 char map[10][10];
12 int vis[10];//第i列是否放置了棋子
13 int cnt;//已放棋子的数目
14 int sum;//放置方法的总数
15 int n,k;
16 void dfs(int s)
17 {
18     int i;
19     if(cnt==k){//所有的棋子都放置好
20         sum++;
21         return ;
22     }
23     else{
24         if(s>=n)//如果越界
25             return ;//返回
26         else{
27             for(i=0;i<n;i++){//讲一个棋子尝试放在0-n-1列的某一行
28                 if(map[s][i]=='#'&&!vis[i]){
29                     vis[i]=1;//标记该列已经放了棋子
30                     cnt++;//棋子数+1
31                     dfs(s+1);//继续搜索
32                     cnt--;//经过一轮递归后num始终保持不变,因为没有放棋子
33                     vis[i]=0;//在此处不放棋子
34                 }
35             }
36             dfs(s+1);//进行剩下的k-1个棋子的遍历
37         }
38     }
39 }
40 int main()
41 {
42     int i;
43     while(~scanf("%d %d",&n,&k)){
44             getchar();
45         if(n==-1&&k==-1) break;
46         memset(vis,0,sizeof(vis));
47         for(i=0;i<n;i++)
48             scanf("%s",map[i]);
49     cnt=sum=0;
50         dfs(0);
51         printf("%d\n",sum);
52     }
53     return 0;
54 }

参考: http://blog.csdn.net/u013486414/article/details/43878071

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
poj-1012-约瑟夫问题
Description The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, .
635 0
算法:POJ1006 三重峰值问题
这题有直接套公式的解法 这里提供一个O(n)的解法。 package practice; import java.io.BufferedInputStream; import java.
683 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19085 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28302 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14233 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
16601 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22186 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载