希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

递归深搜——poj 1321,类八皇后

#include<cstdio>
#include
<cstdlib>
#include
<cmath>
#include
<string>

int k,n,ct,num_p,col[10],ans[92][10],row[10];//col记录第i行放棋子所在的列号

char bd[10][10];//棋盘布局

void queen(int i)
{
    
int j,t;

    
if(num_p==k)//不同于八皇后,k不一定为8,有题目给出
    {
        
/*for(j=0;j<n;++j)记录可能方案情况,此题不要求
            ans[ct][j]=col[j]+1;
*/

        ct
++;
        
return ;
    }


    
if(i==n)return ;//少了此条件则n无限大
    for(j=0;j<n;++j)
    
{
            
if(bd[i][j]=='.')continue;
            
for(t=0;t<i;++t)
                
if(col[t]==j)break;
        
if(t==i)
        
{
            col[i]
=j;
            num_p
++;
            queen(i
+1);
            num_p
--;
            col[i]
=9;
        }

    }

    
if(k<n)//不同于八皇后,第i行可以不放棋子,故深搜多一条支路
    {
        
//num_p++;
        queen(i+1);
        
//num_p--;
    }

}

int main()
{
    
int i,j;
    
while(scanf("%d%d",&n,&k)==2&&n!=-1&&k!=-1)
    
{
        
for(i=0;i<n;++i)
        
{
            scanf(
"%s",bd[i]);
        }


        queen(
0);
        printf(
"%d\n",ct);
        ct
=0;
        memset(col,
0,sizeof(col));
        memset(row,
0,sizeof(row));
    }

    
return 0;
}

posted on 2011-08-04 19:08 拥梦的小鱼 阅读(719) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理