ACM题目————棋盘问题
2024-09-16 05:32:11
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便好!
//Asimple
#include <iostream>
#include <string.h> using namespace std; int n, T, num, cnt, p;
char Map[10][10];
int vis[10];//记录同一列是否有过棋子 using namespace std; void DFS(int k)
{
if( num == p )
{
cnt ++ ;
return ;
}
if( k >= n ) return ;//边界
for( int i=0; i<n; i++)
{
if(!vis[i] && Map[k][i]=='#')
{
vis[i] = 1 ;
num ++ ;
DFS(k+1);
num -- ;
vis[i] = 0 ;
}
}
DFS(k+1);
} int main()
{
while( cin >> n >> p )
{
if( n == -1 && p == -1 ) break ;
for (int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >> Map[i][j] ;
memset(vis,0,sizeof(vis));
cnt = 0 ;
num = 0 ;
DFS(0);
cout << cnt << endl ; } return 0;
}
最新文章
- python pickle 序列化类
- 应用matplotlib绘制地图
- notification的使用
- 用友android
- Android开发教程大全介绍
- React问答小demo
- cmake编译(编译目标)x86或x64
- paip.Adblock屏蔽规则保存位置以及修理恢复
- 【Python网络编程】多线程聊天软件程序
- SmartBusinessDevFramework架构设计-3:考虑开源?
- [Swust OJ 360]--加分二叉树(区间dp)
- JUnit4.8.2来源分析-2 org.junit.runner.Request
- POCO Controller
- Flask中的单例模式
- js中url跳转问题
- Java 中数字和字符串拼接的问题
- c#devexpress 窗体控件dock的重要
- 随机函数rand()和srand()
- asp.net缓存 (转)
- [转]zookeeper-端口说明
热门文章
- 安装Cocoapods(Pods 管理iOS 第三方库)
- chart crash
- Oracle 10046 trace文件分析
- 通过SSIS监控远程服务器磁盘空间并发送邮件报警!
- css 正方体
- CentOS6.5 安装HAProxy 1.5.20
- transient关键字的含义
- csuoj 1113: Updating a Dictionary
- [原创]java WEB学习笔记51:国际化 概述,API 之 locale类,dataFormat类,numberFormat类, MessageFormat类,ResourceBundle 类
- 。。。Hibernate 查询数据 事务管理。。。