亚洲婷婷国产精品电影人久久,丁香五月综合久久激情,久久91精品综合国产首页

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右
5

int w,h,map[len][len],beg[2],min,step[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
6

bool flag[len][len];
7

bool 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

}
12

void 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

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

}
46

int 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 閱讀(245) 評論(0) 編輯收藏引用

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



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

pku 3009

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜