如何获得数组/矩阵中最长的1序列

Question

我的任务是在数组中找到“最长的1行”，包括水平和垂直方向。这个数组只包含0和1，例如：

4 4
0 1 1 1
0 1 0 1
0 1 1 0
1 0 1 0

输出应该打印出“starting” 1的[ i ] [ j ]和“ending” 1的[ i ] [ j ]。所以水平方向应该是[1] [0] [3] [0]。

我正在使用我的getcolor（）函数来获得[ i ] [ j ]位置上的值。

我已经思考了很长时间，几乎整个星期都在思考这个问题。我有一些想法，但都没有奏效。也许是因为我对C语言和数组完全不熟悉。

我知道我应该遍历数组，在每一个找到的1上把坐标保存到"start"，然后继续，将找到的每一个1保存到"end"中。在找到0之后，比较长度，如果长度最大，则覆盖长度。但我无法正确编写代码。有人可以帮我写代码吗？非常感谢。

编辑：这就是我所拥有的，但我只是刚开始，它已经不能工作了：

if(arr != NULL) {
  while (j < arr->cols) {
    while (i <=arr->rows) {
            if (getcolor(arr, i, j) == 1) {
                startI = i;
                startJ = j;
                break;
            }
            else
            i++;
    }
    i=0;
    while (i <=arr->rows) {
            if (getcolor(arr, i, j) == 1) {
                endI = i;
                endJ = j;
            }
            i++;
    }
    i=0;

   printf("start %d %d\nend %d %d\nline %d\n\n", startI, startJ, endI, endJ, line);
   j++;
   }
}

- user3021851

---

请展示一些您已经编写的代码片段。 - woolstar

你在描述中已经概括了大致的想法，请发布你尝试过的代码并告诉我们为什么它没有起作用。 - Dave Swersky

这类似于查找具有最大总和的子数组。 - 0xF1

@0xF1 对于行而言，子数组是有意义的，但对于列则不然。除非我误解了子数组的含义？ - nonsensickle

@nonsensickle：你可以将所有列视为多个一维数组。 - 0xF1

Answer 1

当你遇到像这样的问题时，把它分解成更小、更容易解决的问题会有所帮助。你的问题是一个完美的例子。看起来你试图一次性解决整个问题，但是如你所见，由于嵌套循环等原因，这变得有点棘手。那么，你该如何让问题变得更简单呢？嗯，如果你能轻松地找到单行中最长的行，那么这个问题就会变得更简单。同样地，如果你能够轻松地获取单列中最长的行，那么也会更好。因此，考虑编写以下函数：

int longestLineInRow(int board[][], int width, int height, int &start, int &end)
{
    // returns length, with start and end being the indices of the beginning and end of the line
}

int longestLineInColumn(int board[][], int width, int height, int &start, int &end)
{
    // returns length, with start and end being the indices of the beginning and end of the line
}

现在找到具有最长行的行变得容易：只需找到每行中最长的行，并选择返回最大值的行。列也是如此。

我还没有为您解决在行或列中查找最长行的问题，但这是一个更简单的任务，一旦您停止试图一次解决整个问题，您可能可以自己解决它。

- Caleb

Answer 2

抱歉回复晚了。我没有完全按照你的要求写，但这篇文章会对你有所帮助。请仔细阅读，你就会明白。

代码链接 http://pastebin.com/vLATASab 或者在此处查看：

#include <stdio.h>

main()
{
    int arr[4][4];
    arr[0][0] = 0;arr[0][1] = 1;arr[0][2] = 1;arr[0][3] = 1;
    arr[1][0] = 0;arr[1][1] = 1;arr[1][2] = 0;arr[1][3] = 1;
    arr[2][0] = 0;arr[2][1] = 1;arr[2][2] = 1;arr[2][3] = 0;
    arr[3][0] = 1;arr[3][1] = 0;arr[3][2] = 1;arr[3][3] = 1;

    int i, j, k;
    int line, line_start, line_end, line_max = 0;
    int col, col_start, col_end, col_max = 0;

    // Horizently
    for (k=0; k<4; k++)
    {
        for (i=0; i<4; i++)
        {
            if (!arr[k][i]) continue;
            for (j=i; j<4; j++)
            {
                if (!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("horizontaly\n");
    printf("start: [%d][%d]\n", line, line_start);
    printf("end: [%d][%d]\n", line, line_end);

    // Verticaly
    for (k=0; k<4; k++)
    {
        for (i=0; i<4; i++)
        {
            if (!arr[i][k]) continue;
            for (j=i; j<4; j++)
            {
                if (!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_start, col);
    printf("end: [%d][%d]\n", col_end, col);

}

- rullof

---

如果您将for (j=i; j<4; j++)替换为for (;i<4;i++)（可能使用while更易读），则效率会更高。 （您需要在当前序列开始的位置存储i的值）。 我要解决的问题是，如果一行中有0111111111，则您的实现会找到9个长度为1的序列，第一个长度为9，第二个长度为8等等... 当然，您不应该写4，而应该写一些变量或常量nCols和NRows。 - Antonio

@rullof 非常感谢。你有想法如何使用这些行找到最大的由1组成的正方形吗？ - user3021851

@user3021851 请更新您的问题或者提出一个新的问题，这样其他人才能够帮助您。 - rullof

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct field {
    int rows;
    int cols;
    int *field;
} Field;

Field init_Field(){//Mock
    Field f;
    int data[4][4] = {
        {0, 1, 1, 1},
        {0, 1, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 1, 0}
    };
    f.rows = 4;
    f.cols = 4;
    int size = f.rows * f.cols;
    f.field = malloc(size * sizeof(*(f.field)));
    memcpy(f.field, data, size*sizeof(*(f.field)));
    return f;
}

int getcolor(Field *f, int r, int c){
    if(r < 0 || r >= f->rows) return -1;
    if(c < 0 || c >= f->cols) return -1;
    return f->field[ r * f->cols + c];
}

int search(Field *f, int r, int c, int dr, int dc, int level, int maxLen, int nowMax){
    //dr,dc : incremental
    if(dr > 0 && f->rows - r + level <= nowMax) return -1;//stop search
    if(dc > 0 && f->cols - c + level <= nowMax) return -1;//stop search
    if(level == maxLen)
        return level;
    if(getcolor(f, r, c)==1)
        return search(f, r + dr, c + dc, dr, dc, level + 1, maxLen, nowMax);

    return level;
}

int main(){
    Field f = init_Field();
    int HMaxLen = 0, HMaxRow, HMaxCol;
    int RMaxLen = 0, RMaxRow, RMaxCol;
    int r, c, len;
    for(r = 0; r < f.rows;++r){
        for(c = 0; c < f.cols;++c){
            len = search(&f, r, c, 0, 1, 0, f.cols, HMaxLen);
            if(len > HMaxLen){
                HMaxLen = len;
                HMaxRow = r;
                HMaxCol = c;
            }
            len = search(&f, r, c, 1, 0, 0, f.rows, RMaxLen);
            if(len > RMaxLen){
                RMaxLen = len;
                RMaxRow = r;
                RMaxCol = c;
            }
        }
    }
    free(f.field);
    printf("start %d %d\n  end %d %d\n\n", HMaxRow, HMaxCol, HMaxRow, HMaxCol + HMaxLen-1);
    printf("start %d %d\n  end %d %d\n\n", RMaxRow, RMaxCol, RMaxRow + RMaxLen-1, RMaxRow);
    return 0;
}

- BLUEPIXY

Answer 4

你可以尝试以下方法

void Reset(int s[2], int e[2], int cs[2],  int ce[2], int *resetState, int cc, int pc)
{
*resetState=0;
            if(cc>pc)
            {
                s[0]=cs[0];
                s[1]=cs[1];
                e[0]=ce[0];
                e[1]=ce[1];
            }
}
void Decide(int value, int s[2], int e[2], int cs[2],  int ce[2], int *resetState, int *cc, int *pc, int i, int j)
{
if(value==0&&*resetState)
{
        Reset(s, e, cs, ce, resetState, *cc, *pc);  
}
else if(value)
{
            if(*resetState==0)
            {
                cs[0]=i;
                cs[1]=j;
                if(*cc>*pc)
                {
                    *pc=*cc;
                }
                *cc=0;
                *resetState=1;
            }
            ce[0]=i;
            ce[1]=j;
            ++*cc;
}
}

void FindLargestRowNdColumn(int a[20][20],int row, int col, int hs[2], int  he[2], int vs[2], int ve[2])
{
int i, j, rcc=0, rpc=0, ccc=0, cpc=0;
int chs[2]={0,0}, che[2]={0,0}, cvs[2]={0,0}, cve[2]={0, 0};
int resetRow=0, restCol=0;
for(i=0; i<row; ++i)
{
    for(j=0; j<col; ++j)
    {
        Decide(a[i][j], hs, he, chs, che, &resetRow, &rcc, &rpc, i, j);
        Decide(a[j][i], vs, ve, cvs, cve, &restCol, &ccc, &cpc, i, j);
    }
    Reset(hs, he, chs, che, &resetRow, rcc, rpc);   
    Reset(vs, ve, cvs, cve, &restCol, ccc, cpc);    
}
}

void main()
{
int a[20][20], indexRow, colIndex;
int colum, row,hs[2], he[2], vs[2], ve[2];
printf("Enter number of rows and columns\n");
scanf("%d%d", &row, &colum);
printf("Enter the array\n");
for(indexRow=0; indexRow<row; ++indexRow)
{
    for(colIndex=0; colIndex<colum; ++colIndex)
    {
        scanf("%d", &a[indexRow][colIndex]);
    }
}
FindLargestRowNdColumn(a, row, colum, hs, he, vs, ve);
printf("Row [%d][%d] [%d][%d]\n", hs[0], hs[1], he[0], he[1]);
printf("column [%d][%d] [%d][%d]\n", vs[0], vs[1], ve[0], ve[1]);
}

- Kumareshan

Answer 5

我假设你展示的函数只解决了一半的问题，即找到最长的连续1的垂直序列。你需要编写一个镜像函数来查找最长的水平序列。

我会告诉你我在你的方法中看到的错误：

• 你没有计算出找到的序列的长度
• 你没有存储最长序列的长度和索引
• while (i <=arr->rows) 应该是 while (i < arr->rows)，否则当你只有第0、1、2和3行时，你也会查找第4行。
• 在找到1的序列开头后，你重置了 i。相反，i 应该继续前进
• 你还将 j 保存在 startJ 中，但只要你检查同一列，j 就不会改变
• 你只在每列中寻找一个1的序列
• "horizontally" 和 "vertically" 应该拼写为两个 "L" :-)

- Antonio