棋盘问题 ( POJ -1321 )(简单DFS)
问题 简单 DFS 棋盘 poj
2023-06-13 09:17:22 时间
转载请注明出处:https://blog.csdn.net/Mercury_Lc/article/details/82684942 作者:Mercury_Lc
题解:dfs入门,就是每个点都搜索一下,什么时候够了k个就ans++。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n,k;
int ans = 0;
int step = 0;
char mp[55][55];
bool vis[55];
void dfs(int x)
{
int i;
if(step == k)
{
ans ++;
return ;
}
if(x >= n)
return ;
for(i = 0; i < n; i ++)
{
if(!vis[i] && mp[x][i] == '#')
{
step ++;
vis[i] = true;
dfs(x + 1);
vis[i] = false;
step --;
}
}
dfs(x + 1);
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
if(n == -1 && k == -1)
return 0;
for(int i = 0; i < n; i ++)
{
getchar();
scanf("%s",&mp[i]);
}
ans = 0;
step = 0;
memset(vis,0,sizeof(vis));
dfs(0);
printf("%d\n",ans);
}
return 0;
}
problem 在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放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 Output2
1
相关文章
- 常量字符串的问题
- acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」
- 解决WordPress访问服务器权限不足的问题
- 原生php怎么得到当前项目根目录的绝对路径?这个问题我解决了
- 使用G2O解决优化问题的简单例子
- 需要多次VLOOKUP的问题,在Power Query里原来这么简单! | PQ实战
- 解决使用 mPDF 导出 PDF 时中文及符号乱码问题
- 一个简单的问题:什么是连续网络和不连续网络?
- 超简单一步解决Win10系统无法访问网页,但软件能够联网的问题
- 电脑磁盘老是100%是什么原因 (完美解决电脑磁盘老显示100%问题)
- 字节面试官狂问我:数据库查询超时优化问题
- 简单0-1背包问题求解
- 系统自带模版在 emlog pro 1.8.0 底部信息错位问题暂时的解决方案
- 最新!最简单!解决注册ChatGPT手机号无法接收验证码问题亲测有效!【图文并茂的教程】
- POSTGRESQL 锁表的问题详解数据库
- SSH框架问题——java.lang.NoClassDefFoundError: org/springframework/dao/support/PersistenceExceptionTransla详解编程语言
- 时间解决Java操作Redis过期时间问题(redisjava过期)
- 深度探索Linux高精度定时器技术,精准解决计时精度问题!(linux高精度定时器)
- 连接解决Mac OS网络连接问题的简单方法(macos网络)
- 解决方法解决 Kali Linux 乱码问题的简单方法(kalilinux乱码)
- Linux系统审计:掌握日志问题关键(linux审计日志)
- 解决Linux文件损坏问题的简单方法(linux文件损坏)
- 解决Oracle安装闪退的问题:简单方法与技巧(安装oracle闪退)
- 如何解决Oracle存储中文乱码问题?(oracle存储中文乱码)
- 如何解决MySQL创建数据库报错问题?(mysql创建数据库报错)
- 如何解决Oracle中的排序问题?(oracle排序问题)
- MySQL解决输出乱码问题的实用小技巧(mysql输出乱码)
- MySQL 1045错误连接权限问题实战总结(1045错误MySQL)
- 无法连接Redis主机名解析问题(主机名无法连接redis)
- 解决mysql安装问题的简单方法(mysql一直安装不了)
- 解决MySQL中文乱码问题简单方法(mysql z中文乱码)
- ajax自动完成下拉框自动提示位置问题
- 在Oracle网络结构解决连接问题
- 解析android截屏问题