Balls rolling in the maze

Rat in a Maze

Given a 2D array maze[][] of size M x N, one ball is dropped in each column. The maze is open on the top and bottom sides. Each cell in the box has a diagonal wall spanning two corners of the cell that can redirect a ball to the right or to the left. A cell that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the maze as ‘R‘. A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the maze as ‘L‘. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits an “R” cell on the left and “L” cell on the right or if a cell redirects the ball into either wall of the maze. Return an array answer of size N where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

Examples:

Input: maze[][] = {{‘R’, ‘R’, ‘R’, ‘L’, ‘L’}, {‘R’, ‘R’, ‘R’, ‘R’, ‘L’}, {‘L’, ‘L’, ‘L’, ‘R’, ‘R’}, {‘R’, ‘R’, ‘R’, ‘L’, ‘L’}, {‘L’, ‘L’, ‘L’, ‘L’, ‘L’}}
Output: [1, 2, -1, -1, -1]
Explanation: The balls fall as explained below:

Ball 0 is dropped at column 0 and falls out of the box at column 1.
Ball 1 is dropped at column 1 and falls out of the box at column 2.
Ball 2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.
Ball 3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.
Ball 4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.

Input: maze[][] = {{‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’}, {‘L’, ‘L’, ‘L’, ‘L’, ‘L’, ‘L’}, {‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’}, {‘L’, ‘L’, ‘L’, ‘L’, ‘L’, ‘L’}}
Output: [0, 1, 2, 3, 4, -1]

Approach: To solve the problem, follow the below idea:

The problem can be solved using Dynamic Programming on Grids. Iterate over all the balls one by one and find the final column for each of the ball. Also maintain a dp[][] array such that dp[i][j] stores the final column if the ball lands on cell (i, j).

To find the column in which the ball will fall, we can use a recursive function which checks where will the ball go if it reaches the cell by checking the conditions for the ball to go right and left.

The ball will go to the right if the current cell has an ‘R’ and is not the last cell of the row and the cell to the immediate right should not have an ‘L’ in it.
The ball will go to the left if the current cell has an ‘L’ and is not the first cell of the row and the cell to the immediate left should not have an ‘R’ in it.

Step-by-step algorithm:

Maintain a recursive function, say findColumn(rowNo, colNo) to find the final column for a ball in the cell (rowNo, colNo).
Also maintain a dp[][] array to store the answer for the already visited cells.
Check if the ball can go the right column in the next row by checking the above-mentioned conditions.
Similarly, check if the ball can go the right column in the next row by checking the above-mentioned conditions.
Return the final answer.

Below is implementation of the algorithm:

C++

#include <bits/stdc++.h>
using namespace std;

// function to find the final column for a ball in cell
// (rowNo, colNo)
int findColumn(vector<vector<int> >& maze, int& M, int& N,
            vector<vector<int> >& dp, int rowNo,
            int colNo)
{
    // Base case
    if (rowNo >= M)
        return colNo;

    // Check if we already know the final column for this
    // cell (rowNo, colNo)
    if (dp[rowNo][colNo] != -2)
        return dp[rowNo][colNo];

    int nextCol = -1;

    // Check if the ball can move to the right
    if (maze[rowNo][colNo] == 'R' && colNo + 1 < N
        && maze[rowNo][colNo + 1] != 'L') {
        nextCol = findColumn(maze, M, N, dp, rowNo + 1,
                            colNo + 1);
    }

    // Check if the ball can move to the left
    if (maze[rowNo][colNo] == 'L' && colNo - 1 >= 0
        && maze[rowNo][colNo - 1] != 'R') {
        nextCol = findColumn(maze, M, N, dp, rowNo + 1,
                            colNo - 1);
    }

    // Memoize the result and return the final column
    return dp[rowNo][colNo] = nextCol;
}

// Function to find the final positions of the ball for each
// starting column
vector<int> solve(vector<vector<int> >& maze)
{
    int M = maze.size(), N = maze[0].size();

    // ans vector to store the final positions
    vector<int> ans(N, 0);

    // dp[][] to store the column that the ball falls out of
    // at the bottom
    vector<vector<int> > dp(M, vector<int>(N, -2));

    // Iterate through each starting column and find the
    // final position of the ball
    for (int i = 0; i < N; i++) {
        ans[i] = findColumn(maze, M, N, dp, 0, i);
    }
    return ans;
}

int main()
{
    // Input
    vector<vector<int> > maze
        = { { 'R', 'R', 'R', 'L', 'L' },
            { 'R', 'R', 'R', 'R', 'L' },
            { 'L', 'L', 'L', 'R', 'R' },
            { 'R', 'R', 'R', 'L', 'L' },
            { 'L', 'L', 'L', 'L', 'L' } };
    vector<int> ans = solve(maze);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}

Java

import java.util.Arrays;

public class Main {
    // Function to find the final column the ball falls out of at the bottom for 
    // a given starting column
    static int findColumn(char[][] maze, int M, int N, int[][] dp, int rowNo, int colNo) {
        // Base case
        if (rowNo >= M)
            return colNo;
        if (dp[rowNo][colNo] != -2)
            return dp[rowNo][colNo];
        int nextCol = -1;
        if (maze[rowNo][colNo] == 'R' && colNo + 1 < N && maze[rowNo][colNo + 1] != 'L')
            nextCol = findColumn(maze, M, N, dp, rowNo + 1, colNo + 1);
        // Check if the ball can move to left
        if (maze[rowNo][colNo] == 'L' && colNo - 1 >= 0 && maze[rowNo][colNo - 1] != 'R')
            nextCol = findColumn(maze, M, N, dp, rowNo + 1, colNo - 1);
        // Memoize the result and 
        // return the final column
        dp[rowNo][colNo] = nextCol;
        return dp[rowNo][colNo];
    }
    static int[] GFG(char[][] maze) {
        int M = maze.length;
        int N = maze[0].length;
        // ans array to store the final positions
        int[] ans = new int[N];
        // dp[][] to store the column that the ball falls out of at the bottom
        int[][] dp = new int[M][N];
        for (int[] row : dp)
            Arrays.fill(row, -2);
        for (int i = 0; i < N; i++)
            ans[i] = findColumn(maze, M, N, dp, 0, i);

        return ans;
    }
    public static void main(String[] args) {
        // Input
        char[][] maze = {
                {'R', 'R', 'R', 'L', 'L'},
                {'R', 'R', 'R', 'R', 'L'},
                {'L', 'L', 'L', 'R', 'R'},
                {'R', 'R', 'R', 'L', 'L'},
                {'L', 'L', 'L', 'L', 'L'}
        };
        // Solve the problem
        int[] ans = GFG(maze);
        for (int i : ans)
            System.out.print(i + " ");
        System.out.println();
    }
}

using System;
using System.Collections.Generic;

public class Program
{
    // Function to find the final column for a ball in cell
    // (rowNo, colNo)
    public static int FindColumn(List<List<char>> maze, ref int M, ref int N,
               List<List<int>> dp, int rowNo,
               int colNo)
    {
        // Base case
        if (rowNo >= M)
            return colNo;

        // Check if we already know the final column for this
        // cell (rowNo, colNo)
        if (dp[rowNo][colNo] != -2)
            return dp[rowNo][colNo];

        int nextCol = -1;

        // Check if the ball can move to the right
        if (maze[rowNo][colNo] == 'R' && colNo + 1 < N
            && maze[rowNo][colNo + 1] != 'L')
        {
            nextCol = FindColumn(maze, ref M, ref N, dp, rowNo + 1, colNo + 1);
        }

        // Check if the ball can move to the left
        if (maze[rowNo][colNo] == 'L' && colNo - 1 >= 0
            && maze[rowNo][colNo - 1] != 'R')
        {
            nextCol = FindColumn(maze, ref M, ref N, dp, rowNo + 1, colNo - 1);
        }

        // Memoize the result and return the final column
        return dp[rowNo][colNo] = nextCol;
    }

    // Function to find the final positions of the ball for each
    // starting column
    public static List<int> Solve(List<List<char>> maze)
    {
        int M = maze.Count, N = maze[0].Count;

        // ans list to store the final positions
        List<int> ans = new List<int>(N);

        // dp[,] to store the column that the ball falls out of
        // at the bottom
        List<List<int>> dp = new List<List<int>>();
        for (int i = 0; i < M; i++)
        {
            dp.Add(new List<int>(N));
            for (int j = 0; j < N; j++)
            {
                dp[i].Add(-2);
            }
        }

        // Iterate through each starting column and find the
        // final position of the ball
        for (int i = 0; i < N; i++)
        {
            ans.Add(FindColumn(maze, ref M, ref N, dp, 0, i));
        }
        return ans;
    }

    public static void Main()
    {
        // Input
        List<List<char>> maze = new List<List<char>>()
        {
            new List<char> { 'R', 'R', 'R', 'L', 'L' },
            new List<char> { 'R', 'R', 'R', 'R', 'L' },
            new List<char> { 'L', 'L', 'L', 'R', 'R' },
            new List<char> { 'R', 'R', 'R', 'L', 'L' },
            new List<char> { 'L', 'L', 'L', 'L', 'L' }
        };
        
        List<int> ans = Solve(maze);
        for (int i = 0; i < ans.Count; i++)
        {
            Console.Write(ans[i] + " ");
        }
        Console.WriteLine();
    }
}

Javascript

function findColumn(maze, M, N, dp, rowNo, colNo) {
    // Base case
    if (rowNo >= M) {
        return colNo;
    }

    // Check if we already know the final column for this cell (rowNo, colNo)
    if (dp[rowNo][colNo] !== -2) {
        return dp[rowNo][colNo];
    }

    let nextCol = -1;

    // Check if the ball can move to the right
    if (maze[rowNo][colNo] === 'R' && colNo + 1 < N && maze[rowNo][colNo + 1] !== 'L') {
        nextCol = findColumn(maze, M, N, dp, rowNo + 1, colNo + 1);
    }

    // Check if the ball can move to the left
    if (maze[rowNo][colNo] === 'L' && colNo - 1 >= 0 && maze[rowNo][colNo - 1] !== 'R') {
        nextCol = findColumn(maze, M, N, dp, rowNo + 1, colNo - 1);
    }

    // Memoize the result and return the final column
    dp[rowNo][colNo] = nextCol;
    return dp[rowNo][colNo];
}

function solve(maze) {
    const M = maze.length;
    const N = maze[0].length;

    // ans array to store the final positions
    const ans = Array(N).fill(0);

    // dp[][] to store the column that the ball falls out of at the bottom
    const dp = Array.from({ length: M }, () => Array(N).fill(-2));

    // Iterate through each starting column and find the final position of the ball
    for (let i = 0; i < N; i++) {
        ans[i] = findColumn(maze, M, N, dp, 0, i);
    }

    return ans;
}

// Input
const maze = [['R', 'R', 'R', 'L', 'L'],
    ['R', 'R', 'R', 'R', 'L'],
    ['L', 'L', 'L', 'R', 'R'],
    ['R', 'R', 'R', 'L', 'L'],
    ['L', 'L', 'L', 'L', 'L']];

// Output
const ans = solve(maze);
console.log(ans.join(" "));

Python3

def find_column(maze, M, N, dp, rowNo, colNo):
    # Base case
    if rowNo >= M:
        return colNo

    # Check if we already know the final column for this cell (rowNo, colNo)
    if dp[rowNo][colNo] != -2:
        return dp[rowNo][colNo]

    nextCol = -1

    # Check if the ball can move to the right
    if maze[rowNo][colNo] == 'R' and colNo + 1 < N and maze[rowNo][colNo + 1] != 'L':
        nextCol = find_column(maze, M, N, dp, rowNo + 1, colNo + 1)

    # Check if the ball can move to the left
    if maze[rowNo][colNo] == 'L' and colNo - 1 >= 0 and maze[rowNo][colNo - 1] != 'R':
        nextCol = find_column(maze, M, N, dp, rowNo + 1, colNo - 1)

    # Memoize the result and return the final column
    dp[rowNo][colNo] = nextCol
    return dp[rowNo][colNo]

def solve(maze):
    M = len(maze)
    N = len(maze[0])

    # ans list to store the final positions
    ans = [0] * N

    # dp[][] to store the column that the ball falls out of at the bottom
    dp = [[-2] * N for _ in range(M)]

    # Iterate through each starting column and find the final position of the ball
    for i in range(N):
        ans[i] = find_column(maze, M, N, dp, 0, i)

    return ans

# Input
maze = [['R', 'R', 'R', 'L', 'L'],
        ['R', 'R', 'R', 'R', 'L'],
        ['L', 'L', 'L', 'R', 'R'],
        ['R', 'R', 'R', 'L', 'L'],
        ['L', 'L', 'L', 'L', 'L']]

ans = solve(maze)

# Output
for i in ans:
    print(i, end=" ")
print()

# This code is contributed by shivamgupta310570

Output

1 2 -1 -1 -1

Time Complexity: O(N * M), M is the number of rows and N is the number of columns of the input matrix maze[][].
Auxiliary Space: O(N * M)

Tags:

#Algorithms-Dynamic Programming #DSA #Dynamic Programming #Matrix #Dynamic Programming #Matrix

Rat in a Maze

Balls rolling in the maze

Contact Us