pku 3009

2009年8月10日

题目链接：PKU 3009 Curling 2.0

分类：一道经典DFS

题目分析与算法原型
         没什么特别讲的，直接dfs，没加什么减枝的情况下，跑了250ms左右（暂时没想到好的剪枝策略）.........看到这题之后思路比较清晰，对于每个位置，枚举上，下，左，右四个方向，对于每个方向若没有相邻的障碍物则表示可以从这个方向丢，那么一直从这个方向找，一直到遇到障碍，则从这个障碍的位置继续dfs,若出了板子，表示该方向不可丢，继续下个方向的判断，若当前次数大于10次则返回，若在10之内到达了终点并且所有次数比当前最小的次数还小，则更新最小次数...........


Code:

 1#include<stdio.h>
 2#include<string.h>
 3#define len 25
 4#define max 0x7fffffff                //0上，1下，2左，3右                                             
 5int w,h,map[len][len],beg[2],min,step[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 6bool flag[len][len];
 7bool check(int x,int y)
 8{
 9    if(x>=0&&x<=h-1&&y>=0&&y<=w-1)return true;
10    else return false;
11}
12void dfs(int count,int x,int y)
13{
14    int i,px,py;
15    if(count>10)return;
16    for(i=0;i<4;i++)
17    {
18        px=x+step[i][0];
19        py=y+step[i][1];
20        
21        if(!flag[px][py]&&check(px,py))
22        {    
23            while(map[px][py]!=3&&!flag[px][py]&&check(px,py))
24            {
25                px+=step[i][0];
26                py+=step[i][1];
27            }
28            if(check(px,py))
29            {
30                if(flag[px][py])
31                {
32                    flag[px][py]=false;
33                    dfs(count+1,px-step[i][0],py-step[i][1]);
34                    flag[px][py]=true;
35                }
36                else
37                {
38                    if(count+1<=10&&count<min)min=count+1;
39                    return ;
40                }
41            }
42        }
43    }
44    return ;
45}
46int main()
47{
48    int i,j;
49    while(scanf("%d%d",&w,&h)!=EOF)
50    {
51        if(!w&&!h)break;
52        memset(flag,false,sizeof(flag));
53        for(i=0;i<h;i++)
54            for(j=0;j<w;j++)
55            {
56                scanf("%d",&map[i][j]);
57                if(map[i][j]==2)
58                {
59                    beg[0]=i;
60                    beg[1]=j;
61                }
62                else if(map[i][j]==1)flag[i][j]=true;
63            }
64            min=max;
65            dfs(0,beg[0],beg[1]);
66            if(min<max)printf("%d\n",min);
67            else printf("-1\n");
68    }
69    return 1;
70}

posted on 2009-08-10 20:27 蜗牛也Coding 阅读(277) 评论(0)  编辑 收藏 引用


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


<2009年9月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜