สมมติว่ามีกลุ่มคน 2 คนขึ้นไป ต้องการพบกันและลดระยะทางเดินทางรวมให้น้อยที่สุด เรามีกริด 2 มิติค่า 0 หรือ 1 โดย 1 แทนบ้านของแต่ละคน ระยะทางคำนวณด้วย Manhattan Distance: distance(p1,p2) = |p2.x-p1.x| + |p2.y-p1.y|
เช่น ถ้าอินพุตเป็นกริด 3x5 ตามตาราง (มี 1 ที่ (0,0), (0,4), (2,2)) ผลลัพธ์จะเป็น 6 เพราะจุด (0,2) เป็นจุดพบปะที่เหมาะสม ระยะทางรวม 2+2+2=6 น้อยที่สุด
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- ฟังก์ชัน get(v): เรียง v; i=0, j=v.size()-1, ret=0; while i
- จาก main: รวบรวมพิกัดแถว (row) และคอลัมน์ (col) ของทุกเซลล์ที่เป็น 1; คืนค่า get(row) + get(col)
เหตุผล: ปัญหา Manhattan Distance แยกเป็นแกน x และ y ได้ ค่ามัธยฐาน (median) ให้ผลรวมระยะทางน้อยที่สุด การจับคู่ค่ามากสุดกับน้อยสุด (v[j]-v[i]) เทียบเท่ากับการหาผลรวมระยะทางจาก median
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTotalDistance(vector>& grid) {
vector row, col;
for(int i=0;i v){
sort(v.begin(), v.end());
int i=0, j=v.size()-1, ret=0;
while(i> v = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
cout << (ob.minTotalDistance(v));
}
อินพุต
{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}
เอาต์พุต
6
