Matrix Zigzag Traversal

Matrix Zigzag Traversal

Description:

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]

分析：

遍历数据的下标之和是有规律的，从0增长到行数+列数-2。假设每次遍历的下标之和为k，每次循环让行的下标i从0递增，则列的下标j = k - i。

这里要注意j的范围，如果j < 0直接退出次循环，如果j > cols要continue，因为j是逐渐变小的。

Code：

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
class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @return: a vector of integers
     */
    vector<int> printZMatrix(vector<vector<int> > &matrix) {
        // write your code here
        vector<int> rs;
        if (matrix.size() == 0) {
            return rs;
        }
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        int sum = rows + cols - 2;
        for (int k = 0; k <= sum; k++) {
            vector<int> tem;
            for (int i = 0; i < rows; i++) {
                int j = k - i;
                if (j >= 0 && j < cols) {
                    tem.push_back(matrix[i][j]);
                }
                else if (j < 0) {
                    break;
                }
                else {
                    continue;
                }
            }
            if (k % 2 == 0) {
                for (int t = tem.size() - 1; t >= 0; t--) {
                    rs.push_back(tem[t]);
                }
            }
            else {
                for (int t = 0; t < tem.size(); t++) {
                    rs.push_back(tem[t]);
                }
            }
        }
        
        return rs;
    }
};