在2Darrays/矩阵中找到由1组成的正方形
谢谢你的帮助。 对此，我真的非常感激。 我一直在寻找SO的解决方案，但没有什么是我需要的。 我需要它在C.
我的任务是在数组中找到1的“最大正方形”。 该数组仅包含0和1，并且看起来像这样：
4 4 0 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 输出应该打印“左上角”1的[row][col]和“右下角”的[row][col] ，所以它应该是，例如， [0][1]和[2][3] 。
我正在使用我的getcolor()函数来获取[row][col] spot的值。
此外，我有这些function，以获得最长的水平和垂直线。 出于某种原因，它们仅适用于具有相同列数和行数的数组。 例如，当我使用一个包含4列和5行的数组时，它无法正常工作。 你能帮帮我吗？
void getHline(Bitmap *arr) { int i, j, k; int line, line_start, line_end, line_max = 0; // Horizontally for (k = 0; k rows; k++) { for (i = 0; i rows; i++) { if(!getcolor(arr, k, i)) { continue; } for(j = i; j cols; j++) { if(!getcolor(arr, k, j)) { break; } } j--; if(j - i + 1 > line_max) { line = k; line_start = i; line_end = j; line_max = line_end-line_start+1; } } } printf("horizontally\n"); printf("start: [%d][%d]\n", line_start, line); printf("end: [%d][%d]\n", line_end, line); } void getVline(Bitmap *arr) { int i, j, k; int col, col_start, col_end, col_max = 0; for(k = 0; k cols; k++) { for (i = 0; i rows; i++) { if (!getcolor(arr,i,k)) continue; for (j = i; j cols; j++) { if (!getcolor(arr,j,k)) break; } j--; if (j - i + 1 >col_max) { col = k; col_start = i; col_end = j; col_max = col_end-col_start+1; } } } printf("\nverticaly\n"); printf("start: [%d][%d]\n", col, col_start); printf("end: [%d][%d]\n", col, col_end); }
如果你想要获得最大的正方形，这与最长的水平和垂直线有关，因为它们可以分开并且没有与它们相关的方形。
在尝试解决复杂问题时，请勿尝试立即解决所有问题。
我们首先要做的是，数组的每个点都与一个正方形（每个点的最大点）相关联。 所以我们必须找到那个方块：我们取一个数组的点，然后我们逐步通过连续的水平和垂直线。 对于每个步骤，我们检查是否得到一个正方形并重复该过程，直到我们得到与该单个点相关联的最大正方形。
每当我们得到与点相关联的最大平方时，我们检查它是否比最后一个与前一点相关的最大平方最大。
连接这些部件后，我们得到了最终的程序。
程序中使用的变量的说明： 
链接到程序http://pastebin.com/Yw05Gbtg或在此处查看：
编辑：
#include main() { int lines=4, cols=4; int arr[4][4] = { {0,1,1,1,}, {0,1,0,1,}, {0,1,1,1,}, {1,0,1,0,} }; int x_start, y_start, x_end, y_end, d_max=0; int i, j, k, l; int col_start, line_start, col_end, line_end, checker; for (y_start=0; y_startd_max){ col_start = x_start; line_start = y_start; col_end = x_end; line_end = y_end; d_max = col_end-col_start; } } } printf("The largest square is:\n[%d][%d] x [%d][%d]\n", line_start, col_start, line_end, col_end); // this is only to check if the program is working properly for (y_start=line_start; y_start
代码中某处的行和列之间存在混淆。 要找到它，请将变量i ， j和k重命名为更有意义的内容，例如row ， col_start和col_end 。
至于查找最大平方，您可能希望使用前缀和 。