POJ 2488

http://acm.pku.edu.cn/JudgeOnline/problem?id=2488
这是一道深搜回溯的题目。我这个新手初次做深搜,浏览了无数大牛的解题报告,收获很大。我原来总以为是要用栈来存储结点,却没想到回溯如此简单。
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int n;
 4 int r,c;
 5 int ok;
 6 int visit[100][100];
 7 int px[50],py[50];
 8 int yy[8= {-1,1,-2,2,-2,2,-1,1};//在这就把输出字典顺序确定了
 9 int xx[8= {-2,-2,-1,-1,1,1,2,2};
10 
11 int isok(int x,int y)
12 {
13     return x >= 1 && x <= r && y >= 1 && y <= c;
14 }
15 
16 void dfs(int x,int y,int length);
17 int main()
18 {
19     scanf("%d",&n);
20     for(int i =1;i <= n;i++){
21         scanf("%d%d",&c,&r);
22         visit[1][1= 1;
23         ok = 0;
24         dfs(1,1,1);
25         printf("Scenario #%d:\n",i);
26         if(ok){
27             for(int j = 1;j <= r*c;j++){
28                 printf("%c",px[j]+'A'-1);
29                 printf("%d",py[j]);
30             }
31         }
32         else printf("impossible");
33         printf("\n\n");
34     }
35     system("pause");
36     return 0;
37         
38 }
39 void dfs(int x,int y,int length)
40 {
41     px[length] = x;
42     py[length] = y;
43     if(length == r*c){
44         ok = 1;
45         return;
46     }
47     for(int i = 0;i < 8;i++){
48         int tx = x + xx[i];
49         int ty = y + yy[i];
50         if(isok(tx,ty) && !visit[tx][ty] && !ok){
51             visit[tx][ty] = 1;
52             dfs(tx,ty,length+1);
53             visit[tx][ty] = 0;//巧妙,也是必须的
54         }
55     }
56 }
57 
code

posted on 2009-06-17 13:04 Johnnx 阅读(992) 评论(0)  编辑 收藏 引用


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


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜