gitgud25's blog

By gitgud25, 4 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it