POJ_1321——碁盤問題、遡及+枝切り

Description
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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

 1 #include <cstdio>

 2 #include <cstring>

 3 int n,k,ans,mark[9];

 4 char map[9][9];

 5 void DFS(int k,int r)

 6 {

 7     if(k==0)

 8         {

 9             ans++;

10             return;

11         }

12     for(int i=r;i<n-k+1;i++)//     k ，        

13         {                            //       n-k+1      

14             for(int j=0;j<n;j++)

15                 {

16                     if(mark[j]==0 && map[i][j]=='#')

17                         {

18                             mark[j] = 1;

19                             DFS(k-1,i+1);

20                             mark[j] = 0;

21                         }

22                 }

23         }

24 }

25 int main()

26 {

27     while(~scanf("%d%d",&n,&k) && n+k>0)

28         {

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

30                 {

31                     scanf("%s",map[i]);

32                 }

33             memset(mark,0,sizeof(mark));

34             ans=0;

35             DFS(k,0);

36             printf("%d
",ans);

37         }

38     return 0;

39 }