โจทย์
ได้รับเมทริกซ์ไบนารี เราต้องหาระยะทางขั้นต่ำจากแต่ละเซลล์ไปยังเซลล์ที่ใกล้ที่สุดที่มีค่า 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
