27:鸣人和佐助
描述
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
输入
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。
输出
输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
样例输入
1
2
3
4
5
6
7
8
9
10
11
12
13
| 样例输入1
4 4 1
#@##
**##
###+
****
样例输入2
4 4 2
#@##
**##
###+
****
|
样例输出
解题：
之前是准备用二维数组来标记，但是这样的话不行，如果测试样例是这样的话:
1
2
3
4
| 3 6 1
@#****
*#*###
***##+
|
输出结果为-1,实际上正确结果应该是11。所以在标记数组上还要加一个查克拉的数量状态。
AC代码:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
int m, n, t;
char maze[210][210];
int vis[210][210][15] = {0};
struct node {
int x, y, t, step;
};
int flag;
node st, en, ne;
int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
int BFS() {
queue<node>q;
q.push(st);
while(!q.empty()) {
st = q.front();
q.pop();
if(st.x == en.x && st.y == en.y) {
flag = 1;
return st.step;
}
for(int i = 0; i < 4; i++) {
ne.x = st.x + dir[i][0];
ne.y = st.y + dir[i][1];
if(ne.x >= 1 && ne.x <= m && ne.y >= 1 && ne.y <= n) {
if(maze[ne.x][ne.y] == '#' && st.t >= 1 && !vis[ne.x][ne.y][st.t-1]) {
ne.t = st.t - 1;
ne.step = st.step + 1;
q.push(ne);
vis[ne.x][ne.y][ne.t] = 1;
}
else if(maze[ne.x][ne.y] != '#' && !vis[ne.x][ne.y][st.t]) {
ne.t = st.t;
ne.step = st.step + 1;
q.push(ne);
vis[ne.x][ne.y][ne.t] = 1;
}
}
}
}
}
int main() {
cin>>m>>n>>t;
flag = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
cin>>maze[i][j];
if(maze[i][j] == '@') {
st.x = i;
st.y = j;
st.t = t;
st.step = 0;
vis[st.x][st.y][t] = 1;
}
else if(maze[i][j] == '+') {
en.x = i;
en.y = j;
}
}
}
int ans = BFS();
if(flag) cout<<ans<<endl;
else cout<<-1<<endl;
return 0;
}
|
