poj 1321棋盘问题

棋盘问题
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17920 Accepted: 8878

Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output

2
1
Source
就是简单的深搜，数据小，暴力直接过

就是简单的深搜，数据小，暴力直接过

#include 
#include 
#include 
using namespace std; 
int n,m,sum,map[10][10],visit[10][10]; 
void bfs(int i,int j,int floor,int num) 
{ 
    int ii,jj,x,y; 
    bool zhe,k; 
    if(n-i+numn||num>m) 
        return ; 
 
    if((floor==n)||(num==m)) 
    { 
        //printf("%d i%d j%dnum%d\n",i,j,num,floor); 
        if(num==m) 
            sum++; 
        return ; 
    } 
     
    ii=i; 
    k=true; 
    for(jj=0;jj=0) 
        { 
         
            if(visit[x][y]) 
            { 
                zhe=false; 
                break; 
         
            } 
     
        } 
        x=ii;y=jj; 
        while(zhe&&(x--)>=0) 
        { 
             
            if(visit[x][y]) 
            { 
             
                zhe=false; 
                break; 
            } 
        } 
        if(zhe) 
        { 
            k=false; 
            visit[ii][jj]=1; 
            bfs(i+1,0,floor+1,num+1); 
            visit[ii][jj]=0; 
 
        } 
         
    } 
 
     
        bfs(i+1,0,floor+1,num); 
     
 
} 
int main () 
{ 
 
    int i,j; 
    char c; 
    char str[100]; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        gets(str); 
        if(n==-1&&m==-1) 
            break; 
        for(i=0;i
#include
#include
using namespace std;
int n,m,sum,map[10][10],visit[10][10];
void bfs(int i,int j,int floor,int num)
{
 int ii,jj,x,y;
 bool zhe,k;
 if(n-i+numn||num>m)
  return ;

 if((floor==n)||(num==m))
 {
  //printf("%d i%d j%dnum%d\n",i,j,num,floor);
  if(num==m)
   sum++;
  return ;
 }
 
 ii=i;
 k=true;
 for(jj=0;jj=0)
  {
  
   if(visit[x][y])
   {
    zhe=false;
    break;
  
   }
 
  }
  x=ii;y=jj;
  while(zhe&&(x--)>=0)
  {
   
   if(visit[x][y])
   {
   
    zhe=false;
    break;
   }
  }
  if(zhe)
  {
   k=false;
   visit[ii][jj]=1;
   bfs(i+1,0,floor+1,num+1);
   visit[ii][jj]=0;

  }
  
 }

 
  bfs(i+1,0,floor+1,num);
 

}
int main ()
{

 int i,j;
 char c;
 char str[100];
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  gets(str);
  if(n==-1&&m==-1)
   break;
  for(i=0;i