顺时针打印矩阵--类实现

顺时针打印矩阵

http://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a

直接撸一个State类。next方法得到下一步坐标。走完则返回(-1,-1).

  • 上下左右用enum表示
  • 位置坐标用pair
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;
    }
};
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务