gitgud25's blog

Need some help with this grid problem!
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!

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it 
            XXXXXXX
    XA111BX
    X1X0X1X
    X1X1X1X
    X1X1X1X
    X1X1X1X
    X0X0X0X

        Find the best answer

        Spoiler

        I messed up and marked as 1 the road blocked by a wall, but you get the idea

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you provide thee link to the problem?

→ Reply