博客
关于我
强烈建议你试试无所不能的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

你可能感兴趣的文章
解释器、编译器以及他们之间的差别。
查看>>
MongoDB的快速手动安装
查看>>
JS制作简单的日历控件【JS Date对象操作实例演示】
查看>>
模板—树上倍增LCA
查看>>
高二小假期集训—D5
查看>>
EasyUI easyui-combobox 重复发送请求
查看>>
memcached-repcached
查看>>
[转]CentOS 5.3通过yum升级php到最新版本的方法
查看>>
UVA 11235 - Frequent values RMQ的应用
查看>>
大数据日志采集系统
查看>>
java 堆调优
查看>>
linux 安装JDK
查看>>
JAVA调用CMD命令
查看>>
weblogic的安装
查看>>
SSM框架中,controller的action返回参数给vue.js
查看>>
Mysql 基础3
查看>>
smartctl工具应用(转载整理)
查看>>
控件数据绑定总结
查看>>
HTTP协议
查看>>
Vue 框架-09-初识组件的应用
查看>>