My C++ solution with description


  • 0
    S

    we traverse the matrix, when come across a "1", we try to find the longest line of consecutive one in four directions: horizontal, vertical, diagonal or anti-diagonal.
    before the finding process, we should judge:

    1. horizontal: if M[i][j] = 1, we judge whether M[i][j-1] is 1. if not, we increase j to find the longest consecutive one.
    2. vertical: if M[i][j] = 1, we judge whether M[i-1][j] is 1.
    3. diagonal: if M[i][j] = 1, we judge whether M[i-1][j-1] is 1.
    4. anti-diagonal: if M[i][j] = 1, we judge whether M[i+1][j-1] is 1.
      moreover, we should pay attention to special conditions that "1" is at the boundary of the matrix.
    class Solution {
    public:
        int longestLine(vector<vector<int>>& M) {
            int res = 0;
            if(M.size() == 0 || M[0].size() == 0) return 0;
            
            for(int i = 0; i < M.size(); ++i){
                for(int j = 0; j < M[i].size(); ++j){
                    if(M[i][j] == 1){
                        int tmpres = 1;
                        // horizontal
                        if(j==0 || (j > 0 && M[i][j-1] == 0)){
                            tmpres = 1;
                            for(int k = j+1; k < M[i].size(); ++k){
                                if(M[i][k] == 1) tmpres++;
                                else break;
                            }
                            res = max(res,tmpres);
                        }
                        
                        //vertical
                        if(i==0 || (i>0 && M[i-1][j] == 0)){
                            tmpres = 1;
                            for(int k = i+1; k < M.size(); ++k){
                                if(M[k][j] == 1) tmpres++;
                                else break;
                            }
                            res = max(res,tmpres);
                        }
                        
                        //diagonal
                        if((i==0 || j==0) || (i>0 && j>0 && M[i-1][j-1]==0)){
                            tmpres = 1;
                            for(int k = i + 1, t = j+1; k< M.size() && t<M[k].size(); ++k,++t){
                                if(M[k][t] == 1) tmpres++;
                                else break;
                            }
                            res = max(res,tmpres);
                        }
                        
                        //anti-diagonal
                        if((i==0 || j == M[i].size()) || M[i-1][j+1] == 0){
                            tmpres = 1;
                            for(int k = i + 1, t = j - 1; k< M.size() && t>=0; ++k,--t){
                                if(M[k][t] == 1) tmpres++;
                                else break;
                            }
                            res = max(res,tmpres);
                        }
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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