The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ-1321 棋盘问题—即简化版八皇后问题(dfs深度优先搜索+回溯）

这道题对我的启发非常深，让我对递归+回溯技术有了新的理解。我要向出题者致谢，也要感谢网上分享代码的朋友

//参考了网络上牛人的代码
#include <iostream>
#include <algorithm>
using namespace std;


bool row[9];
bool line[9];
bool map[9][9];
int ans;
int sum;
int n,k;

bool check(int i,int j)
{
    if(map[i][j]&&row[i]&&line[j])return 1;
    else return 0;
}

void dfs(int r)
{
    if(sum==k){ans++;return;}
    if(r==n+1)return;
    for(int i=1;i<=n;i++)
    {
        if(check(r,i))
        {
            row[r]=0;line[i]=0;
            sum++;
            dfs(r+1);
            sum--;
            row[r]=1;line[i]=1;
        }
    }
    dfs(r+1);
}


int main()
{
    int i,j;
    char c;
    while(cin>>n>>k)
    {
        if(n==-1&&k==-1)
            break;
        sum=0;
        ans=0;
        
        for(i=1;i<=n;i++)
        {
            getchar();
            row[i]=1;line[i]=1;
            for(j=1;j<=n;j++)
            {
                scanf("%c",&c);
                if(c=='#')map[i][j]=1;
                else map[i][j]=0;
            }
        }
        dfs(1);
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

posted on 2009-03-07 17:44 abilitytao 阅读(2000) 评论(1)  编辑 收藏 引用

评论

# re: POJ-1321 棋盘问题—即简化版八皇后问题(dfs深度优先搜索+回溯）[未登录] 2009-03-09 22:12 Leon

跟着你的顺序，也做一做PoJ上面的题目。  回复  更多评论   


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