本文主要是介绍[算法] BFS ： poj 2312 Battle City 示例，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
纪念第一次用 “优先队列”， 第一次知道 “方向数组” ！ BFS ： 谁出队就找谁的邻接点访问之并入队！#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <climits>
#include <cassert>
#define BUG puts("here!!!");using namespace std;
const int N = 305;
struct Point {int x, y;int steps;
};
char mmap[N][N];
int n, m;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
bool ok(int x, int y) {return (x >= 0 && x < m && y >= 0 && y < n);
}
Point you, tag;
bool operator < (const Point &a, const Point &b) {return a.steps > b.steps;
}
int bfs() {priority_queue<Point> Q;Q.push(you);Point t, tmp;int xx, yy;while(!Q.empty()) {t = Q.top(); Q.pop();for(int i = 0; i < 4; i++) {xx = t.x + dx[i];yy = t.y + dy[i];if(!ok(xx, yy) || mmap[xx][yy] == 'R' || mmap[xx][yy] == 'S') {continue;}if(xx == tag.x && yy == tag.y) return t.steps + 1;tmp.x = xx;tmp.y = yy;if(mmap[xx][yy] == 'B') {tmp.steps = t.steps + 2;}else tmp.steps = t.steps + 1;mmap[xx][yy] = 'R';Q.push(tmp);}}return -1;
}
int main() {while(scanf("%d%d", &m, &n), m|n) {for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {cin >> mmap[i][j];if(mmap[i][j] == 'Y') {you.x = i;you.y = j;you.steps = 0;}else if(mmap[i][j] == 'T') {tag.x = i, tag.y = j;}}}printf("%d\n", bfs());}return 0;
}
这篇关于[算法] BFS ： poj 2312 Battle City 示例的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
