直接撸一个State类。next方法得到下一步坐标。走完则返回(-1,-1).
class State{
enum Direct{ right, down, left, up};
// 矩阵长宽
int _Max_x;
int _Max_y;
Direct _direct; //当前运行方向
vector<vector<int>> visited; //访问标记0,1矩阵
void __turn_right(){ // 当前方向向右拐
switch( _direct ){
case right: _direct = down; break;
case down: _direct = left; break;
case left: _direct = up; break;
case up: _direct = right; break;
}
}
public:
typedef pair<int, int> Pos;
Pos pos; // 当前位置
State(vector<vector<int>> M, int x, int y){ //构造函数
_Max_x = M.size();
_Max_y = M[0].size();
pos = pair<int, int>{x, y};
_direct = right;
_Max_x = M.size();
_Max_y = M[0].size();
visited = vector<vector<int>> {M.size(), vector<int>(M[0].size(), 0)};
}
Pos next(){ // 走一步, 返回 新坐标(x_,y_);
// 如果走到终点(无路可走) 返回 (-1,-1)
Direct _cur_dir = _direct;
Pos old_p = pos;
Pos p = _pass();
while( p.first == old_p.first && p.second == old_p.second ){
__turn_right();
p = _pass();
if(_cur_dir==_direct) return { -1,-1 };
}
pos = p;
return pos;
}
Pos _pass( ){// 尝试走一步,如果能走,则返回 新坐标(x_,y_);
// 不能走 则返回 老坐标(x,y)
int x,y;
switch( _direct ){
case right: x=pos.first; y=pos.second+1; break;
case down: x=pos.first+1; y=pos.second;break;
case left: x=pos.first; y=pos.second-1;break;
case up: x=pos.first-1; y=pos.second;break;
}
if(x<0 || y<0 || x>=_Max_x || y>=_Max_y || visited[x][y]) return pos;
else{
visited[pos.first][pos.second] = 1;
pos.first = x;
pos.second= y;
return pos;
}
}
};
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> res;
State s(matrix, 0, 0);
for(State::Pos p=s.pos; p.first>=0; ){
res.push_back(matrix[p.first][p.second]);
p=s.next();
}
return res;
}
};