题目

给定一个 m x n 的矩阵 matrix，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请你使用原地算法完成此操作。

---

示例 1

输入：
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

输出：
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

解释：

• matrix[1][1] 为 0，将第 1 行和第 1 列全部置为 0。

---

示例 2

输入：
matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]

输出：
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

解释：

• matrix[0][0] 和 matrix[0][3] 为 0，将第 0 行、第 0 列和第 3 列全部置为 0。

---

提示

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^{31} <= matrix[i][j] <= 2^{31} - 1

实现

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int flag = 0x3f3f3f3f;
        // 从 0,0 开始 向右边遍历 越界或者遇到flag就右转
        int ty[] = {1 , 0 , -1 , 0};
        int tx[] = {0 , 1 , 0 , -1};
        int i = 0 , j = 0 , dir = 0;

        vector<int> res; 
        while(true) {
	        // 如果发生越界或者位于标记之上 遍历结束
            if(i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size() || matrix[i][j] == flag) return res;
            res.push_back(matrix[i][j]);
		    // 判断是否需要转向
            int ni = i + tx[dir] , nj = j + ty[dir];
            if(ni < 0 || ni >= matrix.size() || nj < 0 || nj >= matrix[0].size() || matrix[ni][nj] == flag) {
                dir += 1; dir %= 4;
                ni = i + tx[dir] , nj = j + ty[dir]; // 转向
            }
            matrix[i][j] = flag; // 留下标记
            i = ni , j = nj; // 去到新的位置
        }
    }
};