C++, three solutions, easy to understand


  • 0

    Solution 1.

    We just need to maintain a direction variable and modify it when the path 'turns'.

    The code is as follows:

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

    Update(09/04/2017):

    Solution 2.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int>res;
            if(matrix.empty()) return res;
            DFS(matrix, 0, 0, matrix.size(), matrix[0].size(), res);
            return res;
        }
        
        void DFS(vector<vector<int>>& matrix, int r, int c, int maxR, int maxC, vector<int>& res){
            if(r >= maxR || c >= maxC) return;
            for(int i = c; i < maxC; i++) res.push_back(matrix[r][i]);
            for(int i = r + 1; i < maxR; i++) res.push_back(matrix[i][maxC - 1]);
            for(int i = maxC - 2; i > c && r != maxR - 1; i--) res.push_back(matrix[maxR - 1][i]);
            for(int i = maxR - 1; i > r && c != maxC - 1; i--) res.push_back(matrix[i][c]);
            DFS(matrix, r + 1, c + 1, maxR - 1, maxC - 1, res);
        }
    };
    

    Solution 3.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int>res;
            if(matrix.size() == 0) return res;
            DFS(matrix, 0, matrix.size() - 1, 0, matrix[0].size() - 1, res);
            return res;
        }
        
        void DFS(vector<vector<int>>& matrix, int minRow, int maxRow, int minCol, int maxCol, vector<int>& res){
            if(minRow > maxRow || minCol > maxCol) return;
            for(int i = minCol; i <= maxCol; i++) res.push_back(matrix[minRow][i]);
            minRow++;
            for(int i = minRow; i <= maxRow; i++) res.push_back(matrix[i][maxCol]);
            maxCol--;
            for(int i = maxCol; i >= minCol && minRow <= maxRow; i--) res.push_back(matrix[maxRow][i]);
            maxRow--;
            for(int i = maxRow; i >= minRow && minCol <= maxCol; i--) res.push_back(matrix[i][minCol]);
            minCol++;
            DFS(matrix, minRow, maxRow, minCol, maxCol, res);
        }
    };
    

Log in to reply
 

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