首页 > 代码库 > 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 + 优先队列