Trong bài toán này, chúng ta được cung cấp một bin ma trận nhị phân NxN [] []. Nhiệm vụ của chúng tôi là tìm ra kích thước của dấu ‘+’ lớn nhất được tạo thành bởi tất cả các dấu "+" trong ma trận nhị phân.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
0 1 1 1 1 1 0 1 0
Đầu ra
5
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 dấu '+' lớn nhất mà chúng ta cần để tìm số lớn nhất của 1 theo một hướng cho một điểm trong ma trận mà điểm đó cần phải giống nhau trong cả bốn hướng đối với giá trị 1. Đối với điều này, chúng ta sẽ tạo một ma trận cho mỗi cạnh của điểm tức là 4. Mỗi ma trận sẽ lưu trữ số 1 liên tiếp của phần tử đã cho. Đối với tất cả các giá trị chỉ mục, chúng tôi sẽ tìm giá trị lớn nhất là giá trị nhỏ nhất của tất cả các giá trị liên tiếp theo cả bốn hướng.
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 N 7
int findLargestPlusSize(int mat[N][N]) {
int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
for (int i = 0; i < N; i++) {
conOneTop[0][i] = mat[0][i];
conOneBottom[N - 1][i] = mat[N - 1][i];
conOneLeft[i][0] = mat[i][0];
conOneRight[i][N - 1] = mat[i][N - 1];
}
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (mat[i][j] == 1)
conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
else
conOneLeft[i][j] = 0;
if (mat[j][i] == 1)
conOneTop[j][i] = conOneTop[j - 1][i] + 1;
else
conOneTop[j][i] = 0;
j = N - 1 - j;
if (mat[j][i] == 1)
conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
else
conOneBottom[j][i] = 0;
if (mat[i][j] == 1)
conOneRight[i][j] = conOneRight[i][j + 1] + 1;
else
conOneRight[i][j] = 0;
j = N - 1 - j;
}
}
int maxConOne = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++){
int ConOnes = min(min(conOneTop[i][j],
conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
if(ConOnes > maxConOne)
maxConOne = ConOnes;
}
}
if (maxConOne)
return (4 * (maxConOne - 1) + 1);
return 0;
}
int main() {
int mat[N][N] = {
{ 1, 0, 1, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
};
cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
return 0;
} Đầu ra
The size of the largest plus formed by ones is 9