印刷电路板将布线区域划分成n×m个方格。精确的电路布线问题要求确定连接方格a 的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避 免线路相交，对已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。所示 为一个布线的例子，图中阴影部分是指被封锁的方格,其起始点为a、目标点为b。编写一 个实验程序采用分枝限界法求解。Java代码

下面是 Java 代码实现，采用了分支限界法求解：

import java.util.*;

class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Node implements Comparable<Node> {
    Point point;
    int g, h, f;
    Node parent;

    Node(Point point, int g, int h, Node parent) {
        this.point = point;
        this.g = g;
        this.h = h;
        this.f = g + h;
        this.parent = parent;
    }

    @Override
    public int compareTo(Node o) {
        return this.f - o.f;
    }
}

public class PCBLayout {
    // 定义方向常量
    private static final int[] dx = {0, 1, 0, -1};
    private static final int[] dy = {1, 0, -1, 0};

    // PCBLayout函数
    public static int PCBLayout(int[][] map, Point start, Point end) {
        // 初始化open表和closed表
        PriorityQueue<Node> open = new PriorityQueue<>();
        Set<Point> closed = new HashSet<>();

        // 将起始点添加到open表中
        Node startNode = new Node(start, 0, heuristic(start, end), null);
        open.offer(startNode);

        // 分支限界搜索
        while (!open.isEmpty()) {
            // 取出open表中f值最小的节点
            Node curr = open.poll();

            // 如果当前节点为终止节点，返回路径长度
            if (curr.point.x == end.x && curr.point.y == end.y) {
                return curr.g;
            }

            // 将当前节点添加到closed表中
            closed.add(curr.point);

            // 对当前节点的相邻节点进行扩展
            for (int i = 0; i < 4; i++) {
                int x = curr.point.x + dx[i];
                int y = curr.point.y + dy[i];
                Point next = new Point(x, y);

                // 判断相邻节点是否合法
                if (x >= 0 && x < map.length && y >= 0 && y < map[0].length && map[x][y] != 1) {
                    // 判断相邻节点是否已经在closed表中
                    if (!closed.contains(next)) {
                        // 计算相邻节点的g值和h值
                        int g = curr.g + distance(curr.point, next);
                        int h = heuristic(next, end);

                        // 将相邻节点添加到open表中
                        Node nextNode = new Node(next, g, h, curr);
                        open.offer(nextNode);
                    }
                }
            }
        }

        // 如果open表为空，表示无法从起始点到达终止点
        return -1;
    }

    // 计算两个点之间的曼哈顿距离
    private static int distance(Point a, Point b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    // 计算一个点到终止点的曼哈顿距离
    private static int heuristic(Point a, Point b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    public static void main(String[] args) {
        int[][] map = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 1, 0},
                {0, 1, 1, 1, 1, 0},
                {0, 0, 0, 0, 0, 0}
        };
        Point start = new Point(1, 1);
        Point end = new Point(3, 4);
        int length = PCBLayout(map, start, end);
        System.out.println(length);
    }
}

其中，Point类表示一个点，Node类表示搜索树中的一个节点，f值表示节点的估价函数值，g值表示节点到起始点的距离，h值表示节点到终止点的估计距离，parent表示节点的父节点。

PCBLayout函数实现了分支限界搜索算法，open表使用了优先队列来实现，closed表使用了哈希集合来实现，heuristic函数计算了一个点到终止点的曼哈顿距离，distance函数计算了两个点之间的曼哈顿距离。在main函数中，我们定义了一个5x6的地图，起始点为(1,1)，终止点为(3,4)，调用PCBLayout函数求解最短路径长度，并输出结果。