Найти длину самой длинной последовательности в матрице

Question

Задача:

Учитывая булеву матрицу, которая имеет только 1 и 0. Найдите длину самой длинной последовательности непрерывных 1s. Разрешены только движения: Юг, Юго-Восток и Восток.

Пример матрицы: с выходом 5

10000 
01111 
00100 
00010 

Я пытаюсь решить эту проблему, но не достигли понимания проблемы думать о возможном решении. Нужна помощь в анализе и понимании проблемы.

Update:

Пожалуйста, поделитесь правильность.

for i=1 to n+1 
    N[i][m+1] = 0; 
for j=1 to m+1 
    N[n+1][j] = 0; 
for i=n to 1 
    for j=m to 1 
      if M[i][j] == 1 
       N[i][j] = 1 + max(N[i+1][j] , N[i][j+1]); 
      else 
       N[i][j] = 0 
search max element in matrix, output it. 
} 

Пробовал до сих пор

int main() 
{ 
    int A[5][5] = {{0,0,0,1,1},{1,1,1,0,1},{0,1,1,1,0},{0,0,1,0,0},{1,1,1,1,1}}; 
    int temp[5][5]; 
    int end_r(0), end_c(0); 
    for(int i=0; i<;5; i++){ 
     for(int j=0; j<;5; j++){ 
      temp[i][j] = A[i][j]; 
      int top(0), left(0), max(0); 
      if(i>;0) top = temp[i-1][j]; 
      if(j>;0) left = temp[i][j-1]; 
      if(top>left) max = top; else max=left; 
      if(temp[i][j] && max) {temp[i][j] = ++max, end_r=i; end_c=j;} 
      cout<<temp[i][j]<<" "; 

     } 
     cout<<endl; 
    } 
    int i = end_r, j = end_c, count=temp[i][j]; 
    --count; 
    while(count){  
    if((temp[i-1][j]) == count) --i; else --j; 
    --count; 
} 

    cout<<"Starting Point"<<" "<<i<<" "<<j<<endl; 
    cout<<"Ending Point"<<" "<<end_r<<" "<<end_c<<endl; 
    cout<<"Max Length"<<" "<<temp[end_r][end_c]; 
    return 0; 
} 

Решение

/* 
============================================================================ 
Author   : James Chen 
Email   : a.james.chen@gmail.com 
Description : Find the longest path of 1s available in the matrix 
Created Date : 11-July-2013 
Last Modified : 
============================================================================ 
*/ 

#include <iostream> 
#include <iomanip> 
#include <cassert> 
#include <vector> 

using namespace std; 

void DisplayPath(int* matrix, int rows, int cols, int maxCount) 
{ 
    typedef pair<int, int> Pair; 
    vector<Pair> path; 
    int prevRow = rows; 
    int prevCol = cols; 
    for(int i = rows - 1; i >= 0; --i){ 
     for(int j = cols - 1; j >=0; --j){ 
      if(matrix[ i * cols + j] == maxCount && i <= prevRow && j <= prevCol){ 
       path.push_back(make_pair(i, j)); 
       maxCount --; 
       prevRow = i; 
       prevCol = j;       
      } 

      if(maxCount == 0){ 
       cout << "The path is " << endl; 
       for(int i = path.size() - 1; i >= 0; i--){ 
        cout << path.size() - i << "th -- "; 
        cout << "[ " << path[i].first << ", " << path[i].second; 
        cout << "] " << endl; 
       } 

       return; 
      } 
     } 
    } 
} 

int FindLongest1Sequences(int* matrix, int rows, int cols) 
{ 
    assert(matrix != NULL); 
    assert(rows > 0); 
    assert(cols > 0); 

    int maxCount(0); 
    int count(0); 

    for(int i = 0; i < rows; i ++){ 
     for(int j = 0; j < cols; j++){ 
      int a = (i == 0) ? 0 : matrix[(i - 1) * cols + j]; 
      int b = (j == 0) ? 0 : matrix[i * cols + j - 1]; 
      matrix[i * cols + j] = matrix[i * cols + j] ? max(a, b) + 1 : 0; 
      maxCount = max(maxCount, matrix[i * cols + j]); 
     } 
    } 

    DisplayPath(matrix, rows, cols, maxCount); 

    return maxCount; 
} 

void DoTest(int* matrix, int rows, int cols) 
{ 
    if(matrix == NULL){ 
     cout << "The matix is null" << endl; 
     return; 
    } 

    if(rows < 1){ 
     cout << "The rows of matix is less than 1" << endl; 
     return; 
    } 

    if(cols < 1){ 
     cout << "The cols of matix is less than 1" << endl; 
     return; 
    } 

    cout << "The matrix is " << endl; 
    for(int i = 0; i < rows; ++i){ 
     for(int j = 0; j < cols; ++j){ 
      cout << setw(3) << matrix[i * cols + j]; 
     } 
     cout << endl; 
    } 

    int len = FindLongest1Sequences(matrix, rows, cols); 
    cout << "The longest length is " << len << endl; 
    cout << "---------------------------------------" << endl; 

} 



int main(int argc, char* argv[]) 
{ 
    int matrix[5][5] = { 
     {0, 0, 0, 1, 1}, 
     {1, 1, 1, 0, 1}, 
     {0, 1, 1, 1, 0}, 
     {0, 0, 1, 0, 0}, 
     {1, 1, 1, 1, 1} 
    }; 

    DoTest(&matrix[0][0], 5, 5);  // Expected return 8 

    int matrix1[1][1] = { 
     0 
    }; 
    DoTest(&matrix1[0][0], 1, 1);  // Expected return 0 

    int matrix2[1][1] = { 
     1 
    }; 
    DoTest(&matrix2[0][0], 1, 1);  // Expected return 1 

    int matrix3[5][5] = { 
     0 
    }; 

    DoTest(&matrix3[0][0], 5, 5);  // Expected return 0 

    int matrix4[5][5] = { 
     {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} 
    }; 

    DoTest(&matrix4[0][0], 5, 5);  // Expected return 9 

    int matrix5[5][5] = { 
     {1, 1, 0, 1, 1}, 
     {0, 1, 1, 0, 1}, 
     {1, 0, 0, 0, 0}, 
     {1, 1, 0, 1, 1}, 
     {1, 1, 1, 1, 1} 
    }; 

    DoTest(&matrix5[0][0], 5, 5);  // Expected return 7 

    return 0; 
} 

Выход

The matrix is 
    0 0 0 1 1 
    1 1 1 0 1 
    0 1 1 1 0 
    0 0 1 0 0 
    1 1 1 1 1 
The path is 
1th -- [ 1, 0] 
2th -- [ 1, 1] 
3th -- [ 2, 1] 
4th -- [ 2, 2] 
5th -- [ 3, 2] 
6th -- [ 4, 2] 
7th -- [ 4, 3] 
8th -- [ 4, 4] 
The longest length is 8 
--------------------------------------- 
The matrix is 
    0 
The longest length is 0 
--------------------------------------- 
The matrix is 
    1 
The path is 
1th -- [ 0, 0] 
The longest length is 1 
--------------------------------------- 
The matrix is 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
The longest length is 0 
--------------------------------------- 
The matrix is 
    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 
The path is 
1th -- [ 0, 0] 
2th -- [ 1, 0] 
3th -- [ 2, 0] 
4th -- [ 3, 0] 
5th -- [ 4, 0] 
6th -- [ 4, 1] 
7th -- [ 4, 2] 
8th -- [ 4, 3] 
9th -- [ 4, 4] 
The longest length is 9 
--------------------------------------- 
The matrix is 
    1 1 0 1 1 
    0 1 1 0 1 
    1 0 0 0 0 
    1 1 0 1 1 
    1 1 1 1 1 
The path is 
1th -- [ 2, 0] 
2th -- [ 3, 0] 
3th -- [ 4, 0] 
4th -- [ 4, 1] 
5th -- [ 4, 2] 
6th -- [ 4, 3] 
7th -- [ 4, 4] 
The longest length is 7 
--------------------------------------- 
Press any key to continue . . . 

Ref: https://en.wikipedia.org/wiki/Longest_increasing_subsequence https://sites.google.com/site/spaceofjameschen/annnocements/findthelongestpathof1savailableinthematrix--goldmansachs

Answer 1

Это динамическая задача программирования. Представьте, что вы решили проблему до строки i и столбца j. И для каждой строки < i, и каждый столбец в строке i, который меньше j, у вас есть ответ, сохраненный в DP [] [].

Теперь вы должны посмотреть на него как на индукцию. Лучший возможный ответ для DP [я] [J] может прийти из этих трех мест (если они существуют - это означает, что они являются допустимыми индексами и M [I] [J] == 1):

DP[i - 1][j] (a south move from there to i, j) 
DP[i - 1][j - 1] (a south east move from there) 
DP[i][j - 1] (an east move from there) 

код (первый код), который вы кладете пытается имитировать это, но на самом деле не дает правильное решение для этого теста (поскольку он не захватить юго-восток движение):

100 
010 
001 

на самом деле, ваш первые коды должны быть такими:

N[i][j] = 1 + max(N[i+1][j] , N[i][j+1], N[i + 1][j + 1]); 

Обратите внимание, что N [i] [j] подобен DP [i] [j], который я описал. Тем не менее, я описал DP как проблему, то есть перемещение на юг, юго-восток, восток. Но N [] [] решает проблему по-другому, т. Е. Начинает с нижнего правого угла и движется на запад, запад-север, север. Однако на самом деле это не имеет значения; они оба будут обеспечивать одно и то же решение. (Это хорошее упражнение, чтобы понять, почему)