資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社科
時尚研究
法律研究2D 二進位制陣列最佳會議地點（C++）
在這個問題中，給定一個 2D 二進位制陣列，即陣列的值要麼是 0，要麼是 1，其中 1 標註為該組人員的住所。該組人員想要會面。因此，他們需要儘量縮短到一個共同地點會面的總距離。有效的會面地點可以位於任何位置，但不能是任何人的住所。
為了找到最小距離，建立了一個公式，稱作曼哈頓距離，其中距離 -
（p1，p2）= |p2.x| + |p2.y - p1.y|。
我們來舉一個例子，以便明確概念
示例
Input:
{10001}
{00000}
{00100}
Output: 6解釋 - 這裡最佳會面地點是 (0,2)，這樣會面的總距離為 6（2+2+2）。
現在，讓我們為這個問題建立一個解決方案。這裡，我們必須從陣列中所有標註為 1 的點中找到一箇中點。我們透過分別找到水平和垂直中心（中點）來實現此操作。並且，我將找到該點與所有標記為 1 的點的距離。
演算法
Step 1 : Create two structures with the values of horizontal and vertical positions of the points Marked one. Step 2 : In both this structures, find the mid positions and treat (midx, midy) it as the meeting point. Step 3 : Calculate the distance of each point it to the mid. Step 4 : return the sum of all distances.
示例
讓我們基於這個演算法建立一個演算法 −
#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 5
int minMeetingDistance(int grid[][COL]) {
if (ROW == 0 || COL == 0)
return 0;
vector<int> vertical;
vector<int> horizontal;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (grid[i][j] == 1) {
vertical.push_back(i);
horizontal.push_back(j);
}
}
}
sort(vertical.begin(),vertical.end());
sort(horizontal.begin(),horizontal.end());
int size = vertical.size()/2;
int midx = vertical[size];
int midy = horizontal[size];
int distance = 0;
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
if (grid[i][j] == 1)
distance += abs(midx - i) + abs(midy - j);
return distance;
}
int main() {
int distance[ROW][COL] =
{{1, 0, 1, 0, 1},
{0, 0, 0, 1, 0},
{0, 1, 1, 0, 0}};
cout<<"The minimum distance travelled to meet is "<<minMeetingDistance(distance);
return 0;
}輸出
The minimum distance travelled to meet is 11
更新於: 22-11-2019
140 次瀏覽
廣告