나무, 다람쥐, 견과류 몇 개가 있습니다. 위치는 2D 그리드의 셀로 표시됩니다. 당신의 목표는 다람쥐가 모든 견과류를 모아서 하나씩 나무 아래에 둘 수 있는 최소 거리를 찾는 것입니다. 다람쥐는 한 번에 최대 한 개의 너트만 먹을 수 있으며 인접한 셀로 위, 아래, 왼쪽, 오른쪽의 네 가지 방향으로 이동할 수 있습니다. 거리는 이동 횟수로 표시됩니다.
따라서 입력이 높이:5 너비:7 나무 위치:[2,2] 다람쥐:[4,4] 견과류:[[3,0], [2,5]]와 같은 경우 출력은 12가 됩니다. ,
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
calc() 함수를 정의하면 x1, y1, x2, y2,
가 필요합니다. -
반환 |x1 - x2| + |y1 - y2|
-
minDistance() 함수를 정의하면 높이, 너비, 배열 트리, 배열 sq, 2D 배열 너트 1개,
-
ret :=0
-
maxDiff :=-inf
-
초기화 i :=0의 경우, i <너트의 크기일 때 업데이트(i를 1만큼 증가), −
-
dist :=calc(나무[0], 나무[1], 견과류[i, 0], 견과류[i, 1])
-
렛 :=렛 + 2 * 거리
-
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