การจำลองกระรอกใน C++

มีต้นไม้ กระรอก และถั่วหลายตัว ตำแหน่งจะแสดงโดยเซลล์ในตาราง 2D เป้าหมายของคุณคือการหาระยะทางที่น้อยที่สุดสำหรับกระรอกในการรวบรวมถั่วทั้งหมดและวางไว้ใต้ต้นไม้ทีละตัว กระรอกสามารถดึงน็อตได้ครั้งละหนึ่งตัวเท่านั้น และสามารถเคลื่อนที่ได้สี่ทิศทาง - ขึ้น ลง ซ้าย และขวา ไปยังเซลล์ที่อยู่ติดกัน ระยะทางจะแสดงด้วยจำนวนการเคลื่อนไหว

ดังนั้น หากอินพุตเป็น ความสูง:5 ความกว้าง:7 ตำแหน่งต้นไม้:[2,2] กระรอก:[4,4] ถั่ว:[[3,0], [2,5]] ผลลัพธ์จะเป็น 12 ,

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน calc() ซึ่งจะใช้เวลา x1, y1, x2, y2,

• กลับ |x1 - x2| + |y1 - y2|

• กำหนดฟังก์ชัน minDistance() ซึ่งจะใช้ความสูง ความกว้าง ต้นไม้อาร์เรย์ อาร์เรย์ sq ถั่วอาร์เรย์ 2 มิติหนึ่งตัว

• ยกเลิก :=0

• maxDiff :=-inf

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของถั่ว อัปเดต (เพิ่ม 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]))

• ย้อนกลับ - 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