54. Spiral Matrix

It’s easy to use recursion. First traverse the outmost rows and columns and recurse. It’s also easy to transform the recursion algorithm to an iterative one.

We can also use dfs, first go right, then go down, left, up. I just got the following inefficient code, but I don’t want to optimize:

class Solution {
public:
    struct PairHash {
        std::size_t operator()(const std::pair<int, int>& p) const {
            std::hash<int> hasher;
            
            return hasher(p.first) ^ hasher(p.second);
        }
    };
    enum class Direction {
        left,
        right,
        up,
        down
    };
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        const auto rows = matrix.size();
        const auto cols = rows? matrix.front().size(): 0;
        const auto size = rows * cols;
        
        if (!size) {
            return {};
        }
        
        std::unordered_set<std::pair<int, int>, PairHash> visited;
        std::vector<int> result;
        
        int i = 0;
        int j = 0;
        Direction dir = Direction::right;
        
        while (result.size() != size) {
            result.emplace_back(matrix[i][j]);
            visited.emplace(i, j);
            
            switch (dir) {
                case Direction::right:
                    if (j + 1 < cols && !visited.count({i, j + 1})) {
                        ++j;
                    } else {
                        ++i;
                        dir = Direction::down;
                    }
                    break;
                    
                case Direction::left:
                    if (j > 0 && !visited.count({i, j - 1})) {
                        --j;
                    } else {
                        --i;
                        dir = Direction::up;
                    }
                    break;
                    
                case Direction::up:
                    if (i > 0 && !visited.count({ i-1, j})) {
                        --i;
                    } else {
                        ++j;
                        dir = Direction::right;
                    }
                    break;
                    
                case Direction::down:
                    if (i + 1 < rows && !visited.count({i + 1, j})) {
                        ++i;
                    } else {
                        --j;
                        dir = Direction::left;
                    }
                    break;
            }
        }
        
        return result;
    }
};