[leetcode 剑指 Offer 29. 顺时针打印矩阵] 方向保持的DFS

// 问题和普通的DFS的区别在于，要求DFS的顺序在一定程度上保持有序，所以不能在传统的DFS内部，去遍历所有可能的方向，必须在DFS的
// 各层之间传递一个方向flag（k）用来告知现在的顺序，然后在出现非法位置的时候，去更新方向flag，并且这种DFS可能会导致死循环，
// 必须要给一个明确的退出条件（已经遍历过的位置的数量）class Solution {
public:const static int Max = 110;int vis[Max][Max];vector<int> ans;void dfs(vector<vector<int>>& matrix ,int x, int y, int dir[4][2], int k, int num) {// 明确的出口条件if(num == matrix.size() * matrix[0].size()) {return ;}ans.push_back(matrix[x][y]);vis[x][y] = 1;int new_x = x + dir[k][0];int new_y = y + dir[k][1];if(new_x >= 0 && new_x < matrix.size() && new_y >= 0 && new_y < matrix[0].size() && vis[new_x][new_y] == 0) {dfs(matrix, new_x, new_y, dir, k, num + 1);}else {// 更新方向flagk = (k + 1) % 4;int new_x = x + dir[k][0];int new_y = y + dir[k][1];dfs(matrix, new_x, new_y, dir, k, num + 1);}}vector<int> spiralOrder(vector<vector<int>>& matrix) {int dir[][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};if(matrix.size() != 0)dfs(matrix, 0, 0, dir, 0, 0);return ans;}
};