CODEWITHSUNDEEP
algorithm
aandis
aandis

Reputation: 4212

Number of paths in a rectangular grid with obstacles, after blocking one cell

Given a square grid of size NxN with each cell being empty or having an obstacle, block only one cell so as to minimize the number of paths from top left to bottom right corner. You are only allowed to move one step down or right. After blocking one cell, count the number of paths from top left to bottom right cell. There are always at least 3 empty cell. Two of them are always the start and the finish cell and other one can be any of the remaining cells.

The part of counting the number of paths from top left to bottom right is fairly easy and can be solved easily using dynamic programming.

The part I'm stuck at is the one cell to be blocked to minimize number of paths. Intuition says to search the grid horizontally and block the first cell with max number of incoming and outgoing paths. For example for the grid

..## -> Row 1
..##
....
.... -> Row 4

I would block (3,2) because that would block most of the path and the number of paths remaining would be just one. But I am not entirely confident this is the correct approach. Any insights?

Upvotes: 2

Views: 2424

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726569

The part of counting the number of paths from top left to bottom right is fairly easy and can be solved easily using dynamic programming

This algorithm is an excellent starting point. Consider its implementation that uses an array pathsFromStart[N][N] to store the number of paths from the starting point to a point at (row, col). Run the algorithm again, but now start at the end . This gives you a second 2D array, pathsFromFinish[N][N].

With this two arrays in hand you are ready to find the answer to your original problem: if a point at (row,col) has X paths leading to it from the start, and Y paths leading to it from the finish, then the total number of paths that you would cut by removing that point would be XY. Go through all points on the grid excluding the start, the finish, and the points that are already blocked, and exclude the point with

MAX(pathsFromStart[row][col]*pathsFromFinish[row][col])

Upvotes: 3

Related Questions