kuangbin专题 专题二 搜索进阶 Escape HDU
题目链接：https://vjudge.net/problem/HDU-3533
题目分析：
1.人不能经过碉堡;
2.敌军碉堡可能建到我军基地
3.子弹碰到碉堡就没了，说明子弹会被别的城堡给拦截下来，不能透过其他城堡，导致攻击距离减小，这里预处理时要注意
4.人拥有的能量相当于最大时间
5.人可以禁止不动
该题目就是预处理比较麻烦，bfs函数在预处理之后就中规中矩，预处理要细心。。。为了剪枝，可以用曼哈顿距离判断，曼哈顿距离其实很简单，可以百度一下
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <string.h>
5 #include <queue>
6 #include <algorithm>
7 using namespace std;
8
9 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
10 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
11 #define per(i,j,k) for(int i = (j); i >= (k); i--)
12 #define per__(i,j,k) for(int i = (j); i > (k); i--)
13
14 const int N = 110;
15 int mv_x[] = { 0, 0, 0, -1, 1 }; // （1）
16 int mv_y[] = { 0, 1, -1, 0, 0 }; // （2） （1） + （2） 上，下，左，右，不动
17 bool vis[N][N][1010]; //是否访问标记
18 bool shot[N][N][1010]; //子弹分布标记
19 bool mp[N][N]; //城堡坐标标记
20 int n, m, k, d;
21
22 struct People{
23 int x, y, cost;//花费
24 };
25
26 struct Castle{
27 char c;
28 int t, v, x, y;
29 int end; //能攻击到的最远坐标
30 };
31
32 Castle castle[N];
33
34 //标记城堡位置
35 inline void init_Castle(){
36
37 rep__(i, 0, k){
38
39 cin >> castle[i].c >> castle[i].t >> castle[i].v >> castle[i].x >> castle[i].y;
40
41 mp[castle[i].x][castle[i].y] = true;
42 }
43 }
44
45 //设置城堡攻击范围
46 void set_Castle_dis(){
47
48
49 //遍历地图，遇到城堡就结束判断能攻击到的最后坐标
50 rep__(i, 0, k){
51 int j;
52 if (castle[i].c == 'W'){
53
54 castle[i].end = castle[i].y;
55 for (j = castle[i].y - 1; !mp[castle[i].x][j] && j >= 0; j--) --castle[i].end;
56
57 }
58 else if (castle[i].c == 'E'){
59
60 castle[i].end = castle[i].y;
61 for (j = castle[i].y + 1; !mp[castle[i].x][j] && j <= m; j++) ++castle[i].end;
62
63 }
64 else if (castle[i].c == 'N'){
65
66 castle[i].end = castle[i].x;
67 for (j = castle[i].x - 1; !mp[j][castle[i].y] && j >= 0; j--) --castle[i].end;
68
69 }
70 else if (castle[i].c == 'S'){
71
72 castle[i].end = castle[i].x;
73 for (j = castle[i].x + 1; !mp[j][castle[i].y] && j <= n; j++) ++castle[i].end;
74
75 }
76 }
77 }
78
79 //设置子弹攻击分布图
80 void init_shot(){
81
82
83 //在每个城市子弹攻击范围进行子弹分布处理
84 rep__(i, 0, k){
85 int start_t = 0;
86 int j;
87
88 if (castle[i].c == 'W'){
89
90 for (j = castle[i].y - castle[i].v, start_t = 1; j >= castle[i].end; j -= castle[i].v,
start_t += 1){
91 for (int p = start_t; p <= d; p += castle[i].t)
92 shot[castle[i].x][j][p] = true;
93 }
94 }
95 else if (castle[i].c == 'E'){
96
97 for (j = castle[i].y + castle[i].v, start_t = 1; j <= castle[i].end; j += castle[i].v,
start_t += 1){
98 for (int p = start_t; p <= d; p += castle[i].t)
99 shot[castle[i].x][j][p] = true;
100 }
101 }
102 else if (castle[i].c == 'N'){
103
104 for (j = castle[i].x - castle[i].v, start_t = 1; j >= castle[i].end; j -= castle[i].v,
start_t += 1){
105 for (int p = start_t; p <= d; p += castle[i].t)
106 shot[j][castle[i].y][p] = true;
107 }
108 }
109 else if (castle[i].c == 'S'){
110 for (j = castle[i].x + castle[i].v, start_t = 1; j <= castle[i].end; j += castle[i].v,
start_t += 1){
111 for (int p = start_t; p <= d; p += castle[i].t)
112 shot[j][castle[i].y][p] = true;
113 }
114 }
115 }
116 }
117
118 //预处理
119 void pre(){
120
121 memset(vis, 0, sizeof(vis));
122 memset(shot, 0, sizeof(shot));
123 memset(mp, 0, sizeof(mp));
124
125 init_Castle(); //标记城堡位置
126 set_Castle_dis(); //设置城堡攻击范围
127 init_shot(); //设置子弹攻击分布图
128 }
129
130 //判断是否越界
131 inline bool check(int x, int y){
132 return x >= 0 && x <= n && y >= 0 && y <= m;
133 }
134
135 //曼哈顿距离优化
136 inline bool ok(int x, int y, int cost){
137 return (m + n - x - y <= d - cost);
138 }
139
140 void bfs(){
141
142 if (mp[0][0]) { cout << "Bad luck!" << endl; return; }
143
144 queue<People> que;
145 que.push(People{ 0, 0, 0 });
146
147 while (!que.empty()){
148
149 People tmp = que.front();
150 que.pop();
151
152 rep__(p, 0, 5){
153 int dx = tmp.x + mv_x[p];
154 int dy = tmp.y + mv_y[p];
155 int dcost = tmp.cost + 1;
156
157 //没越界 没被访问过 不是城堡的位置 子弹在这个时刻不攻击这个点 曼哈顿判断能否到达终点
158 if (check(dx, dy) && !vis[dx][dy][dcost] && !mp[dx][dy]
&& !shot[dx][dy][dcost] && ok(dx, dy, dcost)){
159
160 if (dx == n && dy == m){ cout << dcost << endl; return; }
161 vis[dx][dy][dcost] = true;
162 que.push(People{ dx, dy, dcost });
163 }
164 }
165 }
166
167 cout << "Bad luck!" << endl;
168 }
169
170 int main(){
171
172 while (cin >> n >> m >> k >> d){
173 pre();
174 bfs();
175 }
176
177
178 return 0;
179 }