欧美综合77777色婷婷,亚洲精品一区二区在线,亚洲素人一区二区

pku 2488

2009年8月9日

題目鏈接：PKU 2488 A Knight's Journey

分類：DFS

題目分析與算法原型
這道題目就是一個騎士周游問題，問按照給你的走法能否從某個點出發不重復走遍棋盤每個點........直接DFS即可，因為題目要求行號用字母'A'~'Z'表示，列號用阿拉伯數字表示，走的路線是按字典序輸出，對于這些其實也好辦，我們可以定義這樣一個行走路線step[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}，而且出發點從（1，1）開始（不難想到，若從該點找不到可行路線，那么其他點出發也是找不到的），這樣找到的路線一定是字典序最小的，題目要求輸出路線，其實用一個字符數組倒著存，到時候倒著輸出即可了，呵呵..........

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define max 50
4

bool flag[max][max];
5

int step[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
6

int count,n,p,q,pos;
7

char path[5000];
8

bool dfs(int x,int y)
9

{
10

int i;
11

if(count==p*q)return true;
12

for(i=0;i<8;i++)
13

{
14

int px=x+step[i][0],py=y+step[i][1];
15

if(px>=1&&px<=q&&py>=1&&py<=p&&!flag[px][py])
16

{
17

count++;
18

flag[px][py]=true;
19

if(dfs(px,py))
20

{
21

path[pos++]=py+'0';
22

path[pos++]=px+64;
23

return true;
24

}
25

flag[px][py]=false;
26

count--;
27

}
28

}
29

return false;
30

}
31

int main()
32

{
33

int ccase=1,i;
34

scanf("%d",&n);
35

while(n--)
36

{
37

memset(flag,false,sizeof(flag));
38

count=1;
39

flag[1][1]=true;
40

pos=0;
41

scanf("%d%d",&p,&q);
42

printf("Scenario #%d:\n",ccase++);
43

if(dfs(1,1))
44

{
45

path[pos++]='1';
46

path[pos++]='A';
47

for(i=pos-1;i>=0;i--)printf("%c",path[i]);
48

printf("\n");
49

}
50

else printf("impossible\n");
51

printf("\n");
52

}
53

return 1;
54

}

posted on 2009-08-09 15:58 蝸牛也Coding 閱讀(383) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 2488

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜