mohitn's blog

By mohitn, history, 3 years ago, In English

Given a City laid out on a grid, there are R rows of houses and C columns of houses. Each house is known to contain some amount of valuables totaling v_ij. Your task is to rob as many houses as possible to maximize the amount of loot. However, there is a security system in place and if you rob two adjacent houses an alarm will go off Find the optimum set of non-adjacent houses to rob.

Full text and comments »

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

By mohitn, history, 3 years ago, In English

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?

Full text and comments »

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