//章节 - 数组和字符串

//二、二维数组简介

//1.对角线遍历

/*

算法思想：

    有类题属于直观上很好理解，但是写起来却不知如何下手。这题就属于此类。

    这道题好处是给了一个图例，而图例又不像另一种4向（右，左下，下，右上）画法让人误导，而是对角线，方向是右上、左下依次交替。因此，只需确定每条对角线的起点，由起点向右上延伸直到边界，再根据当前所在的行数判断是否需要逆序即可。每行的起始点如下：从[0,0]向下延伸到[m-1,0]，再向右延伸到[m-1][n-1]

*/

//算法实现：

class Solution {

public:

    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {

        vector<int> result;

        int m = matrix.size();

        if(m == 0)

            return result;

        int n = matrix[0].size();

        if(n == 0)

            return result;

        for(int i = 0, j = 0; i+j < m+n-1; ) {  // 起点位置(0,0)->(m-1,0)->(m-1,n-1)，然后每个起点右上延伸直到边界，每隔一行翻转一下

            vector<int> tmp;

            bool bflag = (i+j) & 0x01;

            if(i < m) {

                for(int x = i, y = 0; x>=0 && y<n; x--,y++) {

                    tmp.push_back(matrix[x][y]);

                }

                i++;

            }

            else if(i >= m) {

                for(int x = i-1, y = j+1; x>=0 && y<n; x--,y++) {

                    tmp.push_back(matrix[x][y]);

                }

                j++;

            }

            if(bflag) { // bflag需要判断i+j，但是由于上面i和j已经累加了，所以要用bflag判断

                reverse(tmp.begin(), tmp.end());

            }

            result.insert(result.end(), tmp.begin(), tmp.end());

        }

        return result;

    }

};