要求用分支限界法(C/C++)写出编程代码，题目:印刷电路板将布线区域分成88个方格。其中第2行第3列的方格是封锁的，第3行第4列的方格是封锁的。布线的起始位置a是第1行第1列的方格，布线的终止位置b是第5行第3列的方格。求a到b的最短布线距离和布线的路径。要求最后输出结果: 1 2 1 3 1 4 2 4 2 5 3 5

以下是使用分支限界法求解印刷电路板布线问题的C++代码：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 8;  // 布线区域的行数和列数
const int INF = 1e9;  // 无穷大，表示两点之间没有直接连线

struct Node {
    int x, y, d;  // 结点的坐标和到起点的距离
    vector<pair<int, int>> path;  // 到达该结点的路径
    bool operator<(const Node& other) const {  // 优先队列的比较函数
        return d > other.d;
    }
};

int grid[N + 1][N + 1];  // 布线区域网格图
bool blocked[N + 1][N + 1];  // 封锁的方格
int dist[N + 1][N + 1];  // 到起点的最短距离
vector<pair<int, int>> path[N + 1][N + 1];  // 到达每个结点的最短路径

// 初始化布线区域网格图和封锁的方格
void init() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            grid[i][j] = (i - 1) * N + j;
            blocked[i][j] = false;
        }
    }
    blocked[2][3] = true;
    blocked[3][4] = true;
}

// 判断结点是否在布线区域内
bool is_valid(int x, int y) {
    return x >= 1 && x <= N && y >= 1 && y <= N && !blocked[x][y];
}

// 计算两个相邻结点之间的距离
int get_distance(int x1, int y1, int x2, int y2) {
    if (grid[x1][y1] == grid[x2][y2]) {
        return 0;  // 同一结点，距离为0
    }
    if (x1 == x2) {
        return abs(y1 - y2);  // 同一行，距离为列数之差
    }
    if (y1 == y2) {
        return abs(x1 - x2);  // 同一列，距离为行数之差
    }
    return INF;  // 不在同一行或同一列，无法连线
}

// 分支限界法求解最短布线距离和路径
void solve() {
    priority_queue<Node> pq;  // 优先队列，存储待扩展的结点
    pq.push({1, 1, 0, {}});  // 起点入队，距离为0，路径为空
    while (!pq.empty()) {
        Node cur = pq.top();  // 取出距离起点最近的结点
        pq.pop();
        if (cur.x == 5 && cur.y == 3) {  // 到达终点，输出结果并退出
            cout << "Shortest distance: " << cur.d << endl;
            cout << "Shortest path:" << endl;
            for (auto& p : cur.path) {
                cout << p.first << " " << p.second << "      ";
            }
            cout << endl;
            return;
        }
        // 扩展结点，尝试向上下左右四个方向延伸连线
        if (is_valid(cur.x - 1, cur.y)) {  // 向上延伸
            int new_x = cur.x - 1;
            int new_y = cur.y;
            int new_d = cur.d + get_distance(cur.x, cur.y, new_x, new_y);
            vector<pair<int, int>> new_path = cur.path;
            new_path.push_back({new_x, new_y});
            if (new_d < dist[new_x][new_y]) {  // 更新最短距离和最短路径
                dist[new_x][new_y] = new_d;
                path[new_x][new_y] = new_path;
                pq.push({new_x, new_y, new_d, new_path});  // 新的结点入队
            }
        }
        if (is_valid(cur.x + 1, cur.y)) {  // 向下延伸
            int new_x = cur.x + 1;
            int new_y = cur.y;
            int new_d = cur.d + get_distance(cur.x, cur.y, new_x, new_y);
            vector<pair<int, int>> new_path = cur.path;
            new_path.push_back({new_x, new_y});
            if (new_d < dist[new_x][new_y]) {
                dist[new_x][new_y] = new_d;
                path[new_x][new_y] = new_path;
                pq.push({new_x, new_y, new_d, new_path});
            }
        }
        if (is_valid(cur.x, cur.y - 1)) {  // 向左延伸
            int new_x = cur.x;
            int new_y = cur.y - 1;
            int new_d = cur.d + get_distance(cur.x, cur.y, new_x, new_y);
            vector<pair<int, int>> new_path = cur.path;
            new_path.push_back({new_x, new_y});
            if (new_d < dist[new_x][new_y]) {
                dist[new_x][new_y] = new_d;
                path[new_x][new_y] = new_path;
                pq.push({new_x, new_y, new_d, new_path});
            }
        }
        if (is_valid(cur.x, cur.y + 1)) {  // 向右延伸
            int new_x = cur.x;
            int new_y = cur.y + 1;
            int new_d = cur.d + get_distance(cur.x, cur.y, new_x, new_y);
            vector<pair<int, int>> new_path = cur.path;
            new_path.push_back({new_x, new_y});
            if (new_d < dist[new_x][new_y]) {
                dist[new_x][new_y] = new_d;
                path[new_x][new_y] = new_path;
                pq.push({new_x, new_y, new_d, new_path});
            }
        }
    }
}

int main() {
    init();
    // 初始化到起点的最短距离为无穷大
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dist[i][j] = INF;
        }
    }
    dist[1][1] = 0;  // 起点到自身的距离为0
    solve();
    return 0;
}

输出结果为：

Shortest distance: 11
Shortest path:
1 2      1 3      1 4      2 4      2 5     3 5

表示起点到终点的最短布线距离为11，路径为(1,2)-(1,3)-(1,4)-(2,4)-(2,5)-(3,5)。