# hdu 3442 Three Kingdoms

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 474    Accepted Submission(s): 185

本题其实并不难，有限队列再加广搜就能过，但是处理起来比较麻烦，稍微一点不注意就错了。我就错了好几次最后发现重用了变量（真是低级错误）。

```

1

#include

<

stdio.h

>

2

#include

<

string

.h

>

3

#include

<

queue

>

4

using

namespace

std;

5

struct

node

6

{

7

int

damage,x,y;

8

int

mark[

5

];

9

bool

operator

<

(

const

node

&

a)

const

10

{

11

return

a.damage

<

damage;

12

}

13

};

14

typedef

struct

tt

15

{

16

int

x,y,t;

17

}NODE;

18

int

dir[

4

][

2

]

=

{{

1

,

0

},{

0

,

1

},{

-

1

,

0

},{

0

,

-

1

}};

19

node cur,next;

20

int

n,m,tag;NODE cur1,next1;

21

char

a[

55

][

55

];

int

mark[

55

][

55

],mark1[

55

][

55

];

22

void

bfs(

int

x,

int

y)

23

{

24

priority_queue

<

node

>

qu;

25

cur.x

=

x;cur.y

=

y;cur.damage

=

0

;

26

queue

<

NODE

>

q;

27

int

i,j;

28

for

(i

=

0

;i

<

5

;i

++

)

29

{

30

cur.mark[i]

=

0

;

31

}

32

qu.push(cur);

33

while

(

!

qu.empty ())

34

{

35

cur

=

qu.top ();

36

qu.pop();

37

if

(a[cur.x][cur.y]

==

'

!

'

)

38

{

39

tag

=

1

;

40

return

;

41

}

42

for

(i

=

0

;i

<

4

;i

++

)

43

{

44

next.x

=

cur.x

+

dir[i][

0

];

45

next.y

=

cur.y

+

dir[i][

1

];

46

if

(next.x

>=

1

&&

next.x

<=

n

&&

next.y

>=

1

&&

next.y

<=

m

&&

a[next.x][next.y]

!=

'

#

'

&&

a[next.x][next.y]

!=

'

A

'

&&

a[next.x][next.y]

!=

'

B

'

&&

a[next.x][next.y]

!=

'

D

'

&&

a[next.x][next.y]

!=

'

E

'

)

47

{

48

next.damage

=

cur.damage ;

49

for

(j

=

0

;j

<

5

;j

++

)

50

{

51

next.mark[j]

=

cur.mark[j];

52

}

53

if

(a[next.x][next.y]

==

'

C

'

&&

cur.mark[

2

]

==

0

)

54

{

55

next.damage

+=

3

;

56

next.mark[

2

]

=

1

;

57

}

58

memset(mark1,

0

,

sizeof

(mark1));

59

while

(

!

q.empty ())

60

q.pop ();

61

cur1.x

=

next.x;

62

cur1.y

=

next.y;

63

cur1.t

=

0

;

64

q.push(cur1);

65

while

(

!

q.empty ())

66

{

67

cur1

=

q.front ();

68

q.pop();

69

if

(cur1.t

>

3

)

70

break

;

71

if

(next.mark[

0

]

==

0

&&

cur1.t

<=

2

&&

a[cur1.x][cur1.y]

==

'

A

'

)

72

{

73

next.damage

+=

1

;

74

next.mark[

0

]

=

1

;

75

}

76

if

(next.mark[

1

]

==

0

&&

cur1.t

<=

3

&&

a[cur1.x][cur1.y]

==

'

B

'

)

77

{

78

next.damage

+=

2

;

79

next.mark[

1

]

=

1

;

80

}

81

if

(next.mark[

3

]

==

0

&&

cur1.t

<=

2

&&

a[cur1.x][cur1.y]

==

'

D

'

)

82

{

83

next.damage

+=

4

;

84

next.mark[

3

]

=

1

;

85

}

86

if

(next.mark[

4

]

==

0

&&

cur1.t

<=

1

&&

a[cur1.x][cur1.y]

==

'

E

'

)

87

{

88

next.damage

+=

5

;

89

next.mark [

4

]

=

1

;

90

}

91

for

(j

=

0

;j

<=

4

;j

++

)

92

{

93

next1.x

=

cur1.x

+

dir[j][

0

];

94

next1.y

=

cur1.y

+

dir[j][

1

];

95

if

(next1.x

>=

1

&&

next1.x

<=

n

&&

next1.y

>=

1

&&

next1.y

<=

m

&&!

mark1[next1.x][next1.y])

96

{

97

mark1[next1.x][next1.y]

=

1

;

98

next1.t

=

cur1.t

+

1

;

99

q.push(next1);

100

}

101

}

102

}

103

if

(mark[next.x][next.y]

>

next.damage)

104

{

105

mark[next.x][next.y]

=

next.damage;

106

qu.push(next);

107

}

108

}

109

}

110

}

111

}

112

int

main()

113

{

114

int

t,i,j,sx,sy,count

=

0

;

115

scanf(

"

%d

"

,

&

t);

116

while

(t

--

)

117

{

118

count

++

;tag

=

0

;

119

scanf(

"

%d%d

"

,

&

n,

&

m);

120

for

(i

=

1

;i

<=

n;i

++

)

121

{

122

getchar();

123

for

(j

=

1

;j

<=

m;j

++

)

124

{

125

scanf(

"

%c

"

,

&

a[i][j]);

126

mark[i][j]

=

0xfffffff

;

127

if

(a[i][j]

==

'

\$

'

)

128

{

129

sx

=

i;sy

=

j;

130

}

131

}

132

}

133

bfs(sx,sy);

134

if

(tag)

135

printf(

"

Case %d: %d\n

"

,count,cur.damage );

136

else

137

printf(

"

Case %d: %d\n

"

,count,

-

1

);

138

}

139

return

0

;

140

}

141

```

hdu 3442 Three Kingdoms

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊