C++ 实现曼哈顿路由算法

曼哈顿路由算法（Manhattan Routing Algorithm）是一种常用的电路布线算法，主要用于解决电路板的布线问题。该算法基于曼哈顿距离，即在网格图中计算两点之间的距离。

下面是使用 C++ 实现曼哈顿路由算法的示例代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int INF = 0x3f3f3f3f;

int n, m; // 网格图的行数和列数
int sx, sy, tx, ty; // 起点和终点的坐标
int dis[N][N]; // 记录每个点到起点的曼哈顿距离
int vis[N][N]; // 标记每个点是否访问过
int pre[N][N]; // 记录每个点的前驱节点

// 计算两点之间的曼哈顿距离
int manhattan_distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// 检查点是否合法
bool check(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

// BFS 遍历网格图
void bfs() {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    dis[sx][sy] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == tx && y == ty) {
            break;
        }

        // 枚举当前点的四个方向
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 || dy == 0) { // 只考虑横向和纵向移动
                    int nx = x + dx;
                    int ny = y + dy;
                    if (check(nx, ny) && !vis[nx][ny]) {
                        vis[nx][ny] = 1;
                        dis[nx][ny] = dis[x][y] + manhattan_distance(nx, ny, tx, ty);
                        pre[nx][ny] = x * m + y;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
}

// 输出路径
void print_path() {
    int cur = tx * m + ty;
    vector<int> path;
    while (cur != sx * m + sy) {
        path.push_back(cur);
        cur = pre[cur / m][cur % m];
    }
    path.push_back(sx * m + sy);

    reverse(path.begin(), path.end());
    for (int i = 0; i < path.size(); i++) {
        printf("(%d,%d)", path[i] / m, path[i] % m);
        if (i != path.size() - 1) {
            printf("->");
        }
    }
    printf("\n");
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &sx, &sy, &tx, &ty);

    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));

    bfs();

    printf("最短路径长度为：%d\n", dis[tx][ty]);
    printf("路径为：");
    print_path();

    return 0;
}

在上面的代码中，我们使用 BFS 遍历网格图，并记录每个点到起点的曼哈顿距离。在遍历过程中，我们只考虑横向和纵向移动，忽略对角线移动。最终，我们可以根据记录的前驱节点，输出从起点到终点的最短路径。