Dynamic Programming algorithm

Question

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?

Answer 1

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

Answer 2

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.