Given an integern, generate a square matrix filled with elements from 1 ton2in spiral order.

For example,
Givenn=3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        boolean[][] visited = new boolean[n][n];
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int step = 1;
        int x = 0, y = 0, method = 0;

        if (n == 1) return new int[][]{{1}};

        while (step <= n * n){
            matrix[x][y] = step;
            visited[x][y] = true;

            int xx = x + dirs[method][0];
            int yy = y + dirs[method][1];

            if (xx < 0 || xx >= n || yy < 0 || yy >= n || visited[xx][yy]){
                method = (method + 1) % 4;
                xx = x + dirs[method][0];
                yy = y + dirs[method][1];
            }

            x = xx;
            y = yy;
            step++;
        }

        return matrix;
    }
}