poj_1321_递归基础题

题目描述：

   n*n棋盘，其中部分格子有效，部分格子无效。放置k个皇后，保证行，列上不超过1个皇后。

解题思路：

   同八皇后。。比那个还简单。

代码：

#include <stdio.h>
#include <stdlib.h>
#define N 9

int G[N][N], count, fr[N], fc[N], n, k;

void find_solution(int num, int row)
{
   int i,j;
   if(row == n){
      if(num == k)
         count ++;
   }else{
      for(j=0;j<n;j++)
         if(G[row][j]==1 && fr[row]==0 && fc[j]==0){
            num++;
            fr[row] = 1;
            fc[j] = 1;
            //printf("选择[%d,%d]点.\n",row,j);
            find_solution(num, row+1);
            //printf("撤销[%d,%d]点.\n",row,j);
            fr[row] = 0;
            fc[j] = 0;
            num --;
         }
      find_solution(num, row+1);
   }  
}

main()
{
   char str[N];
   int i,j;
   scanf("%d %d",&n, &k);
   while(n!=-1){
       for(i=0;i<n;i++){
          scanf("%s",str);
          for(j=0;j<n;j++){
             if(str[j] == '#')
                G[i][j] = 1;
             else
                G[i][j] = 0;
          }
       }
       count = 0;
       memset(fr,0,sizeof(fr));
       memset(fc,0,sizeof(fc));
       find_solution(0,0);
       printf("%d\n",count);
       scanf("%d %d",&n, &k);
   }
  
   system("pause");
   return 0;
}