題目
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
答案
class Solution {
private boolean valid(int[][] matrix, boolean[][] visited, int x, int y) {
return x >= 0 && x < matrix.length && y>= 0 && y < matrix[0].length && visited[x][y] == false;
}
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
if(matrix.length == 0) return list;
int m = matrix.length, n = matrix[0].length;
boolean[][] visited = new boolean[m][n];
int[][] dxdy = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// go right, down, left, top. Change directions when hit a visited position
int x = 0, y = -1, tx = 0, ty = 0;
int cnt = 0, dir = 0;
while(cnt < m * n) {
tx = x + dxdy[dir][0];
ty = y + dxdy[dir][1];
if(valid(matrix, visited, tx, ty)) {
x = tx;
y = ty;
}
else {
dir = (dir + 1) % 4;
continue;
}
list.add(matrix[x][y]);
visited[x][y] = true;
cnt++;
}
return list;
}
}
