kuangbing带你飞 专题一 简单搜索题解

kuangbin带你飞 专题一 简单搜索
1. POJ 1321 棋盘问题
http://poj.org/problem?id=1321
题目类似八皇后 但是加入了障碍物 以及规则为不能同列和同行
我一开始的思路走入了误区 用bool二维数组判断标记
其实我们可以简化问题
将问题看做 在每一行选一个点落下棋子 而保证棋子不在一列 即可
由此确定出dfs的递归参数 一个是行 一个是棋子数 当超出行的时候回溯 在棋子数满足答案时res++并回溯
有一个值得注意的地方 在一行里 可以选择放 也可以选择不放 要注意写出在本行不放的递归函数
char g[10][10];
bool st[10];//这是列的标记 行不需要 因为我们是行行递推下去的
int res, n, k;

void dfs(int dep, int num)//第几行 落子数
{
if(num == k) {res +

kuangbing带你飞 专题一 简单搜索题解最先出现在Python成神之路。