题目描述
n皇后的简化加强版,舍弃了斜边的限制,加了一些其他的限制
思路
增加判断条件后直接爆搜
C++ 代码
//DFS
//类似于八皇后的一道多了一些限制的题
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
char g[N][N]; //存储输入棋盘
int ans; //存储答案
int n, k;
int m; //存储已近放入棋盘的棋子数
bool line[N]; //存储当前列上有没有其他棋子
void dfs(int x)
{
if(m == k) //当棋子放光的时候
{
ans++;
return;
}
if(x == n) //防止越界
return;
for(int i = 0; i < n; i++) //爆搜
if(!line[i] && g[x][i] == '#')
{
line[i] = true;
m++; //记录放入的棋子数
dfs(x + 1);
line[i] = false; //还原初始状态
m--;
}
dfs(x + 1);
//这个是关键,因为 k <= m,因此可能有行不用放棋子,所以我们要手动舍弃行,直接进入下一行
}
int main()
{
while(scanf("%d%d", &n, &k) && n != -1 && k != -1)
{
ans = m = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> g[i][j];
dfs(0);
cout << ans << endl;
}
return 0;
}
是因为k <= n吧?不是m
对的!
dfs(x + 1);
//这个是关键,因为 k <= m,因此可能有行不用放棋子,所以我们要手动舍弃行,直接进入下一行这一行应该在什么时机执行啊?假如有四行,放三颗棋子,这里是不是还有一个选4行里面选哪三行啊,但是是怎么实现的啊,谁能讲讲。孩子彻底懵逼了
爆搜是不是写错了
暴搜
能解释一下吗大佬
我感觉我看不懂这个题跟你dfs for循环那里
就是每个结点有着0 ~ n-1 种选择,因为dfs本质就是一颗搜索树,画个图就好了