資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究C++中的松鼠模擬
有一棵樹、一隻松鼠和幾顆堅果。位置用二維網格中的單元格表示。你的目標是找到松鼠收集所有堅果並將它們一個接一個地放在樹下的最小距離。松鼠一次最多隻能拿一顆堅果，並且可以沿四個方向移動——上、下、左、右，到相鄰的單元格。距離用移動次數表示。
因此，如果輸入類似於高度：5 寬度：7 樹的位置：[2,2] 松鼠：[4,4] 堅果：[[3,0], [2,5]]，則輸出將為 12。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 calc()，它將接收 x1、y1、x2、y2。
返回 |x1 - x2| + |y1 - y2|
定義一個函式 minDistance()，它將接收高度、寬度、一個樹陣列、一個松鼠陣列和一個二維堅果陣列。
ret := 0
maxDiff := -inf
初始化 i := 0，當 i < 堅果數量時，更新（i 增加 1），執行：
dist := calc(tree[0], tree[1], nuts[i, 0], nuts[i, 1])
ret := ret + 2 * dist
maxDiff := maxDiff 與 2 * dist - (dist + calc(nuts[i, 0], nuts[i, 1], sq[0], sq[1])) 之間的最大值
返回 ret - maxDiff
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int calc(int x1, int y1, int x2, int y2){
return abs(x1 - x2) + abs(y1 - y2);
}
int minDistance(int height, int width, vector<int>& tree, vector<int>& sq, vector<vector>& nuts) {
int ret = 0;
int maxDiff = INT_MIN;
for (int i = 0; i < nuts.size(); i++) {
int dist = calc(tree[0], tree[1], nuts[i][0],
nuts[i][1]);
ret += 2 * dist;
maxDiff = max(maxDiff, 2 * dist - (dist + calc(nuts[i][0], nuts[i][1], sq[0], sq[1])));
}
return ret - maxDiff;
}
};
main(){
Solution ob;
vector<int> v = {2,2}, v1 = {4,4};
vector<vector<int>> v2 = {{3,0}, {2,5}};
cout << (ob.minDistance(5,7,v, v1, v2));
}輸入
5, 7, {2,2},{4,4}, {{3,0}, {2,5}}輸出
12
更新於：2020年11月16日
263 次檢視
廣告