Matrix Zigzag Traversal 185

Question

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in ZigZag-order.

Example

Given a matrix:

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

return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]

Solution

沿着斜线往上走，往下走，再往上走。。。直到最后一个元素。用dx，dy来控制走的方向，每次走到上下边界之后就换方向。

代码如下：

public class Solution {
    /**
     * @param matrix: a matrix of integers
     * @return: an array of integers
     */ 
    public int[] printZMatrix(int[][] matrix) {
        // write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return new int[0];
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int[] res = new int[m * n];
        res[0] = matrix[0][0];
        int count = 1;
        int x = 0;
        int y = 0;
        int dx = -1;
        int dy = 1;

        while(count < m * n){
            if(x + dx >= 0 && y + dy >= 0 && x + dx < m && y + dy < n){
                //如果还没走到头，则继续往斜上方或者斜下方走
                x = x + dx;
                y = y + dy;
            }else{
                //往上走走到头
                if(dx == -1 && dy == 1){
                    //如果还能向右移动则向右移，不行就向下移
                    if(y + dy < n){
                        y++;
                    }else{
                        x++;
                    }
                    dx = 1;
                    dy = -1;
                }else{//往下走走到头
                    //如果还能向下移动则向下移，否则向右移
                    if(x + dx < m){
                        x++;
                    }else{
                        y++;
                    }
                    dx = -1;
                    dy = 1;
                }
            }
            res[count++] = matrix[x][y];
        }

        return res;
    }
}