POJ 1321 棋盘问题

题意：中文题不解释。

思路：经典DP，比较取巧的想法是一行行(按照题目意思一行最多只能放一个)来看，标记一列列。注意考虑到有些行可能不放的情况。

/**

Sample Input

2 1

#.

.#

4 4

...#

..#.

.#..

#...

-1 -1

Sample Output

2

1

**/

#include<cstdio>

#include<cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 15;

char maps[maxn][maxn];

int vis[maxn];

int ans;

int n,k;

void dfs(int c,int cnt){

    if(cnt == k){

        ans++;

        return ;

    }

    if(c >= n)

        return ;

    for(int i=0;i<n;i++){

        if(!vis[i]&&maps[c][i]=='#'){  //该列没有访问过，而且可以放棋子

            vis[i] = 1;

            dfs(c+1,cnt+1);

            vis[i] = 0;

        }

    }

    dfs(c+1,cnt);  //这一行也可以不放

}

int main()

{

    while(~scanf("%d%d",&n,&k))

    {

        ans = 0;

        memset(vis,0,sizeof(vis));

        if(n==-1&&k==-1)

            break;

        for(int i=0;i<n;i++){

            scanf("%s",maps[i]);

        }

        dfs(0,0);

        printf("%d\n",ans);

    }

    return 0;

}