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 <stdio.h>
2#include <stdlib.h>
3
4int** spiralMatrixIII(int rows, int cols, int rStart, int cStart, int* returnSize, int** returnColumnSizes) {
5 *returnSize = rows * cols;
6 *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
7 for (int i = 0; i < *returnSize; ++i) (*returnColumnSizes)[i] = 2;
8
9 int** result = (int**)malloc(sizeof(int*) * (*returnSize));
10 int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // right, down, left, up
11 int totalSteps = 0, steps = 1;
12 int dir = 0;
13 result[totalSteps++] = (int*)malloc(sizeof(int) * 2);
14 result[0][0] = rStart; result[0][1] = cStart;
15 int r = rStart, c = cStart;
16
17 while (totalSteps < (*returnSize)) {
18 for (int i = 0; i < steps; ++i) {
19 r += directions[dir][0];
20 c += directions[dir][1];
21 if (0 <= r && r < rows && 0 <= c && c < cols) {
22 result[totalSteps] = (int*)malloc(sizeof(int) * 2);
23 result[totalSteps][0] = r;
24 result[totalSteps][1] = c;
25 totalSteps++;
26 }
27 }
28 if (dir == 1 || dir == 3) steps++;
29 dir = (dir + 1) % 4;
30 }
31 return result;
32}This solution initializes variables for direction and position, and iterates until all grid elements are visited. For each direction, it moves step-by-step and checks boundary conditions to ensure valid indices.