Study/Algorithm/leetcode/54.java at master · 1ilsang/Study · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//https://leetcode.com/problems/spiral-matrix/
//https://1ilsang.blog.me/221588151803

class Solution {
    private int[] dr = {0,1,0,-1};
    private int[] dc = {1,0,-1,0};

    public List<Integer> spiralOrder(int[][] matrix) {
        LinkedList<Integer> ret = new LinkedList<>();
        if(matrix.length == 0) return ret;

        int n = matrix.length;
        int m = n > 0 ? matrix[0].length : 0;
        boolean[][] visit = new boolean[n][m];
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 0));
        int cnt = 0;

        while(!queue.isEmpty()) {
            int r = queue.peek().r;
            int c = queue.peek().c;
            int d = queue.peek().d;
            ret.add(matrix[r][c]);
            visit[r][c] = true;
            cnt++;
            queue.poll();
            if(cnt == n * m) break;

            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr < 0 || nc < 0 || nr >= n || nc >= m || visit[nr][nc]) {
                d += 1;
                if(d == 4) d = 0;
                nr = r + dr[d];
                nc = c + dc[d];
            }
            queue.offer(new Node(nr, nc, d));
        }

        return ret;
    }

    private class Node {
        int r, c, d;

        Node(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
}