Saturday, September 5, 2020

Unique paths with obstacles

Problem:  A robot is located at the top-left corner(0, 0) of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner (m -1, n-1) of the grid.

Now consider if some obstacles are added to the grids. How many unique paths would there be?


        public static int UniquePathsWithObstacles(int[][] obstacleGrid)

        {

            if (obstacleGrid == null || obstacleGrid.Length == 0)

            {

                return 0;

            }

            int m = obstacleGrid.Length;

            int n = obstacleGrid[0].Length;

            int[,] count = new int[m, n];

            count[0, 0] = obstacleGrid[0][0] == 0 ? 1 : 0;

            for (int i = 1; i < m; ++i)

            {

                if (obstacleGrid[i][0] == 0)

                {

                    count[i, 0] = count[i - 1, 0];

                }

            }

            for (int i = 1; i < n; ++i)

            {

                if (obstacleGrid[0][i] == 0)

                {

                    count[0, i] = count[0, i -1];

                }

            }

            for (int i = 1; i < m; ++i)

            {

                for (int j = 1; j < n; ++j)

                {

                    if (obstacleGrid[i][j] == 0)

                    {

                        count[i, j] = count[i, j - 1] + count[i - 1, j];

                    }

                }

            }

            return count[m - 1, n - 1];

        }

No comments:

Post a Comment