99久久精品免费观看国产,精品国产乱码久久久久软件,狠狠综合久久综合88亚洲

pku 3083

2009年8月10日

題目鏈接：PKU 3083 Children of the Candy Corn

分類：DFS+BFS

題目分析與算法原型
這題難度也不算太大，但是卻寫(xiě)了很久，也調(diào)了很久，主要就是順時(shí)針和逆時(shí)針的DFS的坐標(biāo)處理，看了Discuss里面有大牛的代碼到了8k，心中不免有些膽顫，于是就多花了時(shí)間思考如何寫(xiě)的精簡(jiǎn)一些，然而事實(shí)上也用了將近120行左右代碼（算不上精簡(jiǎn)了），呵呵，主要就是DFS那塊（BFS基本沒(méi)問(wèn)題），對(duì)于每次，我用了兩個(gè)數(shù)組，兩個(gè)方向（一個(gè)是當(dāng)前的另一個(gè)是上次的），作為參數(shù)來(lái)判斷下次的坐標(biāo)，拿逆時(shí)針轉(zhuǎn)的來(lái)說(shuō)，對(duì)于當(dāng)前的點(diǎn)若為‘#’則下次鐵定向右轉(zhuǎn)（對(duì)于當(dāng)前方向來(lái)說(shuō)），順時(shí)針的情況剛好相反，個(gè)人感覺(jué)自己的DFS函數(shù)還不夠簡(jiǎn)練，相信有更好的記錄方法，呵呵

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define max 45
4

//left,right,ll,rr數(shù)組中下標(biāo)對(duì)應(yīng)的0,1,2,3分別表示當(dāng)前方向?yàn)樯希螅ㄓ遥拢遥ㄗ螅?/span>
5

int left[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
6

int right[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
7

int ll[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
8

int rr[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
9

int step[4][2]={{-1,0},{1,0},{0,-1},{0,1}},n,w,h,beg[2],res1,res2,res3,min,pub;
10

char map[max][max];
11

bool flag[max][max];
12

struct node
14

{
15

int x,y,step;
16

}queue[max*max];
17

bool check(int x,int y)
19

{
20

if(x>=0&&x<=h-1&&y>=0&&y<=w-1)return true;
21

else return false;
22

}
23

// 當(dāng)前方向向左或右旋轉(zhuǎn)數(shù)組，前進(jìn)一步,當(dāng)前方向，上次的方向，當(dāng)前的坐標(biāo)
24

void dfs(int d[4][2],int dd[4][2],int now,int last,int pos[2])
25

{
26

int p[2];
27

if(map[pos[0]][pos[1]]=='E')
28

{
29

pub++;
30

return ;
31

}
32

if(map[pos[0]][pos[1]]=='S'||map[pos[0]][pos[1]]=='.')
33

{
34

pub++;
35

p[0]=pos[0]+d[now][0];
36

p[1]=pos[1]+d[now][1];
37

dfs(d,dd,(now+1)%4,now,p);
38

}
39

else if(map[pos[0]][pos[1]]=='#'||!check(pos[0],pos[1]))
40

{
41

int kk=(now-1+4)%4;
42

if(now==(last+1)%4)//往左轉(zhuǎn)過(guò)來(lái)的
43

{
44

p[0]=pos[0]-d[last][0]+dd[kk][0];
45

p[1]=pos[1]-d[last][1]+dd[kk][1];
46

}
47

else if(now==(last-1+4)%4)//往右轉(zhuǎn)過(guò)來(lái)的
48

{
49

p[0]=pos[0]+d[last][0]+dd[kk][0];
50

p[1]=pos[1]+d[last][1]+dd[kk][1];
51

}
52

dfs(d,dd,kk,now,p);
53

}
54

return ;
55

}
56

int bfs()
58

{
59

int i,front=0,rear=1;
60

queue[0].x=beg[0];
61

queue[0].y=beg[1];
62

queue[0].step=1;
63

flag[beg[0]][beg[1]]=true;
64

while(front<rear)
65

{
66

for(i=0;i<4;i++)
67

{
68

int x=queue[front].x,y=queue[front].y;
69

x+=step[i][0];
70

y+=step[i][1];
71

if(!flag[x][y]&&check(x,y)&&map[x][y]!='#')
72

{
73

flag[x][y]=true;
74

queue[rear].x=x;
75

queue[rear].y=y;
76

queue[rear].step=queue[front].step+1;
77

if(map[x][y]=='E')return queue[rear].step;
78

rear++;
79

}
80

}
81

front++;
82

}
83

}
84

int main()
85

{
86

int i,j,kk;
87

scanf("%d",&n);
88

while(n--)
89

{
90

scanf("%d%d",&w,&h);
91

memset(flag,false,sizeof(flag));
92

min=1;
93

for(i=0;i<h;i++)
94

for(j=0;j<w;j++)
95

{
96

scanf(" %c",&map[i][j]);
97

if(map[i][j]=='S')
98

{
99

beg[0]=i;
100

beg[1]=j;
101

}
102

}
103

if(beg[0]==h-1)kk=0; //上
104

else if(beg[0]==0)kk=1; //下
105

else if(beg[1]==w-1)kk=2; //左
106

else if(beg[1]==0)kk=3; //右
107

pub=0;
108

dfs(left,ll,kk,(kk-1+4)%4,beg);
109

res1=pub;
110

pub=0;
111

if(kk==3)kk=1;
112

else if(kk==1)kk=3;
113

dfs(right,rr,kk,(kk-1+4)%4,beg);
114

res2=pub;
115

res3=bfs();
116

printf("%d %d %d\n",res1,res2,res3);
117

}
118

return 1;
119

}
120

121

posted on 2009-08-10 18:01 蝸牛也Coding 閱讀(325) 評(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 管理

pku 3083

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜