[matrix] C++ 0ms recursion easy to understand


  • 0

    We just need to maintain a direction variable and modify it when the path 'turns'.
    The code is as follows and any advice is welcomed.

        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int>res;
            if(matrix.size()==0) return res;
            pair<int,int>direction(0,1);
            vector<vector<int>>visited(matrix.size(),vector<int>(matrix[0].size(),0));
            spiral(matrix,0,0,direction,res,visited);
            return res;
        }
        
        void spiral(vector<vector<int>>& matrix,int r,int c,pair<int,int>& direction,vector<int>& res,vector<vector<int>>& visited){
            res.push_back(matrix[r][c]);
            visited[r][c]=1;
            if(res.size()==matrix.size()*matrix[0].size()) 
                return;
            int nextRow=r+direction.first;
            int nextCol=c+direction.second;
            if(nextRow==matrix.size()||nextCol==matrix[0].size()||nextCol<0||visited[nextRow][nextCol]==1) 
                direction=nextDirection(direction);
            spiral(matrix,r+direction.first,c+direction.second,direction,res,visited);
        }
        
        //directions: right=(0,1) -> down=(1,0) -> left=(0,-1) -> up=(-1,0);
        pair<int,int> nextDirection(pair<int,int>& direction){
            if(direction==make_pair(0,1)) return {1,0};
            if(direction==make_pair(1,0)) return {0,-1};
            if(direction==make_pair(0,-1)) return {-1,0};
            return {0,1};
        }
    

Log in to reply
 

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