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 阅读(1932) 评论(1)  编辑 收藏 引用

评论

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

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


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