poj 1321 dfs

背景：1AC，自己YY的方法，很好。

思路：这个题看到感觉是八皇后的变种。但是有两点不同：1.棋盘不是规则的形状，这个简单，就相当于有些地方不能放。2.棋子数k <= n,这个就有点问题了，因为八皇后是棋子数等于行数只需要每一行都放一个棋子就可以了。这里我还是采用逐行搜索的方法，但是对于每一行的判断是选一个或者不选，这样搜索出说有情况即可。

我的代码：

#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 10
#define INF 0x3fffffff
#define LL long long int
using namespace std;
bool diagram[M][M],vis[M];
int n,k,ans,step;

void dfs(int x){
     if(step == k){return;}
     for(int j=0;j <= n;j++){
        if(j == 0 && x+1 <= n) dfs(x+1);//这一行一个都不选。
        else if(j != 0 && !vis[j] && diagram[x][j]){//这一行选一个
            vis[j]=1;
            step++;
            if(step == k){ans++;}//到达目标状态加一。
            if(x+1 <= n) dfs(x+1);
            step--;//回溯
            vis[j]=0;
        }
     }
}

int main(void){
    while(scanf("%d%d%*c",&n,&k),n != -1){
        memset(vis,0,sizeof(vis));
        ans=step=0;
        for(int i=1;i <= n;i++){
            for(int j=1;j <= n;j++){
                char c=getchar();
                c != '#' ? diagram[i][j]=0 : diagram[i][j]=1;
            }
            getchar();
        }
        dfs(1);
        printf("%d\n",ans);
    }
    return 0;
}

poj 1321 dfs

原文：http://blog.csdn.net/jibancanyang/article/details/44648291