博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 1321-棋盘问题
阅读量:4991 次
发布时间:2019-06-12

本文共 2158 字,大约阅读时间需要 7 分钟。

这是手册上的深搜题,首先我们要将棋盘的位置标记,因为行和列都不同,所以必须用两个数组分别来存

点的横坐标和纵坐标,然后开始一个棋子一个棋子地摆上去,计算有几种摆法。

#include
#include
using namespace std; const int N = 8*8 + 10; int x[N], y[N]; bool visx[N], visy[N]; int n, k, m; long long cnt; char ch[N]; void dfs( int a, int ans) {
if( k == ans) cnt ++; for( int i = a; i < m; i ++) if( !visx[ x[i] ] && !visy[ y[i] ]) {
visx[ x[i] ] = true; visy[ y[i] ] = true; dfs( i + 1, ans + 1); visx[ x[i] ] = false; visy[ y[i] ] = false; } } int main() {
while( true) {
cin >> n >> k; if( n == -1 && k == -1) break; m = 0; for( int i = 0; i < n; i ++) {
cin >> ch; for( int j = 0; j < n; j ++) {
if( ch[j] == '#') {
x[m] = i; y[m] = j; m ++; } } } memset( visx, false, sizeof visx); memset( visy, false, sizeof visy); cnt = 0; dfs( 0, 0); cout << cnt << endl; } return 0; }

下面这个代码超时,没搞懂原因

#include
#include
using namespace std; const int N = 8*8 + 10; int x[N], y[N]; bool vis[N][N]; int n, k, m; long long cnt; char ch[N]; void dfs( int a, int ans) {
if( k == ans) cnt ++; for( int i = a; i < m; i ++) if( !vis[ x[i] ][ y[i] ]) {
vis[ x[i] ][ y[i] ] = true; dfs( i + 1, ans + 1); vis[ x[i] ][ y[i] ] = false; } } int main() {
while( true) {
cin >> n >> k; if( n == -1 && k == -1) break; m = 0; for( int i = 0; i < n; i ++) {
cin >> ch; for( int j = 0; j < n; j ++) {
if( ch[j] == '#') {
x[m] = i; y[m] = j; m ++; } } } memset( vis, false, sizeof (vis) ); cnt = 0; dfs( 0, 0); cout << cnt << endl; } return 0; }

 

 

转载于:https://www.cnblogs.com/Yu2012/archive/2011/11/19/2255641.html

你可能感兴趣的文章
[beta cycle]daily scrum10_2.25
查看>>
【转载】和 Thrift 的一场美丽邂逅
查看>>
CM_RESOURCE_LIST structure 分类: wind...
查看>>
css单位pr,em,与颜色
查看>>
Angularjs笔记(三)
查看>>
@ControllerAdvice 标签为起作用
查看>>
lambda
查看>>
ubuntu16.04下使用python3开发时,安装pip3与scrapy,升级pip3
查看>>
python网络编程基础
查看>>
selenium+maven+testng+IDEA+git自动化测试环境搭建(二)
查看>>
Mini2440 UART原理及使用
查看>>
Linux学习第六篇之文件处理命令ln(链接命令)
查看>>
thinkphp5 tp5 七牛云 上传图片
查看>>
Windows 7 x64 安装Windows SDK 7.1失败的原因及解决方法
查看>>
VM下Linux网卡丢失(pcnet32 device eth0 does not seem to be ...)解决方案
查看>>
第一阶段意见汇总以及改进
查看>>
再说virtual
查看>>
随笔:技术流可以这样写博客
查看>>
[优化]JavaScript 格式化带有占位符字符串
查看>>
打JAR包
查看>>