久久免费午夜影院,午夜电影亚洲,欧美日韩三区

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

pku 3083

2009年8月10日

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

分類：DFS+BFS

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

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define max 45
4

//left,right,ll,rr數組中下標對應的0,1,2,3分別表示當前方向為上，左（右），下，右（左）
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

13

struct node
14

{
15

int x,y,step;
16

}queue[max*max];
17

18

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

// 當前方向向左或右旋轉數組，前進一步,當前方向，上次的方向，當前的坐標
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)//往左轉過來的
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)//往右轉過來的
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

57

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

只有注冊用戶登錄后才能發表評論。




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

<

2009年7月

>

日

一

二

三

四

五

六

28

29

30

1

2

3

4

5

6

7

8

9

10

11

14

16

20

22

27

28

29

30

31

1

2

3

4

5

6

7

8

統計

隨筆 - 78
文章 - 0
評論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 95166
排名 - 261

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 3083

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜