Received this question during a phone interview recently. Wasn't able to come up with an answer. Here is the question:
Given a M * N grid with non-negative values on each cell, representing the height of each cell. Your task is to walk from top left corner to bottom right corner. Rule is, you can only walk from cell with higher height to lower one (i.e. to walk from cell i to j, we should have grid[i] >= grid[j]), but not the other way around. Also your walk is four-directional.
Q1: Are are able to reach the target with the given cell?
Q2: If not, now you can change the height of each cell arbitrarily (can only increase the height), what is the minimum total change cost (i.e. if we change from 1 to 2, cost is 1) so that we can reach the target?

Q1 is straightforward, and I will given an example for Q2 to explain:

Given grid is:

1 2
3 4

Min cost change will be following, with total cost of 4

4 2
4 4

Another example:

99  105   105  105  105  105
99  888   99   99   99   105
99  888   99   888  99   105
99  99    99   888  102   1

Min cost is 6, by chaning the starting cell's 99 to 105