您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 2312 Battle City：优先队列 BFS 最短转弯/射击路径

編輯：關於C++

题目大意

M×N 网格（≤300×300），坦克从 Y 出发到达 T。地形：空地 E、河流 R、钢墙 S、砖墙 B。动作：移动到相邻空地（1 回合），或向四方向射击（1 回合），子弹飞行直到出界或击中墙（砖墙变空地，钢墙无效）。求最少回合数。

建模：带权图最短路

状态：位置 (x,y)
移动：到相邻 E 代价 1
射击：方向上首个 B 变 E，代价 1（可视为移动到该 B 位置代价 2：射击+移动）
S、R 不可通行

Dijkstra / 优先队列 BFS

边权非负（1 或 2），用优先队列（小顶堆）实现 Dijkstra。

C++ 实现

#include 
#include 
#include 
using namespace std;

const int N = 305;
char grid[N][N];
int vis[N][N], M, N;
int sx, sy, tx, ty;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};

struct Node { int x, y, d; bool operator<(Node o) const { return d > o.d; } };

bool ok(int x, int y) {
    return x>=0 && x=0 && y q;
    memset(vis, -1, sizeof(vis));
    vis[sx][sy] = 0;
    q.push({sx, sy, 0});
    while (!q.empty()) {
        Node u = q.top(); q.pop();
        if (u.x==tx && u.y==ty) return u.d;
        for (int i=0;i<4;++i) {
            int nx=u.x+dx[i], ny=u.y+dy[i];
            if (ok(nx,ny) && vis[nx][ny]==-1) {
                vis[nx][ny] = 0;
                int cost = (grid[nx][ny]=='B') ? 2 : 1; // 砖墙：射击+移动=2
                q.push({nx, ny, u.d + cost});
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> M >> N, M||N) {
        for (int i=0;i> grid[i][j];
                if (grid[i][j]=='Y') { sx=i; sy=j; grid[i][j]='E'; }
                else if (grid[i][j]=='T') { tx=i; ty=j; }
            }
        cout << bfs() << endl;
    }
    return 0;
}