日韩亚洲精品视频,亚洲综合成人在线,国产日韩在线不卡

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

pku 3009

2009年8月10日

題目鏈接：PKU 3009 Curling 2.0

分類：一道經(jīng)典DFS

題目分析與算法原型
沒(méi)什么特別講的，直接dfs，沒(méi)加什么減枝的情況下，跑了250ms左右（暫時(shí)沒(méi)想到好的剪枝策略）.........看到這題之后思路比較清晰，對(duì)于每個(gè)位置，枚舉上，下，左，右四個(gè)方向，對(duì)于每個(gè)方向若沒(méi)有相鄰的障礙物則表示可以從這個(gè)方向丟，那么一直從這個(gè)方向找，一直到遇到障礙，則從這個(gè)障礙的位置繼續(xù)dfs,若出了板子，表示該方向不可丟，繼續(xù)下個(gè)方向的判斷，若當(dāng)前次數(shù)大于10次則返回，若在10之內(nèi)到達(dá)了終點(diǎn)并且所有次數(shù)比當(dāng)前最小的次數(shù)還小，則更新最小次數(shù)...........

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

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

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

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



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