Sponsored
Sponsored
To simulate walking in a spiral, maintain a direction vector and a step count for each segment. Initially face east, and keep track of direction changes in the order of east, south, west, north. After two direction changes, increase the step count which determines how far to walk in the current direction before turning.
Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.
1#include <vector>
2
3using namespace std;
4
5vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
6 vector<vector<int>> result;
7 result.push_back({rStart, cStart});
8 int numSteps = 1;
9 while (result.size() < rows * cols) {
10 for (int i = 0; i < 2; ++i) {
11 for (int j = 0; j < numSteps; ++j) {
12 if (result.size() == rows * cols) return result;
13 if (i == 0) cStart++;
14 if (i == 1) rStart++;
15 if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
16 result.push_back({rStart, cStart});
17 }
18 }
19 }
20 numSteps++;
21 for (int i = 0; i < 2; ++i) {
22 for (int j = 0; j < numSteps; ++j) {
23 if (result.size() == rows * cols) return result;
24 if (i == 0) cStart--;
25 if (i == 1) rStart--;
26 if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
27 result.push_back({rStart, cStart});
28 }
29 }
30 }
31 numSteps++;
32 }
33 return result;
34}This solution involves incrementing/decrementing rows and columns while checking whether they're within bounds. The number of steps increases after every two directions.