题解 | #逆时针吃草#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> eatGrass(vector<vector<int> >& matrix) {
        // write code here
        a = matrix;
        n = matrix[0].size();
        m = matrix.size();
        dfs(0, 0, n - 1, m - 1);
        return ans;
    }

    int n, m;
    vector<vector<int> > a;
    vector<int> ans = vector<int>();

    // 题目的 y 轴是向下的，通过转换器访问 matrix 即可
    int get(int x, int y) {
        return a[m - 1 - y][x];
    }

    // 从左下角 [sx, sy] 到右上角 [rtx, rty]，顺时针走一圈
    void dfs(int sx, int sy, int rtx, int rty) {
        if (!(sx <= rtx && sy <= rty)) return;
        // cout << "good";
        if (sx == rtx) { // 仅剩最后一列
            for (int y = sy; y <= rty; ++y) {
                ans.push_back(get(sx, y));
            }
            return;
        }
        if (sy == rty) { // 仅剩最后一行
            for (int x = sx; x <= rtx; ++x) {
                ans.push_back(get(x, sy));
            }
            return;
        }
        // 走一圈
        int x = sx, y = sy;
        for (; y < rty; ++y) { // 上
            ans.push_back(get(x, y));
        }
        for (; x < rtx; ++x) { // 右
            ans.push_back(get(x, y));
        }
        for (; y > sy; --y) { // 下
            ans.push_back(get(x, y));
        }
        for (; x > sx; --x) { // 左，注意不要重复放入起点 [sx, sy]
            ans.push_back(get(x, y));
        }
        dfs(sx + 1, sy + 1, rtx - 1, rty - 1);
    }

};