Algorithm Hint: Minimum cost path visiting half the cells in a grid?

[meteora]

I am trying solve this a problem: http://usaco.org/index.php?page=viewproblem2&cpid=245

In short:
1. Input is an N x N grid with a non-negative integer in each cell.
2. We can move from one cell to any of its adjacent cell in all four directions.
3. The 'cost' needed to move from one cell to another is the positive difference of their values.
4. We have to find the minimum cost such that we can visit atleast half of the cells with that cost;

I am not being able to think of any solution that runs in time O(N²) or better (N² because of the size of N, any algorithm worse than it will not run within the time limit) for this problem.
So I need a hint on how to solve this problem optimally. Please dont give the solution, only a hint. Thank you.

[naraku9333]

Dijkstra http://en.m.wikipedia.org/wiki/Dijkstra's_algorithm

[meteora]

Thanks. But what I want is not the shortest path. It look more like the travelling salesman problem. I had made a mistake in the question, now i edited it.