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
 4bool flag[max][max];
 5int step[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
 6int count,n,p,q,pos;
 7char path[5000];
 8bool 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}
31int 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 阅读(402) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜