当前位置:首页 > 开发 > Web前端 > DOM > 正文

hdu 3442 Three Kingdoms

发表于: 2015-11-13   作者:互联网   来源:转载   浏览次数:
dom
摘要: Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 474    Accepted Submission(s): 185    &n

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

    震惊

    震惊

编辑推荐
Three years old birthday Three years old birthday it to, but darkfall gold from the beginning
http://forums.ffshrine.org/f72/seven-kingdoms-i-ii-ancient-adversaries-game-45781/ Seven King
From http://www.notebooks.com/2010/01/17/three-ways-to-sync-browser-bookmarks/ Many people us
http://bbs.9ria.com/viewthread.php?tid=77910&extra=page%3D1%26amp%3Borderby%3Ddateline%26amp%
1,首先我们应该知道 three.js是做什么的? hree.js是JavaScript编写的WebGL第三方库。提供了非常多
1,首先我们应该知道 three.js是做什么的? hree.js是JavaScript编写的WebGL第三方库。提供了非常多
开始使用THREE.JS 译序 Three.js是一个伟大的开源WebGL库,WebGL允许JavaScript操作GPU,在浏览器端
[译] THREE.JS入门教程-1.开始使用THREE.JS 译序 Three.js是一个伟大的开源WebGL库,WebGL允许JavaS
Table of contents Introduction WCF service object instancing basics Per call instance mode Ho
今天终于搞定了Three20添加到项目中的方式,之前也弄过,但是不记得了,这次纪录下来,好记性不如烂
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号