Article From:https://www.cnblogs.com/wanghaixv/p/9059974.html

Chessboard problem

A chessboard with a given shape (which may be irregular) has no difference in playing chess pieces. Two pieces of any chessboard that can not be placed on the same line or the same column in a chessboard are required to be programmed to solve all feasible placement schemes, C, for a chessboard with a given shape and size and K pieces.

Input

The input contains multiple sets of test data. It
The first line of each group of data is two positive integers, N K, separated by a space, indicating that the chessboard will be described in a matrix of a n*n and the number of chessmen is placed. N < = 8, K < = n
The end of the input is expressed when -1 -1 is used. It
The next N line describes the shape of the chessboard: there are n characters per line, which represents the chessboard area, which represents the blank area (the data guarantees no redundant blank lines or blank columns). It

Output

For each set of data, a row output is given, and the number of programs put out is C (data guarantee C< 2^31).

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

Question: similar to the eight queens, but different from the eight queens.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

char map[10][10];
bool mark[10];
int n,k,tot,q;
int m;

void DFS(int cur)
{
    if(k==m)
    {
        tot++;
        return ;
    }
    if(cur>=n) return ;
    for(int i=0;i<n;i++)
    {
        if(mark[i]==0&&map[cur][i]=='#')
        {
            mark[i]=1;
            m++;
            DFS(cur+1);
            mark[i]=0;
            m--;
        }
    }
    DFS(cur+1);
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF&&n!=-1&&k!=-1)
    {
        tot=0;
        m=0;
        for(int i=0;i<n;i++) scanf("%s",map[i]);
        memset(mark,0,sizeof(mark));
        DFS(0);
        printf("%d\n",tot);
    }
    return 0;
}

 

Link of this Article: Deep search

Leave a Reply

Your email address will not be published. Required fields are marked *