# Backtracking, the easiest to understand. O(n) algorithm n= matrix size

• I think this is most straight forward way to solve the problem. The technique is backtracking...
suppose you are standing @i,j, get coded the next legal step. Stop tracking when nowhere else to go.

``````class Solution {
public:
bool  is_legal(vector<vector<int> > &matrix, int i, int j) {
// check if current stand is legal or not
if(!((i >= 0 && i < matrix.size()) && (j >= 0 && j < matrix[0].size()))) return false;
if(matrix[i][j] == -10000) return false;
return true;
}

void solver(vector<vector<int> > &matrix, vector<int> &res, int i, int j, int dirt) {
//dirt
//0: up
//1: down
//2: right
//3: left
//accept condition
if(!(is_legal(matrix, i-1,j) || is_legal(matrix, i+1, j) || is_legal(matrix, i, j+1) || is_legal(matrix, i, j-1) || is_legal(matrix, i, j))) {
return;
} else if(dirt == 0 && !(is_legal(matrix, i-1, j))) {   //change directions
dirt = 2;
} else if(dirt == 2 && !(is_legal(matrix, i, j+1))) {
dirt = 1;
} else if(dirt == 1 && !(is_legal(matrix, i+1, j))) {
dirt = 3;
} else if(dirt == 3 && !(is_legal(matrix, i, j-1))) {
//left
dirt = 0;
}
int curt = matrix[i][j];
res.push_back(curt);   //push into the tracker
matrix[i][j] = -10000;    //mark as visited
if(dirt == 1)    solver(matrix, res, ++i, j, dirt);
if(dirt == 0)    solver(matrix, res, --i, j, dirt);
if(dirt == 2)    solver(matrix, res, i, ++j, dirt);
if(dirt == 3)    solver(matrix, res, i, --j, dirt);
}
vector<int> spiralOrder(vector<vector<int> > &matrix) {
vector<int> v;
solver(matrix, v, 0, 0, 2);
return v;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.