จากเมทริกซ์ไบนารี เราต้องหาระยะทางต่ำสุดจากแต่ละเซลล์ไปยังเซลล์ที่ใกล้ที่สุดซึ่งมี 1
มาดูตัวอย่างกัน
ป้อนข้อมูล
0 0 1 1 1 0 0 0 0
ผลผลิต
1 1 0 0 0 1 1 1 2
ระยะทางต่ำสุดคือระยะที่น้อยที่สุดจากแถวเซลล์ปัจจุบัน - 1 แถวเซลล์ + คอลัมน์เซลล์ปัจจุบัน - 1 คอลัมน์เซลล์
อัลกอริทึม
-
เริ่มต้นเมทริกซ์ของขนาดที่ต้องการ
-
เริ่มต้นเมทริกซ์ขนาดเดียวกันเพื่อเก็บระยะทาง
-
วนซ้ำทั่วทั้งเมทริกซ์
.-
หากค่าเซลล์ปัจจุบันคือ 1 ให้ตั้งค่าระยะทางเป็น 0 เนื่องจากระยะห่างจาก 1 ถึง 1 คือ 0
-
ถ้าค่าเซลล์ปัจจุบันเป็น 0
-
วนซ้ำเมทริกซ์ทั้งหมดอีกครั้ง
-
หากเซลล์เป็น 1 ให้คำนวณระยะทางจากเซลล์ปัจจุบัน
-
อัพเดทระยะทางขั้นต่ำ
.
-
-
-
พิมพ์เมทริกซ์ระยะทาง
การนำไปใช้
ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน C++
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> findNearest1Distance(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (rows == 0) {
return matrix;
}
int cols = matrix[0].size();
vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
distance[i][j] = 0;
}else if (matrix[i][j] == 0) {
for (int k = 0; k < rows; k++) {
for (int l = 0; l < cols; l++) {
if (matrix[k][l] == 1) {
distance[i][j] = min(distance[i][j], abs(k - i) + abs(l - j));
}
}
}
}
}
}
return distance;
}
int main() {
vector<vector<int>> matrix{
{0, 0, 1},
{1, 1, 0},
{0, 0, 0}
};
vector<vector<int>> result = findNearest1Distance(matrix);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
1 1 0 0 0 1 1 1 2
