ACM题目————棋盘问题

时间:2022-12-25 11:24:59
Description
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放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 -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;
}

ACM题目————棋盘问题的更多相关文章

  1. ACM题目————中缀表达式转后缀

    题目描述 我们熟悉的表达式如a+b.a+b*(c+d)等都属于中缀表达式.中缀表达式就是(对于双目运算符来说)操作符在两个操作数中间:num1 operand num2.同理,后缀表达式就是操作符在两 ...

  2. ACM题目————马拦过河卒

    题目描述 棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下.或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.因此称之为“马拦过河卒”. ...

  3. HDU ACM 题目分类

    模拟题, 枚举1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 1047 1048 104 ...

  4. ACM题目推荐(刘汝佳书上出现的一些题目)&lbrack;非原创&rsqb;

    原地址:http://blog.csdn.net/hncqp/article/details/1758337 推荐一些题目,希望对参与ICPC竞赛的同学有所帮助. POJ上一些题目在http://16 ...

  5. 有一种acm题目叫做,奇葩!

    本文全然没有技术含量,纯粹是娱乐. 我事实上想写点东西.可是近期好像做计算几何做得太多了,一种想说说不出东西的感觉,唯有写一下一些奇葩的题目了. HDU3337:Guess the number pi ...

  6. ACM题目————STL练习之求次数

    题目地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=1112 描述 题意很简单,给一个数n 以及一个字符串str,区间[i,i+n-1] 为一个 ...

  7. ACM题目————zoj问题

    题目1006:ZOJ问题 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:20322 解决:3560 题目描述: 对给定的字符串(只包含'z','o','j'三种字符),判断他是否能AC. ...

  8. ACM题目————又见拦截导弹

    描述 大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮 ...

  9. ACM题目————还是畅通工程

    Submit Status Description 某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离.省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路 ...

随机推荐

  1. C&plus;&plus; 输出调试的一些技巧

    主要利用了宏和stderr... #define enable_debug #ifdef enable_debug FILL some macros/functions here #else /// ...

  2. Scala 深入浅出实战经典 第63讲:Scala中隐式类代码实战详解

    王家林亲授<DT大数据梦工厂>大数据实战视频 Scala 深入浅出实战经典(1-87讲)完整视频.PPT.代码下载:百度云盘:http://pan.baidu.com/s/1c0noOt6 ...

  3. TOMOYO Linux&lpar;undone&rpar;

    目录 . TOMOYO Introduction . TOMOYO Sourcecode Analysis 1. Introduction TOMOYO是一款基于LSM Framework实现的LSM ...

  4. objective-c中自己创建的对象为什么不能调用release

    dealloc方法,本就不应该手动调用. 你自己创建的对象,看你代码怎么写的了.例子:NSString *str1 = [NSString stringWithString:@"abc&qu ...

  5. ARM指令系统

    转载自:http://cxb4224.blog.163.com/blog/static/191224151201110220325976/ ARM处理器的工作状态和工作模式 工作状态 ARM处理器一般 ...

  6. uoj &num;31&period; 【UR &num;2】猪猪侠再战括号序列 贪心

    #31. [UR #2]猪猪侠再战括号序列 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://uoj.ac/problem/31 Descript ...

  7. 【HDOJ】1969 Pie

    二分. #include <stdio.h> #include <math.h> ; ]; int main() { int case_n, n, f, m; double r ...

  8. &lbrack;Angular 2&rsqb; Keynote&colon; Lazy Routing -- NGCONF

    So How to do lazy loading for router in Angular 2. The nomarl way to write a router in Angular 2: Yo ...

  9. NET MVC异常处理模块

    一个简单的ASP.NET MVC异常处理模块   一.前言 异常处理是每个系统必不可少的一个重要部分,它可以让我们的程序在发生错误时友好地提示.记录错误信息,更重要的是不破坏正常的数据和影响系统运行. ...

  10. canvas-弧形可拖动进度条

    一.效果如下: See the Pen XRmNRK by pangyongsheng (@pangyongsheng) on CodePen. 链接dome 二. 本文是实现可拖动滑块实现的基本,及 ...