在 C++ 中查找由所有 1 组成的最大“+”的大小
在这个问题中,我们给出了一个NxN二进制矩阵bin[][]。我们的任务是在一个二进制矩阵中找到由所有1形成的最大“+”的大小。
让我们举个例子来理解这个问题,
输入
0 1 1 1 1 1 0 1 0输出结果
5
解决方法
该问题的一个简单解决方案是找到最大的“+”,我们需要为矩阵中的一个点在一个方向上找到最大数量的1,对于给定的1,该点在所有四个方向上都必须相同。对于这样,我们将为点的每一侧创建一个矩阵,即4。每个矩阵将存储给定元素的连续1的数量。对于所有索引值,我们将找到最大值,即所有四个方向上所有连续值中的最小值。
程序来说明我们的解决方案的工作,
示例
#includeusing 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<<"由一个组成的最大加号的大小是 "< 输出结果 由一个组成的最大加号的大小是 9