Gần nhất 1 trong ma trận nhị phân trong C ++

Cho một ma trận nhị phân, chúng ta cần tìm khoảng cách tối thiểu từ mỗi ô đến ô gần nhất có chứa 1.

Hãy xem một ví dụ.

Đầu vào

0 0 1
1 1 0
0 0 0

Đầu ra

1 1 0 0 0 1 1 1 2

Khoảng cách tối thiểu là khoảng cách nhỏ nhất từ ​​hàng ô hiện tại - 1 hàng ô + cột ô hiện tại - 1 cột ô.

Thuật toán

• Khởi tạo ma trận có kích thước mong muốn.

• Khởi tạo một ma trận khác có cùng kích thước để lưu trữ khoảng cách.

• Lặp lại trên toàn bộ ma trận

  .

  • Nếu giá trị ô hiện tại là 1, thì hãy đặt khoảng cách thành 0 vì khoảng cách từ 1 đến 1 là 0

  • Nếu giá trị ô hiện tại là 0

    • Lặp lại toàn bộ ma trận một lần nữa

    • Nếu ô là 1, thì hãy tính khoảng cách từ ô hiện tại.

    • Cập nhật khoảng cách tối thiểu.

      .

• In ma trận khoảng cách.

Thực hiện

Sau đây là cách thực hiện thuật toán trên trong 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;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

1 1 0
0 0 1
1 1 2