562 Leetcode: Longest Line of Consecutive One in Matrix

https://leetcode.com › problems › longest-line-of-consecutive-one-in-matrix

Notes:

This question can be solved by dp. (there're other ways of course, counting ones in four directions.., but it is not easy to convert the indexes in diagonal and anti-diagonal directions..., we also need to consider how to label the visiting condition of each 1 node, in order to check each direction of the 1 node only once.)

Let us focus on dp, since it is very straightforward. There are four directions that we need to consider, so we need three 2-D matrix, or one 3-D matrix used as the dp matrix.

dp[i][j][k] representing the maximum number of ones ending with the element at (i, j). k = 0, 1, 2, 3 are for horizontal, vertical, diagonal, and anti-diagonal directions, respectively.

If M[i][j] == 0, we just need to set all dp[i][j][k] = 0; or nothing if they are initialized as 0;

If M[i][j] == 1, we just need to update all dp[i][j][k] by 1 from the previous ones. And we need to save the largest one as the local optimal solution.

After scanning the whole matrix, we should obtained the largest of all the local maximums which is the global maximum.

See the code below:

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if (M.empty() || M[0].empty()) return 0;
        int m = M.size(), n = M[0].size(), res = 0;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(4)));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (M[i][j] == 0) continue;
                for (int k = 0; k < 4; ++k) dp[i][j][k] = 1;
                if (j > 0) dp[i][j][0] += dp[i][j - 1][0]; // horizonal
                if (i > 0) dp[i][j][1] += dp[i - 1][j][1]; // vertical
                if (i > 0 && j < n - 1) dp[i][j][2] += dp[i - 1][j + 1][2]; // diagonal
                if (i > 0 && j > 0) dp[i][j][3] += dp[i - 1][j - 1][3]; // anti-diagonal
                res = max(res, max(dp[i][j][0], dp[i][j][1]));
                res = max(res, max(dp[i][j][2], dp[i][j][3]));
            }
        }
        return res;
    }
};