POJ1321 棋盘问题 —— DFS回溯
2024-09-07 15:31:59
题目链接:http://poj.org/problem?id=1321
棋盘问题
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 50263 | Accepted: 24352 |
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
Source
题解:
类似于八皇后问题。
由于题目要求放k个,不像八皇后那样固定了8个,所以在一开始时不知道怎样处理“k个”。即如果实际能放的位置比k要大时该怎么处理
一开始是想:在能够放的地方,执行两种操作,放和不放。但是却会出现重复,因为对于一行,不放的位置可以是多个,这就有了多种情况,但实际上这多种情况都是一样的,因为对于接下来的行,所呈现的状态是一样的。
正确的操作是:把操作对象从“一个”改为“一行”。对于每一行,有放和不放两种操作,如果不放,则直接跳过;如果放,则再决定放在哪个位置。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = +; int n, k, ans;
char m[MAXN][MAXN];
int col[MAXN]; void dfs(int dep, int t)
{
if(dep==n+) //到达末时,如果刚好放了k个,则计数器+1
{
if(t==k) ans++;
return;
} dfs(dep+, t); //这一行不放
for(int i = ; i<=n; i++) //这一行放
{
if(m[dep][i]=='#' && col[i]== && t<k ) //t<k为剪枝
{
col[i] = ;
dfs(dep+, t+);
col[i] = ;
}
} //以下为错误的思想
// for(int i = 1; i<=n; i++)
// {
// if(m[dep][i]=='#' && col[i]==0 )
// {
// dfs(dep+1, t); //会出现重复
// col[i] = 1;
// dfs(dep+1, t+1);
// col[i] = 0;
// }
// } } int main()
{
while(scanf("%d%d",&n,&k))
{
if(n==- && k==-) break; ms(col,);
ans = ;
for(int i = ; i<=n; i++)
scanf("%s", m[i]+); dfs(, );
cout<< ans <<endl;
}
}
最新文章
- COGS182 [USACO Jan07] 均衡队形[RMQ]
- 译:Google的大规模集群管理工具Borg(一)------ 用户视角的Borg特性
- 嘻哈帮天通苑_poppin——张锋
- Objective-C命名编写规范
- Citrix 服务器虚拟化之六 Xenserver虚拟机创建与快照
- apache禁止公网IP访问的配置
- 自学Zabbix3.6.2-触发器triggers severity严重程度
- 设计模式NO.2
- solr多集合配置
- Ffmpeg使用
- cookie 和session 详解
- 在过去五分钟内,TypeScript语言服务以外终止了5次
- drand48 等 随机数生成函数
- 在UnrealEngine中用Custom节点实现毛玻璃的效果
- 5款最好的免费在线网站CSS验证器
- centos 安装python PIL模块
- List接口、Set接口和Map接口
- cgroup其他部分 IO + hugepage
- EasyUI学习总结(二)——easyloader分析与使用(转载)
- c#之根据出生日期获得星座信息