首页 > 代码库 > NYOJ 284 坦克大战 bfs + 优先队列
NYOJ 284 坦克大战 bfs + 优先队列
这类带权的边的图,直接广搜不行,要加上优先队列,这样得到的结果才是最优的,这样每次先找权值最小的,代码如下
1 #include <stdio.h> 2 #include <iostream> 3 #include <queue> 4 #include <string.h> 5 using namespace std; 6 typedef struct Node{ 7 int x, y; 8 int step; 9 friend bool operator < (const Node &a, const Node &b) 10 { 11 return a.step > b.step; 12 } 13 }Node; 14 const int MAX = 300 + 5; 15 int N, M; 16 int Map[MAX][MAX]; 17 int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 18 Node s, e; 19 bool match(Node node)//判断是否到达终点 20 { 21 if (node.x == e.x && node.y == e.y) 22 return true; 23 return false; 24 } 25 bool check(Node node)//判断这个点是否能走 26 { 27 if (node.x < 0 || node.y < 0 || node.x >= N || node.y >= M || Map[node.x][node.y] == 0) 28 return false; 29 return true; 30 } 31 int bfs() 32 { 33 priority_queue<Node> q;//优先队列 34 q.push(s); 35 Node p1, p2; 36 while (!q.empty()) 37 { 38 p1 = q.top(); 39 q.pop(); 40 for (int i = 0; i < 4; i++) 41 { 42 p2.x = p1.x + next[i][0]; 43 p2.y = p1.y + next[i][1]; 44 p2.step = p1.step + Map[p2.x][p2.y]; 45 if (match(p2)) 46 { 47 return p2.step; 48 } 49 if (check(p2)) 50 { 51 Map[p2.x][p2.y] = 0; 52 Node v = p2; 53 q.push(v); 54 } 55 } 56 } 57 return -1; 58 } 59 int main() 60 { 61 char ch; 62 while (~scanf("%d%d", &N, &M) && N + M) 63 { 64 for (int i = 0; i < N; i++) 65 { 66 for (int j = 0; j < M; j++) 67 { 68 cin >> ch; 69 if (ch == ‘Y‘)//起点 70 { 71 s.x = i; 72 s.y = j; 73 s.step = 0; 74 Map[i][j] = 0; 75 } 76 else if (ch == ‘T‘)//终点 77 { 78 e.x = i; 79 e.y = j; 80 e.step = 0; 81 Map[i][j] = 1; 82 } 83 else if (ch == ‘B‘)//普通砖块,权值为2 84 { 85 Map[i][j] = 2; 86 } 87 else if (ch == ‘E‘)//空地,权值为1 88 { 89 Map[i][j] = 1; 90 } 91 else 92 { 93 Map[i][j] = 0;//为0的时候表示此点不可走 94 } 95 } 96 } 97 printf("%d\n", bfs()); 98 } 99 100 return 0;101 }
NYOJ 284 坦克大战 bfs + 优先队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。