## Sunday, July 23, 2017

### [Leetcode] Diagonal Traverse, Solution

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
```Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

```
Note:
1. The total number of elements of the given matrix will not exceed 10,000.

[Thoughts]

1. 如果row < 0, row = 0, 变换通道
2. 如果col < 0, col = 0, 变换通道
3. 如果 col > N, col = N-1, row = row +2;
4. 如果 row > M, row = M-1. col = col +2;

[Code]
``````1:    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
2:      if(matrix.size() == 0 || matrix[0].size() == 0) return {};
3:
4:      vector<int> result;
5:
6:      vector<pair<int, int>> move_delta{{-1, 1}, {1, -1}};
7:
8:      int rows = matrix.size(), cols = matrix[0].size();
9:      int row = 0, col = 0, m = 0;
10:      for(int i = 0; i< rows * cols; i++) {
11:        result.push_back(matrix[row][col]);
12:        row += move_delta[m].first;
13:        col += move_delta[m].second;
14:
15:        if(row >= rows) {
16:          row = rows-1;
17:          col = col +2;
18:          m = 1-m;
19:        }
20:
21:        if(col >= cols) {
22:          col = cols -1;
23:          row = row + 2;
24:          m = 1-m;
25:        }
26:
27:        if(row < 0) {
28:          row = 0;
29:          m = 1-m;
30:        }
31:
32:        if(col < 0) {
33:          col = 0;
34:          m = 1-m;
35:        }
36:      }
37:      return result;
38:    }
``````