Solving Maze Problems

You are asked to navigate a maze. Initially, you are placed at a certain position (the starting position) in the maze and is asked to try to reach another position (the goal position). Positions in the maze will either be open or blocked with an obstacle. Positions are identified by (x,y) coordinates. There are some rules in this problem:

The size of a maze map size is 10 x 10.
The starting and the goal positions can be anywhere in the map.
At any moment, you can only move 1 step in one of 4 directions. Valid directions are: East, West, South, North.
You can only move to positions without obstacles and must stay within the maze.
You have to mark the solution path with ‘+’ in the maze, and DO NOT mark the path which does not lead to the goal position.
If there is no solution path, just output “No solution”.

Technical Specification

To make this problem more concrete, we will consider the maze represented by a matrix of characters. A maze includes:

A starting position: ‘S’, position where you start.
A goal position: ‘G’, goal position.
Obstacles: ‘#’, positions where you cannot move to.
Open positions: ‘.’, positions where you can move to.
Footprints: ‘+’ , footprints you made. Note that each of an input maze has only one solution path.

Output

There is an empty line at the end of output.