POJ 1321

题意

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

思路

经典DFS
用一个all记录摆放种类, 一个now记录目前为止放了几个棋子, 当now == k时 all++, return;

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mst(a) memset(a, 0, sizeof(a));
using namespace std;
const int maxn = 10;
int g[maxn][maxn];
int vis[maxn]; //记录某列是否已放过棋子
int n, k, all, now;

void init(){
    mst(g);
    all = 0;
    now = 0;
}

void dfs( int x ){
    if( now == k ){
        all++;
        return;
    }
    if( x >= n )  return;
    for( int j = 0; j < n; j++ ){
        if( vis[j] == 0 && g[x][j] == 1 ){
            vis[j] = 1;
            now++;
            dfs(x+1);
            vis[j] = 0;
            now--;
        }
    }
    dfs(x+1);
    return;
}

int main()
{
    while( scanf("%d%d",&n, &k) == 2 && n != -1 ){
        init();
        getchar();
        mst(g);
        char ch;
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j < n; j++ ){
                scanf("%c",&ch);
                if( ch == '#' ) g[i][j] = 1;
                else if( ch == '.' ) g[i][j] = 0;
            }
            getchar();
        }
        dfs(0);
        printf("%d
", all);
    }
    return 0;
}