simple, with an example


  • 0
    V
    First, an example.
    For the input: M[i,j]
     [[0,1,1,0],
     [0,1,1,0],
     [0,0,0,1]]
    
    The DP matrix would look like,  Mat[i,j,k] // k is always 4 ? since we only need up, left, leftd, rightd
     [ [0,0,0,0],   [1,1,1,1],   [1,1,1,1],   [0,0,0,0] ],
     [ [0,0,0,0],   [2,1,1,2],   [2,2,2,1],   [0,0,0,0] ],
     [ [0,0,0,0],   [0,0,0,0],   [0,0,0,0],   [1,1,3,1] ]
    
    For every cell [i,j], in the input matrix we save 4 items in dp matrix. 
    Take a look at cell [1, 1] in the given input matrix. We need to save
    1. It has one 1 in the up direction, giving a total of 2 1s (including the 1 at cell [1,1])
    2. It has zero 1 in the left direction, giving a total of 1 1 in that direction so far
    3. It has zero 1 in the leftd direction, giving a total of 1 in that direction so far
    4. It has one 1 in the rightd direction giving a total of 2 in that direction
                                                                                                                    
    That is why the cell in the dp matrix at the corresponding [1,1] shows [2,  1,     1,      2]
    ------------------------------------------------------------------------up, left, leftd, rightd
    
    Why do we need to save 4 items for each cell?
    
    Take a look at the cell [1,1] in the input matrix again. 
    If we blindly save that the longest 1s so far at cell [1,1] is 2 (because we have another 1 at the up position), 
    then what do you do when you come to cell [1,2] and find another 1? 
    Do you increment to 3 since you have 2 so far on the left of cell [1,2]. 
    So, you are missing information there. You do not know if that 2 came from the up(no increment) 
    or left(should increment) side of cell [1,1].
    
    So, just save all information from all 4 sides.
     We do not need bottom, since we are going to calculate that when we iterate through matrix. 
    ```Classic top-down DP```
    
    Now, let's code
    
    
    public int LongestLine(int[,] M) {
            int max = 0;
            if (M == null) return max;
    
            var m = M.GetLength(0); var n = M.GetLength(1);
            var mat = new int[m, n, 4]; //every dp cell will now have 4 items
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < 4; k++) {
                        if (M[i, j] == 0) {
                            mat[i, j, k] = 0;
                        } else {
                            switch (k) {
                                case 0: // up
                                    mat[i, j, k] = 1 + (i-1 < 0 ? 0 : mat[i - 1, j, k]);
                                    break;
                                case 1: // left
                                    mat[i, j, k] = 1 + (j-1 < 0 ? 0 : mat[i, j - 1, k]);
                                    break;
                                case 2: // leftdiagonal
                                    mat[i, j, k] = 1 + (j-1 < 0 || i-1 < 0 ? 0 : mat[i - 1, j - 1, k]);
                                    break;
                                case 3: // rightdiagonal
                                    mat[i, j, k] = 1 + (j+1 == n || i-1 < 0 ? 0 : mat[i - 1, j + 1, k]);
                                    break;
                            }
                            max = mat[i, j, k] > max ? mat[i, j, k] : max;
                        }
                    }
                }
            }
    
            return max;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.