My DFS AC solution, easy to understand!!!


  • 0
    D

    public class Solution {
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length==0 || matrix[0].length==0) {
            return res;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        boolean[][] vis = new boolean[row][col];
        dfs(res, matrix, 0, 0, vis, 0);
        return res;
    }
    
    private void dfs(List<Integer> res, int[][] matrix, int i, int j, boolean[][] vis, int idx) {
        int row = matrix.length;
        int col = matrix[0].length;
        res.add(matrix[i][j]);
        vis[i][j] = true;
        int count = 0;
        while(true) {
            if (count == 4) {
                break;
            }
            idx = idx % 4;
            int[] dir = dirs[idx];
            int x = i+dir[0];
            int y = j+dir[1];
            if (x<0||x>=row||y<0||y>=col||vis[x][y]) {
                idx++;
                count++;
                continue;
            }
            dfs(res, matrix, x, y, vis, idx);  // continue to use the last direction
        }
    }
    

    }


Log in to reply
 

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