曼哈顿距离和c++实现
时间: 2024-06-17 08:07:55 浏览: 8
曼哈顿距离也叫曼哈顿街区距离,是指在规定的坐标系上,从一个点到另一个点的各个坐标数值差的绝对值的和。在二维平面上,两点 (x1,y1) 和 (x2,y2) 之间的曼哈顿距离是 |x1-x2| + |y1-y2|。
以下是一个C++实现示例:
```
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int x1, y1, x2, y2;
cout << "Enter the coordinates of point 1: ";
cin >> x1 >> y1;
cout << "Enter the coordinates of point 2: ";
cin >> x2 >> y2;
int manhattan_distance = abs(x1 - x2) + abs(y1 - y2);
cout << "The Manhattan distance between the two points is: " << manhattan_distance << endl;
return 0;
}
```
相关问题
曼哈顿距离c++代码
曼哈顿距离又称为城市街区距离,是两个向量在所有对应元素上差的绝对值的和。在二维平面上,曼哈顿距离就是两点横坐标差的绝对值与纵坐标差的绝对值之和。C++代码实现如下:
```
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
int x1, y1, x2, y2;
cout << "Enter the first point (x, y): ";
cin >> x1 >> y1;
cout << "Enter the second point (x, y): ";
cin >> x2 >> y2;
int manhattanDistance = abs(x1 - x2) + abs(y1 - y2);
cout << "The Manhattan distance between (" << x1 << ", " << y1 << ") and (" << x2 << ", " << y2 << ") is: " << manhattanDistance << endl;
return 0;
}
```
C++ 实现曼哈顿路由算法
曼哈顿路由算法(Manhattan Routing Algorithm)是一种常用的电路布线算法,主要用于解决电路板的布线问题。该算法基于曼哈顿距离,即在网格图中计算两点之间的距离。
下面是使用 C++ 实现曼哈顿路由算法的示例代码:
```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 遍历网格图,并记录每个点到起点的曼哈顿距离。在遍历过程中,我们只考虑横向和纵向移动,忽略对角线移动。最终,我们可以根据记录的前驱节点,输出从起点到终点的最短路径。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)