棋盘问题 POJ - 1321(简单搜索)

本文主要是介绍棋盘问题 POJ - 1321(简单搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

根据题意得，棋盘位置每行每列只能有一个棋子，那么也就是说，对于每一行，在该行中最多只有一个位置放有棋子，需要对该棋子的位置进行搜索，确定之后，进入下一行，当落下k个棋子时，计数加1，返回上一个状态继续。
需要注意的是，以行进行搜索，则需要对列进行标记，反之亦然。

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1010
char a[N][N];
int b[N],n,k,ans;
void dfs(int row,int step)  //以行为单位搜索，则行必然不会重复
{if(step==k){ans++;return;}if(row>n) return;for(int i=0;i<n;i++){  //遍历列，对列进行标记if(a[row][i]=='#'&&!b[i]){b[i]=1;dfs(row+1,step+1);b[i]=0;}}dfs(row+1,step); //考虑该行中不下棋的情况return;
}
int main()
{while(~scanf("%d%d",&n,&k)){memset(b,0,sizeof(b));if(n==-1&&k==-1) break;for(int i=0;i<n;i++)scanf("%s",a[i]);ans=0;dfs(0,0);printf("%d\n",ans);}return 0;
}

这篇关于棋盘问题 POJ - 1321(简单搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---