Tìm kích thước dấu '+' lớn nhất từ các 1 trong ma trận nhị phân trong C++

Trong bài toán này, cho ma trận nhị phân NxN bin[][]. Nhiệm vụ là tìm kích thước dấu '+' lớn nhất được tạo bởi toàn bộ số 1.

Ví dụ minh họa:

Đầu vào

0 1 1 1 1 1 0 1 0

Đầu ra

5

Phương pháp giải

Tìm dấu '+' lớn nhất cần tìm số 1 liên tiếp tối đa theo 4 hướng từ một điểm, và phải bằng nhau 4 hướng. Tạo 4 ma trận lưu số 1 liên tiếp cho mỗi hướng. Với mỗi ô, tìm min của 4 hướng, lấy max tổng thể.

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

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; 
}

Kết quả

The size of the largest plus formed by ones is 9