Description

Input

Output

Sample Input

2 1

#.

.#

4 4

...#

..#.

.#..

#...

-1 -1

Sample Output

2

1

题意清晰，回溯也非常明白。建议学习回溯的时候对N皇后还有N皇后的变式好好学习一下，类N皇后真是学习回溯非常好的例题。

分析：

如在第i行第j列，遇到'#'号。那么接下来的处理就有两种情况了。

第一种：把i,j放入到一个数组C中，然后继续向第i+1行进行搜索，直到找到K个位置或者到了棋盘的边界

另外一种：我不选择第i行第j列的位置，然后继续向第i+1行进行搜索，直到找到K个位置或者到了棋盘的边界

最后。回溯另一个很重要的就是剪枝，剪枝过程在代码里面有凝视。

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 15;

int N,K,ans,C[maxn];

char Map[maxn][maxn];

bool can_place(int row,int col)

{

    for(int i = 0;i < row;i++)

    {

        if(C[i] == col) return false;

    }

    return true;

}

void DFS(int row,int cur) {

    if(cur == K)

    {

        ans ++;

        return;

    }

    if(row >= N) return;

    if(cur + (N-row) < K) return; // 剪枝

    for(int j = 0;j < N;j++)

    {

        if(Map[row][j] == '#'&&can_place(row,j))

        {

            C[row] = j;

            DFS(row+1,cur+1);

            C[row] = -1;

        }

    }

    DFS(row+1,cur);

}

int main() {

    freopen("input.in","r",stdin);

    while(~scanf("%d %d",&N,&K))

    {

        if(N == -1 && K == -1) break;

        for(int i = 0;i < N;i++) scanf("%s",Map[i]);

        ans = 0;

        memset(C,-1,sizeof(C));

        for(int j = 0;j < N;j++)

        {

            if(Map[0][j] == '#')

            {

                C[0] = j;

                DFS(1,1);

                C[0] = -1;

            }

        }

        DFS(1,0);

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

    }

    return 0;

}