Backtracking, the easiest to understand. O(n) algorithm n= matrix size


  • 0
    S

    I think this is most straight forward way to solve the problem. The technique is backtracking...
    suppose you are standing @i,j, get coded the next legal step. Stop tracking when nowhere else to go.

    class Solution {
    public:
        bool  is_legal(vector<vector<int> > &matrix, int i, int j) { 
            // check if current stand is legal or not
            if(!((i >= 0 && i < matrix.size()) && (j >= 0 && j < matrix[0].size()))) return false;
            if(matrix[i][j] == -10000) return false;
            return true;
        }
    
        void solver(vector<vector<int> > &matrix, vector<int> &res, int i, int j, int dirt) {
            //dirt
            //0: up
            //1: down
            //2: right
            //3: left
            //accept condition
            if(!(is_legal(matrix, i-1,j) || is_legal(matrix, i+1, j) || is_legal(matrix, i, j+1) || is_legal(matrix, i, j-1) || is_legal(matrix, i, j))) {
                return;
            } else if(dirt == 0 && !(is_legal(matrix, i-1, j))) {   //change directions
                dirt = 2;
            } else if(dirt == 2 && !(is_legal(matrix, i, j+1))) {
                dirt = 1;
            } else if(dirt == 1 && !(is_legal(matrix, i+1, j))) {
                dirt = 3;
            } else if(dirt == 3 && !(is_legal(matrix, i, j-1))) {
                //left
                dirt = 0;
            }
            int curt = matrix[i][j];
            res.push_back(curt);   //push into the tracker
            matrix[i][j] = -10000;    //mark as visited
            if(dirt == 1)    solver(matrix, res, ++i, j, dirt);
            if(dirt == 0)    solver(matrix, res, --i, j, dirt);
            if(dirt == 2)    solver(matrix, res, i, ++j, dirt);
            if(dirt == 3)    solver(matrix, res, i, --j, dirt);
        }
        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            vector<int> v;
            solver(matrix, v, 0, 0, 2);
            return v;
        }
    };

Log in to reply
 

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