希望的海洋

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 拥梦的小鱼 阅读(732) 评论(0)  编辑 收藏 引用 所属分类: POJ


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