- 题目链接：http://bailian.openjudge.cn/practice/4115/
- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
-
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
- 输入
-
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。 - 输出
- 输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
- 样例输入
-
样例输入1 4 4 1 #@## **## ###+ **** 样例输入2 4 4 2 #@## **## ###+ ****
- 样例输出
-
样例输出1 6 样例输出2 4
1 #include <iostream> 2 #include <queue> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 struct point 8 { 9 int x, y, ckl, time; 10 point (int xx,int yy, int cc, int tt):x(xx), y(yy), ckl(cc), time(tt){}; 11 }; 12 13 int r,c,t; 14 int min_time = 1 << 30; 15 int dx[4] = {0, 0, 1, -1}; 16 int dy[4] = {1, -1, 0, 0}; 17 char mp[210][210]; 18 bool visited[210][210][11]; 19 20 int bfs(int x, int y, int ex, int ey, int t) 21 { 22 queue<point> q; 23 q.push(point(x, y, t, 0)); 24 while (!q.empty()) 25 { 26 point temp = q.front(); 27 q.pop(); 28 for (int i = 0; i < 4; i++) 29 { 30 int sx = temp.x + dx[i]; 31 int sy = temp.y + dy[i]; 32 if (sx == ex && sy == ey) 33 { 34 min_time = temp.time + 1; 35 return true; 36 } 37 if (mp[sx][sy] == '*') 38 { 39 if (sx >= 0 && sx < r && sy >= 0 && sy < c && !visited[sx][sy][temp.ckl]) 40 { 41 visited[sx][sy][temp.ckl] = true; 42 q.push(point(sx, sy, temp.ckl, temp.time + 1)); 43 } 44 } 45 if (mp[sx][sy] == '#') 46 { 47 if (sx >= 0 && sx < r && sy >= 0 && sy < c && !visited[sx][sy][temp.ckl - 1] && temp.ckl > 0) 48 { 49 visited[sx][sy][temp.ckl - 1] = true; 50 q.push(point(sx, sy, temp.ckl - 1, temp.time + 1)); 51 } 52 } 53 } 54 } 55 return false; 56 } 57 58 int main(){ 59 cin >> r >> c >> t; 60 int x, y, ex, ey; 61 memset(visited, 0, sizeof(visited)); 62 for (int i = 0; i < r; i++) 63 { 64 for (int j = 0; j < c; j++) 65 { 66 cin >> mp[i][j]; 67 if(mp[i][j] == '@') 68 { 69 x = i; 70 y = j; 71 mp[i][j] = '*'; 72 } 73 if(mp[i][j] == '+') 74 { 75 ex = i; 76 ey = j; 77 mp[i][j] = '*'; 78 } 79 } 80 } 81 if (bfs(x, y, ex, ey, t)) 82 cout << min_time << endl; 83 else 84 cout << "-1" <<endl; 85 }
参考：
分析http://www.cnblogs.com/huibixiaoxing/p/6537769.html
代码http://blog.csdn.net/u010524510/article/details/47148665
