Tìm chu vi hình dạng từ các số 1 trong ma trận nhị phân trong C++

Trong bài toán này, cho ma trận nhị phân bin[][] kích thước NxM chỉ chứa 0 và 1. Nhiệm vụ là tìm chu vi hình dạng được tạo bởi các số 1.

Chu vi bao quanh hình từ mọi phía. Với 1 ô đơn lẻ, chu vi = 4.

Ví dụ minh họa:

Đầu vào

bin[][] = [1, 0] [1, 0]

Đầu ra

6

Giải thích

Ô (0,0) và (1,0) nối nhau tạo hình chữ nhật cạnh 2 và 1. Chu vi = 6.

Phương pháp giải

Tìm đóng góp của mỗi ô 1 vào chu vi. Tối đa 4 (ô đơn lẻ). Tối thiểu 0 (bị bao quanh 4 phía bởi 1). Duyệt ma trận, với mỗi ô 1 kiểm tra 4 hàng xóm (trên, dưới, trái, phải), đóng góp = 4 - số hàng xóm là 1. Tổng tất cả đóng góp.

Chương trình minh họa:

Ví dụ

#include <iostream> 
using namespace std; 

#define R 3 
#define C 5 

int contibutionToPerimeter(int mat[][C], int i, int j) { 
    int neighbours = 0; 
    if (i > 0 && mat[i - 1][j]) neighbours++; 
    if (j > 0 && mat[i][j - 1]) neighbours++; 
    if (i < R-1 && mat[i + 1][j]) neighbours++; 
    if (j < C-1 && mat[i][j + 1]) neighbours++; 
    return (4 - neighbours); 
} 

int calcPerimeter(int mat[R][C]){ 
    int perimeter = 0; 
    for (int i = 0; i < R; i++) 
        for (int j = 0; j < C; j++) 
            if (mat[i][j] == 1) 
                perimeter += contibutionToPerimeter(mat, i, j); 
    return perimeter; 
} 

int main() { 
    int mat[R][C] = { {0, 1, 0, 0, 0}, {1, 1, 1, 1, 0}, {1, 1, 0, 1, 1} }; 
    cout<<"The perimeter of shapes from formed with 1s is "<<calcPerimeter(mat); 
    return 0; 
}

Kết quả

The perimeter of shapes from formed with 1s is 18