dfs style solution


  • 0
    T
    class Solution {
    public:
    void traverse(vector<vector<int>>& matrix, int i, int j, vector<int>& ret, 
                  vector<vector<bool>>& visited,
                  int d[4][2],
                  int dir) {
        ret.push_back(matrix[i][j]);
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int nextI = i + d[dir%4][0];
            int nextJ = j + d[dir%4][1];
            if (nextI < 0 || nextJ < 0 || nextI >= matrix.size() || nextJ >= matrix[0].size() ||
                visited[nextI][nextJ]) {
                dir++;
                continue;
            }
            traverse(matrix, nextI, nextJ, ret, visited, d, dir);
            break;
        }
        
    }
    
    
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
         vector<int> ret;
         int row = matrix.size();
         if (row == 0) return ret;
         int col = matrix[0].size();
         vector<vector<bool>> visited(row, vector<bool>(col, false));
         int d[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};//right->down->left->up
         traverse(matrix, 0, 0, ret, visited, d, 0);
         return ret;
      }
    };

Log in to reply
 

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