C++ 中查找由所有 1 组成的最佳 '+' 形状的矩阵

2025年3月25日 | 阅读 4 分钟

在计算机科学和算法问题解决中，寻找各种问题的有效答案经常会让我们遇到以组合逻辑为核心的迷人谜题。其中一个问题是，找出由二进制矩阵中所有 1 组成的最大的“加号”（'+'）的大小。想象一个二维二进制网格，其中每个单元格都可以是 0 或 1。我们的目标是找到完全由 1 组成的最大的十字形结构（'+'）。这个结构必须满足几个要求：它的臂必须垂直和水平延伸，交叉点由中心单元格表示。此外，加号的臂不能交叉或超出矩阵的边界。

示例

1 1
1 1
1 0

输出

方法

解决该问题的一个简单方法是确定最大的“+”，这需要找出矩阵中某一点在一个方向上连续 1 的最大数量，并且该数量在所有四个方向上对于给定的 1 必须相同。我们将通过为该点的每一侧创建一个矩阵（或 4 个矩阵）来做到这一点。对于给定的元素，每个矩阵都将记录连续 1 的总数。对于每个索引值，我们将确定最大值，即四个方向上所有后续值的最小值。

示例 1

让我们看一个 C++ 程序来查找给定二进制矩阵中由所有 1 组成的最大的“+”的大小。

#include <iostream>
using namespace std;

// Size of the binary square matrix
#define N 5

// Function to find the size of the largest '+'
int findLargestPlus(int mat[N][N]) {
    // Arrays to store maximum consecutive 1's to the left, right, top, and bottom of each cell
    int left[N][N], right[N][N], top[N][N], bottom[N][N];

    // Initialize the arrays
    for (int i = 0; i < N; i++) {
        top[0][i] = mat[0][i];
        bottom[N - 1][i] = mat[N - 1][i];
        left[i][0] = mat[i][0];
        right[i][N - 1] = mat[i][N - 1];
    }

    // Fill the arrays
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (mat[i][j] == 1)
                left[i][j] = left[i][j - 1] + 1;
            else
                left[i][j] = 0;

            if (mat[j][i] == 1)
                top[j][i] = top[j - 1][i] + 1;
            else
                top[j][i] = 0;

            j = N - 1 - j;

            if (mat[j][i] == 1)
                bottom[j][i] = bottom[j + 1][i] + 1;
            else
                bottom[j][i] = 0;

            if (mat[i][j] == 1)
                right[i][j] = right[i][j + 1] + 1;
            else
                right[i][j] = 0;

            j = N - 1 - j;
        }
    }

    // Find the size of the largest '+'
    int max_size = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int min_len = left[i][j];
            min_len = min_len < right[i][j] ? min_len : right[i][j];
            min_len = min_len < top[i][j] ? min_len : top[i][j];
            min_len = min_len < bottom[i][j] ? min_len : bottom[i][j];

            if (min_len > max_size)
                max_size = min_len;
        }
    }

    // Calculate the total size of the largest '+'
    if (max_size)
        return 4 * (max_size - 1) + 1;
    return 0;
}

/* Driver function */
int main() {
    // Binary Matrix of size N
    int mat[N][N] = {
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1}
    };

    // Find and print the size of the largest '+'
    cout << "Size of the largest '+' formed by all 1's: " << findLargestPlus(mat) << endl;

    return 0;
}

输出

Size of the largest '+' formed by all 1's: 9

说明

此 C++ 程序的目的是找出给定二进制矩阵中仅包含 1 的最大加号（'+'）的大小。之后，它首先初始化数组，并存储矩阵中每个单元格左、右、上、下连续 1 的最大数量。这些数组通过遍历矩阵并更新每个方向上连续 1 的计数来填充。最后，程序使用中心单元格和四个方向上长度为 (n - 1) 的四个臂来确定并返回最大加号的大小。返回零表示没有找到加号，这意味着最大大小为零。

下一个主题2-sat-problem-in-cpp

C++ 中查找由所有 1 组成的最佳 '+' 形状的矩阵

示例

方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中查找由所有 1 组成的最佳 '+' 形状的矩阵

示例

方法

相关帖子

C++ 中的莫里斯遍历进行前序遍历

C++ 中的等分数字

C++ 中的鸭子数

C++ 中的 std::uninitialized_fill

C++ 中的自定义填字游戏

C++ 中的 std::is_destructible

C++ 中的 Zenkendorf 定理（非相邻斐波那契表示）

C++ std::mem_fun_ref

C++ 与 Prolog 的区别

C++ dlsym() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器