562. Longest Line of Consecutive One in Matrix

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

Input:
[[0,1,1,0],
 [0,1,1,0],
 [0,0,0,1]]
Output: 3

Hint: The number of elements in the given matrix will not exceed 10,000.

利用一個3維的vector去紀錄所有情形到目前為止的數量，第一個維度代表row，第二個維度代表col，第三個維度: 0代表horizontal的結果，1代表vertical的結果，2代表對角線的結果，3代表反對角線的結果。

// Dynamic Programming
int longestLine(vector<vector<int>>& M) { // time: O(m * n); space: O(m * n)
    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, 0) ) );
    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; // update
            if (j > 0) dp[i][j][0] += dp[i][j - 1][0]; // horizontal
            if (i > 0) dp[i][j][1] += dp[i - 1][j][1]; // vertical
            if (i > 0 && j > 0) dp[i][j][2] += dp[i - 1][j - 1][2]; // diagonal
            if (i > 0 && j < n - 1) dp[i][j][3] += dp[i - 1][j + 1][3]; // anti-diagonal
            res = max({res, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]});
        }
    }
    return res;
}

最外層的for loop是row的loop，所以可以用一個row參數來記錄水平的結果，搭配其他3個arrays分別紀錄垂直、對角線、反對角線的結果。

// Dynamic Programming with Optimized Space Usage
int longestLine(vector<vector<int>>& M) { // time: O(m * n); space: O(m + n)
    if (M.empty() || M[0].empty()) return 0;
    int m = M.size(), n = M[0].size(), res = 0;
    vector<int> col(n, 0), diag(m + n - 1, 0), anti(m + n - 1, 0);
    for (int i = 0; i < m; ++i) {
        int row = 0;
        for (int j = 0; j < n; ++j) {
            if (M[i][j] == 1) {
                res = max(res, ++row);
                res = max(res, ++col[j]);
                res = max(res, ++diag[i + j]);
                res = max(res, ++anti[j - i + m - 1]);
            } else {
                row = 0;
                col[j] = 0;
                diag[i + j] = 0;
                anti[j - i + m - 1] = 0;
            }
        }
    }
    return res;
}

空間最優化的解，分別對水平和垂直寫各自的nested for loops，然後再寫對角線的，對角線外層for loop是第k條正反對角線的意思。

// Optimized Space Method
int longestLine(vector<vector<int>>& M) { // time: O(m * n); space: O(1)
    if (M.empty() || M[0].empty()) return 0;
    int m = M.size(), n = M[0].size(), res = 0, row = 0, col = 0, diag = 0, anti = 0;
    // Horizontal
    for (int i = 0; i < m; ++i) {
        for (int j = 0, row = 0; j < n; ++j) {
            row = M[i][j] ? (row + 1) : 0;
            res = max(res, row);
        }
    }
    // Vertical
    for (int j = 0; j < n; ++j) {
        for (int i = 0, col = 0; i < m; ++i) {
            col = M[i][j] ? (col + 1) : 0;
            res = max(res, col);
        }
    }
    for (int k = 0; k < m + n; ++k, diag = 0, anti = 0) {
        // Diagonal
        for (int i = max(m - 1 - k, 0), j = max(0, k - m + 1); i < m && j < n; ++i, ++j) {
            diag = M[i][j] ? (diag + 1) : 0;
            res = max(res, diag);
        }
        // Anti-diagonal
        for (int i = min(k, m - 1), j = max(0, k - m + 1); i >= 0 && j < n; --i, ++j) {
            anti = M[i][j] ? (anti + 1) : 0;
            res = max(res, anti);
        }
    }
    return res;
}