54. Spiral Matrix-蒲公英云

54. Spiral Matrix

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

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

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

题意：
给定一个m行n 列的矩阵，返回这个矩阵的顺时针螺旋序的各个元素。
即：从先顺时针遍历最外圈，再顺时针遍历此外圈···。

方法：
显然，这就是一个模拟的问题了，跟着问题的要求实现一遍就行。
但是在实现的过程中，需要注意以下几点：

顺时针的螺旋，先左->右，再上->下，再右->左，最后下到上。
每旋转一圈，里面的半径就会变小，同一个位置的元素不能被遍历两次。

基于这两个观察，有两种实现方式：
一、
使用一个标识来标识，某个位置是否被访问过。当遍历的过，发现当前位置越界、或已经被遍历过了，那么就需要改变遍历的方向。我们使用direct[3]={0,1,-1} 表示横竖方向的三种增量。

class Solution { 
public:
    struct _node
    { 
        int x, y;
        bool operator <(const _node & rh) const{ 
            return x < rh.x || (x == rh.x && y < rh.y);
        }
    };
    vector<int> spiralOrder(vector<vector<int>>& matrix) { 
        vector<int> rst;
        int m = matrix.size(), n = 0;
        if (m > 0)
        { 
            n = matrix[0].size();
        }
        int x = 0, y = 0;
        _node node = {  x, y };
        set<_node>  flags;
        int xd = 1, yd = 0;
        int direct[3] = {  0, 1, -1 };
        while (rst.size() < m*n)
        { 
            if (flags.find({ y,x}) == flags.end() && (x < n) && y < m && y >= 0 && x >= 0)
            //说明目前的增长方向是合理的
            { 
                rst.push_back(matrix[y][x]);
                flags.insert({  y,x });
            }
            else
            //目前增长方向需要变更
            { 
                x -= xd;//取消之前的一步增长
                y -= yd;//取消之前的一步增长
                xd = yd = 0;
                for (int j = 0; j < 3; j++)
                //首先尝试变更 横轴
                { 
                    xd = direct[j];
                    if (flags.find({  y , x + xd }) == flags.end() && y < m && (x + xd) < n && y >= 0 && (x + xd) >= 0)
                    { 
                        goto label;
                    }
                }
                xd = 0;
                for (int j = 0; j < 3; j++)
                //其次考虑变更纵轴
                { 
                    yd = direct[j];
                    if (flags.find({  y + yd, x  }) == flags.end() && (y + yd) < m && (x) < n && (y + yd) >= 0 && (x ) >= 0)
                    { 
                        goto label;
                    }
                }
                yd = 0;
                break;//无法再进行下去，说明整个矩阵已经遍历完全。
            }
            label:
            x += xd;
            y += yd;
        }
        return rst;
    }
};

二、
使用 4个变量来维护上，下、左、右已经遍历的顶部行、头部行、左列、右列。

class Solution { 
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) { 
        vector<int> rst;
        int m = matrix.size(), n = 0;// MxN
        if (m > 0)
        { 
            n = matrix[0].size();
        }
        int x = 0, y = 0;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        int direction = 0;
        while (rst.size()<m*n)
        { 
            if (direction == 0)
            { 
                for (int i = left; i <= right; i++)
                { 
                    rst.push_back(matrix[x][i]);
                }
                top++;//遍历了顶部
                y=right;
            }
            else if (direction == 1)
            { 
                for (int i = top; i <= bottom; i++)
                { 
                    rst.push_back(matrix[i][y]);
                }
                right--;//遍历了右列
                x=bottom;
            }
            else  if (direction == 2)
            { 
                for (int i = right; i >= left; i--)
                { 
                    rst.push_back(matrix[x][i]);
                }
                bottom--;//遍历的底部
                y=left;
            }
            else if(direction == 3)
            { 
                for (int i = bottom; i >= top; i--)
                { 
                    rst.push_back(matrix[i][y]);
                }
                left++;//遍历了左列
                x=top;
            }
            direction = (direction + 1 ) % 4;
        }
        return rst;
    }
};