回溯水题训练

BNUOJ 1440

这题其实就是变相的简单的n皇后问题，（不同的地方在于n皇后问题是每一行每一列都只摆放一个皇后，而这里可以不摆放）不过遍历时有个小技巧就是每走到一个位置都从此时的行出发往下遍历所有的行和列，这样，如果某一行不拜访，则可以通过循环直接下一行，无需再次递归，再次递归会TLE。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=100;
int n,m,cnt;
bool vis[maxn];
char g[10][10];
int dfs(int cur,int m){
if(m==0)
return ++cnt;
for(int i=cur;i<n;i++)///巧妙
for(int j=0;j<n;j++)
if(g[i][j]=='#'&&!vis[j]){
vis[j]=true;
dfs(i+1,m-1);///这里注意从i出发
vis[j]=false;
}
}
int main(){
while(cin>>n){
cin>>m;
if(m==-1&&n==-1)
break;
memset(g,'',sizeof(g));
memset(vis,0,sizeof(vis));
cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>g[i][j];
//canf("%d",&g[i][j]);
}
dfs(0,m);
cout<<cnt<<endl;
}
return 0;
}

最后

以上就是高大雪糕为你收集整理的回溯水题训练的全部内容，希望文章能够帮你解决回溯水题训练所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。