gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

POJ 2435-- Navigating the City

1

#include <cstdio>
2

#include <cstring>
3

4

const int MAXE = 80;
5

const int MAXN = 60;
6

const int SIZE = 5000;
7

8

struct NODE
9

{
10

char m_cMark;
11

int m_pre;
12

int m_x, m_y;
13

}Q[SIZE];
14

15

int N, E, g_start_x, g_start_y, g_end;
16

char map[MAXN][MAXE];
17

bool visited[MAXN][MAXE];
18

19

void BFS()
20

{
21

int h = 0, t = 1;
22

NODE temp;
23

visited[g_start_x][g_start_y] = true;
24

Q[0].m_x = g_start_x;
25

Q[0].m_y = g_start_y;
26

27

while ( h <= t )
28

{
29

temp = Q[h];
30

31

if ( map[temp.m_x][temp.m_y] =='E' )
32

{
33

g_end = temp.m_pre;
34

break;
35

}
36

37

if ( temp.m_x > 0 && !visited[temp.m_x - 1][temp.m_y] )
38

{
39

visited[temp.m_x - 1][temp.m_y] = true;
40

Q[t].m_x = temp.m_x - 1;
41

Q[t].m_y = temp.m_y;
42

Q[t].m_pre = h;
43

Q[t].m_cMark = 'N';
44

if ( map[temp.m_x - 1][temp.m_y] == '+' )
45

Q[t].m_cMark = '+' ;
46

t++;
47

48

}
49

if ( temp.m_y + 1 < E && !visited[temp.m_x][temp.m_y + 1] )
50

{
51

visited[temp.m_x][temp.m_y + 1] = true;
52

Q[t].m_x = temp.m_x;
53

Q[t].m_y = temp.m_y + 1;
54

Q[t].m_pre = h;
55

Q[t].m_cMark = 'E';
56

if ( map[temp.m_x][temp.m_y + 1] == '+' )
57

Q[t].m_cMark = '+' ;
58

t++;
59

}
60

if ( temp.m_x + 1 < N && !visited[temp.m_x + 1][temp.m_y] )
61

{
62

visited[temp.m_x + 1][temp.m_y] = true;
63

Q[t].m_x = temp.m_x + 1;
64

Q[t].m_y = temp.m_y;
65

Q[t].m_pre = h;
66

Q[t].m_cMark = 'S';
67

if ( map[temp.m_x + 1][temp.m_y] == '+' )
68

Q[t].m_cMark = '+' ;
69

t++;
70

}
71

if ( temp.m_y > 0 && !visited[temp.m_x][temp.m_y - 1] )
72

{
73

visited[temp.m_x][temp.m_y - 1] = true;
74

Q[t].m_x = temp.m_x;
75

Q[t].m_y = temp.m_y - 1;
76

Q[t].m_pre = h;
77

Q[t].m_cMark = 'W';
78

if ( map[temp.m_x][temp.m_y - 1] == '+' )
79

Q[t].m_cMark = '+' ;
80

t++;
81

}
82

83

h++;
84

}
85

}
86

87

int main()
88

{
89

// freopen("1.txt", "r", stdin);
90

int i, j, len;
91

char ch, result[SIZE];
92

93

scanf("%d %d", &N, &E);
94

95

N = (N << 1) - 1, E = (E << 1) - 1;
96

97

memset(visited, 0, sizeof(visited));
98

getchar();
99

for ( i = 0; i < N; ++i )
100

{
101

for ( j = 0; j < E; ++j )
102

{
103

ch = getchar();
104

map[i][j] = ch;
105

if ( ch == 'S' )
106

{
107

g_start_x = i;
108

g_start_y = j;
109

}
110

else if ( ch == '.' )
111

{
112

visited[i][j] = true;
113

}
114

}
115

getchar();
116

}
117

118

BFS();
119

120

i = g_end, len = 0;
121

while ( i != 0 )
122

{
123

if ( Q[i].m_cMark != '+' )
124

{
125

result[len++] = Q[i].m_cMark;
126

}
127

i = Q[i].m_pre;
128

}
129

130

i = len - 1, j = 1;
131

132

len -= 2;
133

while ( len >= 0 )
134

{
135

if ( result[len] == result[i] ) {
136

j++;
137

}
138

else {
139

printf("%c %d\n", result[i], j);
140

i = len;
141

j = 1;
142

}
143

len--;
144

}
145

printf("%c %d\n", result[i], j);
146

147

return 0;
148

}

posted on 2009-04-02 14:39 巫閱讀(183) 評論(0) 編輯收藏引用所屬分類: 搜索

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


相關文章: POJ 2435-- Navigating the City POJ 2488(簡單的深搜)

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

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