搜索：poj 1321 棋盘问题 —FS ）

[转]http://poj.org/problem?id=1321

?

#include <stdio.h>#include <stdlib.h>#include <iostream>#include <memory.h>using namespace std;int map[10][10];int n,k,cou,sum;void input()        //处理输入数据，把能走的赋为0，不能的为2，走过的为1{char str[10];for(int i=1; i<=n; i++){cin >> str;for(int p=0; p<n; p++)map[i][p+1] = ( str[p] == '#' ? 0 : 2 );}}int find(int i,int j)  //这个函数真应该起个好名字。。。突出不来它的作用捏。。{                       // 这个是判断是否有和i j 同行 同列的元素，没的话返回1for(int p=1; p<=n; p++)if( map[i][p] == 1 )return 0;for(int p=1; p<=n; p++)    if( map[p][j] == 1 )        return 0;return 1;}void DFS(int d)    // 深搜呀 深搜呀 深搜。。。{if( cou + n - d + 1 < k ) // 这个是如果cou加上未来几行（理想情况下 n-d）+1 还小于K    return ;              //即没希望达到K了，早点return。。if( cou == k ){sum++;return;}if( d > n )    return ;int flag = 0;for(int j=1; j<=n; j++){if( find(d,j) && !map[d][j] ){flag = 1;map[d][j] = 1;cou++;DFS(d+1);cou--;map[d][j] = 0;}}if( flag == 1 )    DFS(d+1);}int main(void)   // 这个不废话了。。 sum记录方案个数，cou记录放置的棋子个数{while( cin >> n >> k && n!= -1 ){memset( map,0,sizeof(map) );cou = 0; sum = 0;input();DFS(1);cout << sum << endl;}    return 0;}

?