leetcode 885. Spiral Matrix III 螺旋矩阵 III

Problem: 885. Spiral Matrix III 螺旋矩阵 III

解题过程

防止越界的问题，所以扩展了边界的，将矩阵复制到中间，方向累加的，取模4，长度len在方向上前进len步，当该格子访问过时，才累加长度len++，避免了越界问题

Code

class Solution { public: vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) { vector<vector<bool>> status( 301, vector<bool>(301, false) ); vector<vector<int>> matrix(301, vector<int>(301, -1)); vector<vector<int>> ret; ret.push_back({rStart, cStart}); rStart += 100; cStart += 100; for(int i = 0; i < rows; i++) { for(int j = 0; j < cols; j++) { matrix[i + 100][j + 100] = 0; } } int len = 1, direction = 1, sum = rows * cols, k, x, y; if(ret.size() == sum) return ret; status[rStart][cStart] = true; while(sum > 0) { k = len; while(k > 0) { x = rStart; y = cStart; if( direction % 4 == 1 ) { ++cStart; } else if( direction % 4 == 2 ) { ++rStart; } else if( direction % 4 == 3 ) { --cStart; } else { --rStart; } if(status[rStart][cStart] == true) { rStart = x; cStart = y; direction = (direction - 1 + 4) % 4; len++; k = 1; continue; } if(matrix[rStart][cStart]==0) { ret.push_back({rStart-100, cStart-100}); if(ret.size() == sum) { return ret; } } status[rStart][cStart] = true; k--; } direction++; } return {{}}; } };

官方题解的答案

class Solution { public: vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) { vector<vector<int>> ret = {{rStart, cStart}}; int sum = rows * cols; if(sum == 1) { return ret; } for(int i = 1; i < rows * cols * 2; i++) { if( (i&1)==1 ) { for(int j = 0; j < i; j++) { cStart++; if(rStart>=0 && rStart < rows && cStart>=0 && cStart < cols) { ret.push_back({rStart, cStart}); } } for(int j = 0; j < i; j++) { rStart++; if(rStart>=0 && rStart < rows && cStart>=0 && cStart < cols) { ret.push_back({rStart, cStart}); } } } else { for(int j = 0; j < i; j++) { cStart--; if(rStart>=0 && rStart < rows && cStart>=0 && cStart < cols) { ret.push_back({rStart, cStart}); } } for(int j = 0; j < i; j++) { rStart--; if(rStart>=0 && rStart < rows && cStart>=0 && cStart < cols) { ret.push_back({rStart, cStart}); } } } if(ret.size() == sum) { return ret; } } return {{}}; } };