Riddles, brain puzzles and mathematical problems

[BAndrew]

I know it is a long time, but I've got two new problems if anyone is interested.

Problem 1:
Consider this a game.
Starting from the square on the top left corner (marked as green) you must end up in the bottom right square (marked as red). The rules you must follow are the following:

• You can only move up, left, down or right.
  
• The number on the square is the exact number of moves you can make each time before stoping on a square. For example from the start you can go two steps on the right an land on the 3. From there you can go two steps down and one right and land on the 1, and so on.
  

Can you find a solution? What is the best solution? Or equivalently what is the route with the minimum number of steps?
If you feel like it, write an algorithm or a computer program that finds the best possible route (or routes).

Problem 2 (This actually is hard)

What is the average of the number of ways you can express a positive integer as the sum of the squares of two integers.

In other words: Let s>0 be an integer. In average, how many times will it satisfy:
n² + m² = s (where n,m are integers)

For example, if s = 2 we have:

1² + 1² = 2
(-1)² + (-1)² = 2
1² + (-1)² = 2
(-1)² + 1² = 2

So there are 4 ways for number 2.