Sponsored
Sponsored
Use depth-first search (DFS) to simulate the movement of each ball from the top to the bottom, keeping track of the ball's column. If a ball encounters a 'V' shape or hits the wall, it gets stuck. This approach simulates the scenario for each ball individually.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for the result and recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4int dfs(int **grid, int m, int n, int row, int col) {
5 if (row == m) return col;
6 int nextCol = col + grid[row][col];
7 if (nextCol < 0 || nextCol >= n || grid[row][nextCol] != grid[row][col]) return -1;
8 return dfs(grid, m, n, row + 1, nextCol);
9}
10
11int* findBall(int** grid, int gridSize, int* gridColSize, int* returnSize) {
12 *returnSize = *gridColSize;
13 int *result = (int *)malloc((*gridColSize) * sizeof(int));
14 for (int i = 0; i < *gridColSize; ++i) {
15 result[i] = dfs(grid, gridSize, *gridColSize, 0, i);
16 }
17 return result;
18}We define a recursive depth-first search function that simulates the ball's journey through the grid. It returns the column at the bottom if the ball falls through, or -1 if it gets stuck. We iterate over each column to drop a ball and compute its result using this DFS function.
Utilize nested loops to simulate the motion of each ball iteratively instead of using recursion. It tracks each movement step-by-step across the grid, calculates next positions, transitions to subsequent rows, and monitors for blockages or exits.
Time Complexity: O(m * n), driven by iterating through all cells.
Space Complexity: O(n), where n stands for the result array requirement.
1#
The C code iteratively calculates the trajectory for each ball using nested loops without recursion. Starting at each column, the ball’s path is calculated through rows, checking for possible redirections or blockages and finalizing the column or stuck status.