Leecode---顺时针打印矩阵

2019-07-22

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路：

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16 
从1开始顺时针打印

我们从第一个点 1 开始，按着上右下左的顺序遍历矩阵即可，注意遍历时候矩阵不要“碰壁“。

小技巧就是：开始方向从右开始，每次碰壁就进行转向

碰壁是两种情况：

最外围的 rows, cols 越界，如 4 再往右走，cols 就越界了，所以要向下转
内围的遍历时候碰到标记为 true 的墙壁，如 5=>6=>7 就不能再碰到 8，因为 8 在外围遍历时候已经标记为 true。所以要向下转向到 7=>11

C++ 代码

class Solution{
public:
	vector<int> printMatrix(vector<vector<int>> matrix){
		vector<int> res;
		if(matrix.empty()) return res;
		int rows = matrix.size(), cols = matrix[0].size();
		vector<vector<bool>> st(rows, vector<bool>(cols, false));
        int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
		int x = 0, y = 0, direct = 1; //初始位置(0,0),d 控制方向
        for(int k = 0; k < rows * cols; k++){
        	res.push_back(matrix[x][y]);
        	st[x][y] = true;
            int a = x + dx[direct], b = y + dy[direct];
            if(a<0 || a>=rows || b<0 || b>=cols || st[a][b])//碰壁就转头
            {
            	direct = (direct + 1) % 4;
            	a = x + dx[direct], b = y + dy[direct];
            }
        	x = a, y = b;//不要忘记更新坐标值
        }
		return res;
	}
};