D-碁盤問題

3402 ワード

Descriptionは所定の形状の碁盤にあります(形状が不規則である可能性がある)上に駒を並べても、駒に違いはない.並べ替えを要求する場合、任意の2つの駒を碁盤の中の同じ行または同じ列に置くことはできない.所定の形状と大きさの碁盤に対して、k個の駒を並べたすべての実行可能な並べ替えスキームCをプログラミングして解いてください.Inputは複数のテストデータを含んでいることを入力します.各グループのデータの第1行は2つの正整です数、n kは、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を表す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域(データ保証余分な空白行または空白列が発生しないこと)を表す.Outputは、データのセットごとに、1行の出力を与え、配置されたシナリオ数Cを出力する(データ保証C<2^31).Sample Input 2 1
.
.# 4 4 …# ..#. .#..

-1-1 Sample Output 2 1と八皇后の問題差は多くなく、最初の行の最初から検索を開始し、その位置がその列にマークされず碁盤である場合、ここに駒を置いてマークし、行ごとに列が衝突できないため、次の行を検索し、駒数に1を加える.毎回検索する前に駒が切れたかどうかを判断し、使い終わったらシナリオ数に1を加えて直接返します.すべての検索が完了するまで、すべてのスキーマ数が取得されました.
#include
#include 
#include
using namespace std;
int n,k,ans;
char map[12][12];
int vis[12];
int DFS(int i,int cur)
{
    if(cur>=k) 
    {
        ans++;
        return 0;
    }
    int x,y;
    for(x=i;xfor(y=0;yif(!vis[y] && map[x][y]=='#')
            {
                vis[y]=1;
                DFS(x+1,cur+1);
                vis[y]=0;
            }
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&k)&&n!=-1)
    {
        ans=0;
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        for(int i=0;iscanf("%s",map[i]);
        DFS(0,0);
        printf("%d
"
,ans); } return 0; }