The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢(mèng)令

導(dǎo)航

<

2009年3月

>

日

一

二

三

四

五

六

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

22

25

29

31

1

2

3

4

統(tǒng)計(jì)

隨筆 - 414
文章 - 13
評(píng)論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

搜索

閱讀排行榜

評(píng)論排行榜

POJ-1321 棋盤問題—即簡(jiǎn)化版八皇后問題(dfs深度優(yōu)先搜索+回溯）

這道題對(duì)我的啟發(fā)非常深，讓我對(duì)遞歸+回溯技術(shù)有了新的理解。我要向出題者致謝，也要感謝網(wǎng)上分享代碼的朋友

//參考了網(wǎng)絡(luò)上牛人的代碼

#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 閱讀(2052) 評(píng)論(1) 編輯收藏引用

評(píng)論

# re: POJ-1321 棋盤問題—即簡(jiǎn)化版八皇后問題(dfs深度優(yōu)先搜索+回溯）[未登錄] 2009-03-09 22:12 Leon

跟著你的順序，也做一做PoJ上面的題目。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理