Блог пользователя mohitn

Автор mohitn, история, 4 года назад, По-английски

You are given a grid of size (m, n) where each (i, j) is the cost of unlocking the door (i, j). You are given a starting position (sx, sy). And you have to collect 2 gems at position (g1x, g1y) and (g2x, g2y).

You only need to unlock a door once, no matter how many times you visit it. Find the minimum cost of collecting both the gems; you can move left, right, down, and up.

I was thinking of Dijkstra but how to manage the state?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Make a dijsktra with $$$(i,j,mask)$$$ where $$$mask$$$ represents what you have collected so far. Your initial state is $$$(s_x,s_y,0)$$$ and you want $$$\text{min } \forall \ (i,j), \ dis(i,j,3).$$$