夏休み合宿第3週第2ステージF-碁盤問題検索

19177 ワード

F-チェッカーの問題
Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u
Submit 
Status
Description
1つの所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.並べ替え時に任意の2つの駒が碁盤の中の同一行または同一列に置かれないことを要求する場合は、所定の形状と大きさの碁盤に対してk個の駒を並べたすべての実行可能な並べ替えスキームCをプログラミングして解いてください.
Input
複数セットのテストデータを入力します. 
各グループのデータの最初の行は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

分析:
この問題は私に長い時間を費やして、ずっと正確に提出していないで、プログラムは2つの多重再帰を使って、1つは制御プログラムの横行が下へ循環して、1つは制御プログラムの縦行が下へ循環して、すべての条件を見つけます.
依然として再帰で、依然として深く探して、依然としてとても理解しにくくて、依然としてとても人を苦しめます
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n,k,s,t,v[10];
char a[10][10];
void DFS(int i)
{
    if(t==k)
    {
        s++;
        return ;
    }
    if(i>=n)
        return ;
    for(int  j=0; j<n; j++)
        if(v[j]==0&&a[i][j]=='#')
        {
            v[j]=1;
            t++;
            DFS(i+1);
            v[j]=0;
            t--;
        }
   DFS(i+1);
}
int main()
{
    int i,j;
      while(scanf("%d %d",&n,&k)&&(n!=-1&&k!=-1))
    {
        getchar();
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
                scanf("%c",&a[i][j]);
            getchar();
        }
        memset(v,0,sizeof(v));
        s=0,t=0;
        DFS(0);
        printf("%d
",s); } return 0; }