A 2d grid is given with the number of rows and columns ranging [2, 100]. The grid has one of 0, 1, X, A, B in each of its cell.
- 0 denotes an open road
- 1 denotes a blocked road
- X is a road blocked by a wall which can be broken
- A and B denote collectibles (Only one A and one B are in the grid)
The objective is to start from any cell lying on the perimeter of the grid, collect the two collectibles and leave the grid while minimizing the number of broken walls. A wall once broken becomes an open road. Valid moves are UP, DOWN, LEFT and RIGHT.
I had an intuition about using BFS or Dijkstra but couldn't find my way around. Some help with implementation, idea or approaching such problems will be much appreciated.
P.S. Does anyone have a list of such problems?
Thanks!
Just a guess.
So, we want to minimize the number of broken walls. This makes it seem like movement is free when we're not breaking any walls. So, breaking a wall has a cost of 1 associated with it, and otherwise movement has a cost of 0.
So, I was thinking about when we would need to break a wall. And we would only have to break a wall if it connects two separate components.
So, this means that, we can build a component graph where each connected component is a node, and the outgoing edges of the component node will be these walls which connect to other components.
Once we build the graph, we want to find a path from somewhere on the perimeter to A, then to B, then to the perimeter again to exit, or from somewhere on the perimeter to B, then to A, then to somewhere on the perimeter again.
To do that, we can find the shortest path from A to B, the shortest path from B to some component node which contains a node on the perimeter, and the shortest path from A to some perimeter node.
I might have missed something, but this is what I came up with.
I found a counter example to this where the min cost path was through an intermediate node. That node connected the perimeter, A, and B on disjoint paths but with the minimum cost.
It should still work. You just get from the perimeter to either A or B. It doesn’t matter if you do it through an “intermediate” node.
Find the best answer
I messed up and marked as 1 the road blocked by a wall, but you get the idea
can you provide thee link to the problem?