CODEWITHSUNDEEP
algorithmmatrixdynamic-programming
Ramesh
Ramesh

Reputation: 46

Dynamic Programming algorithm

Given a matrix of size NxM of 0 and 1. If a mouse is present at [i:j] then it would be 1, otherwise it would be 0. We have to start from [0:0] and reach [n-1:m-1]. We can go down or right only. A mouse at position [i:j] will scare us if we pass through a position [x:y] such that |i-x|+|j-y|<=1.

Find a path in which we are scared by minimum number of distinct mice. Mind the word distinct i.e. a mouse if has scared us then it won't scare us again.

This question was asked in an interview. I tried to solve it by the idea used in general DP problem where we can move down and right and have to find the minimal path, but in all those problems we can take minimum of [i-1:j] and [i:j-1] to find current index minimum and work down all the rows from left to right.

But I am not able to use this idea here, since here a mouse effects 4 cells.

Can someone give the idea how this can be solved?

Upvotes: 3

Views: 651

Answers (4)

TT_ stands with Russia
TT_ stands with Russia

Reputation: 1912

I think the very simple idea (which is probably not complete but is good enough to satisfy an interviewer) is the following.

We assign weights to edges. First, all edges have weight 0. Then consider a mouse in the vertex A. Vertex A has 4 adjacent edges b,c,d,e which connect A with vertices B,C,D,E (case when A has only 2 or 3 adjacent edges is similar). So now we increase weight by 1 for every edge adjacent to vertices B,C,D,E except edges b,c,d,e. Now vertex A adds weight 2 to every MINIMAL weight path "scared by vertex A". A special consideration is needed for any of possible 4 angular mice, where we can increase edge weights by 2.

Now we have a simplest DP problem of finding a path of minimal weight in an integer lattice with down/right moves. My concern is about mice which are separated with only 1 or 2 steps. I quickly checked, and this seems to work, but I don't have a complete proof.

Upvotes: 1

Andrew Tomazos
Andrew Tomazos

Reputation: 68588

If we were only scared by a mouse if we passed through its cell the problem would be trivial. Simply increment the scariness of the path if it passes through one of the mouse cells. By induction on paths we can then memoize the best path from a given cell to the end, and then build our way to the starting point in the usual DP fashion.

The complexity is created by the requirement that if we pass through one of the 5 cells within range of the mouse, then we need to increment the scariness of the path, but only once.

This could be achieved by using a bit field of width N, where N is the number of mouses, and the ith bit indicates if the path causes you to be scared of the ith mouse. The DP can then use a bitwise OR operation with the one vector (0,0,..,0,1,0,..,0,0) where the 1 is in the ith position for the ith mouse.

But then you would have a problem in finding the best partial path, because there is no strict ordering of bit fields with equal weight. Some simple heuristic logic reveals that you only need to be concerned with the distinction in no more than the 9 cell sequare surrounding a mouse. So you can simply keep track of a set of best partial paths near there. The solutions kept near mouse i are the best solutions when not scared by mouse i, and those where you are scared by mouse i. After the proximity is left distinguishing the two is no longer relevant.

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55589

At each cell, store where the most efficient path came from (top or left) (essentially a bit value at each cell).

  1. When considering the cell to the left, if that cell came from the top and there is a mouse right above the current cell, we know it already scared us.

    Illustration: (C is current cell, L is to the left, S is the source for L)

    0S1 <- this mouse already scared us
0LC

  2. When considering the cell to the top, if that cell came from the left and there is a mouse to the left of the current cell, we know it already scared us.

    Illustration: (C is current cell, T is to the top, S is the source for T)

    0ST
01C
 ^- this mouse already scared us

  3. When considering the cell to the top, if that cell has a mouse, we know it already scared us.

    Illustration: (C is current cell)

    01 <- this mouse already scared us
0C

  4. When considering the cell to the left, if that cell has a mouse, we know it already scared us.

    Illustration: (C is current cell)

    01C
 ^- this mouse already scared us

  5. When considering the cell either to the top or to the left, if the current cell has a mouse, we know it already scared us.

    Illustration: (1 is current cell, L is to the left, T is to the top)

    0T
L1 <- this mouse already scared us

Deriving the algorithm from here shouldn't be too difficult.

Upvotes: 0

orezvani
orezvani

Reputation: 3775

I think the simplest (not efficient enough) way to attack this problem is solving a shortest path on a graph of NxM vertices, with the following edge cost function (i and j are graph nodes that refer to cells (i',j') and (i'',j'') in the main matrix):

c(i,j) = 1 if [(i',j') and (i'',j'') are sideByside] && [(i'',j'') is scaring] ,
         0 otherwise

Upvotes: 1

Related Questions