C++에서 각 데카르트 좌표를 연결하기 위한 최소 비용을 찾는 프로그램

2D 데카르트 좌표점(x, y)의 목록이 있다고 가정합니다. 비용이 |x0 - x1|인 (x0, y0) 및 (x1, y1)을 연결할 수 있습니다. + |y0 - y1|. 몇 개의 점을 연결할 수 있다면 모든 점을 경로로 연결하는 데 필요한 최소 비용을 찾아야 합니다.

따라서 입력이 점 =[[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2]와 같은 경우 , -3]],

(0, 0)에서 (0, 2),(0, -2),(2, 0),(-2, 0)까지 비용은 2, 총계는 8이므로 출력은 14가 됩니다. (2, 3)은 (0, 2)에서 가장 가깝고 비용은 |2+1| =3이고 (2, -3)의 경우 (0, -2)에 가장 가깝고 비용도 3이므로 총 비용은 8 + 6 =14입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• MAX :=정보
• interval() 함수를 정의하면 i, j 및 점 배열 p가 필요합니다.
• 반환 |(p[i, x] - p[j, x]) + |p[i, y] - p[j, y]||
• 메인 방법에서 다음을 수행하십시오. -
• n :=p의 크기
• n <2이면 0을 반환합니다.
• n개의 슬롯이 있는 distance라는 배열을 정의하고 MAX로 채웁니다.
• n 크기의 방문 배열 정의
• 거리[0] :=0
• 초기화 i의 경우:=0, i
• min_d :=MAX
• 노드:=0
• j 초기화의 경우:=0, j
• 방문한[j]가 거짓이고 거리[j]
• min_d :=거리[j]
• 노드:=j

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include #include #define MAX 99999 네임스페이스 사용 std;int interval(int i, int j, vector>&p) { return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);}int solve(vector>&p) { int n =p.size (), 비용 =0; if (n <2) 반환 0; 벡터 거리(n, MAX); vector 방문(n); 거리[0] =0; for (int i =0; i > 점 ={{0, 0},{0, 2},{0, -2},{2, 0},{-2 , 0}, {2, 3}, {2, -3}}; cout <<해결(점);}

입력

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}} 
출력
 
14