Trong bài toán này, chúng ta được cung cấp một bin ma trận nhị phân [] [] có kích thước nXm chỉ bao gồm 0 và 1. Nhiệm vụ của chúng ta là Tìm chu vi của các hình được tạo bằng 1s trong ma trận nhị phân.
Chu vi được thực hiện sẽ bao phủ hình từ tất cả các phía, tức là
Với 1 giá trị duy nhất, chu vi là 4.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
bin[][] = [1, 0] [1, 0]
Đầu ra
6
Giải thích
Các ô (0,0) và (1, 0) được nối với nhau tạo thành hình chữ nhật có cạnh 2 và 1. Chu vi là 6.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm tất cả một và các đóng góp của chúng vào chu vi và sau đó cộng tất cả để tìm giá trị.
Phần đóng góp của số 1 vào chu vi trong ma trận là, Phần đóng góp lớn nhất là 4, khi chỉ số 1 đóng góp vào chu vi
Mức đóng góp tối thiểu là 0, khi số 1 được bao quanh bởi tất cả các bên.
Vì vậy, với mỗi phần tử của ma trận, chúng ta cần kiểm tra xem nó có phải là 1 hay không. Đối với all1’s, chúng ta sẽ tìm các hàng xóm của nó, sau đó đóng góp vào chu vi và cuối cùng là chu vi.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
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;
} Đầu ra
The perimeter of shapes from formed with 1s is 18