# A Grid Search Problem

There are several questions on DP, some may do the grid search, find the path, like going through the maze. Also note that when doing the recursive searching, if not do the "memory", sometime, you got O(n^2), when doing the recursion, if the possible state can be expressed as a m*n matrix, then the running time complexity will be just O(mn).

Below is a question I collected, however the question was not articulated clearly. Beside, I personally think Dijkstra is also a DP problem. 

Given an nXn grid of integers, staring and ending cells , write an algorithm to find the path with highest value.

1) You can move right, left, top and bottom
2) You can visit a cell only once

The problem sounds like a dynamic program at first. But it is a Dijkstra's algorithm applies on the graph where we have Left, Right, Up, Down pointers. We need a queue to store the visited node and need to mark node explored. The algorithm take O(E+V). By the way Dijkstra's algorithm is a dynamic programming approach.

A modified Dijkstra can be used to find the sequence of move from starting cell (S) to target cell (T). We keep a max-heap, and at every stage max-value unvisited cell is extracted from the heap. Time complexity seems to be O(n^2 log n) as the max path length could be O(n^2).

FindMax(source,dest,current_sum){
  if(source==dest)
    return current_sum
  else{
    source.visited=true
    int up_sum=down_sum=left_sum=right_sum=-1
    if(source.up not visited)
         int up_sum=FindMax(source.up,dest,current_sum+source_value)
    if(source.down not visited)
      int down_sum=FindMax(source.down,dest,current_sum+source_value)
    if(source.left not visited)
      int left_sum=FindMax(source.left,dest,current_sum+source_value)
       if(source.right not visited)
      int right_sum=FindMax(source.right,dest,current_sum+source_value)
    source.visited=false
    return max(up_sum,down_sum,left_sum,right_sum)
  }
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥