class Solution {
private:
vector<int> res;
vector<vector<int>> st;
int end=0;
public:
void dfs(int x,int y,int l,vector<vector<int>> &matrix){
if(end) return;
res.push_back(matrix[x][y]);
st[x][y]=1;
if(l==0){
if(y<matrix[0].size()-1&&!st[x][y+1]) dfs(x,y+1,0,matrix);
else if(x<matrix.size()-1&&!st[x+1][y]) dfs(x+1,y,1,matrix);
else{
end=1;
return ;
}
}
if(l==1){
if(x<matrix.size()-1&&!st[x+1][y]) dfs(x+1,y,1,matrix);
else if(y>0&&!st[x][y-1]) dfs(x,y-1,2,matrix);
else{
end=1;
return ;
}
}
if(l==2){
if(y>0&&!st[x][y-1]) dfs(x,y-1,2,matrix);
else if(x>0&&!st[x-1][y]){
dfs(x-1,y,3,matrix);
}
else{
end=1;
return ;
}
}
if(l==3){
if(x>0&&!st[x-1][y]) dfs(x-1,y,3,matrix);
else if(y<matrix[0].size()-1&&!st[x][y+1]) dfs(x,y+1,0,matrix);
else{
end=1;
return ;
}
}
}
vector<int> printMatrix(vector<vector<int> > matrix) {
if(!matrix.size()||!matrix[0].size()) return res;
st=vector(matrix.size(),vector<int>(matrix[0].size()));
dfs(0,0,0,matrix);
return res;
}
};