日韩午夜av,精品成人一区二区三区,在线看视频不卡

對于蝸牛來說，狂奔雖不代表極速，但展現(xiàn)的卻是一種拼盡全力的姿態(tài)........

pku 2488

2009年8月9日

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

分類：DFS

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

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

只有注冊用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



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