import java.io.*;
import java.util.*;

class Maze
{
	static Scanner console = new Scanner(System.in);
	protected static int rows;
	protected static int columns;
	protected static char[][] maze;
	protected static Scanner infile;

	public static void main(String[] args)throws FileNotFoundException,
												IOException
	{
		//Maze 1
		infile = new Scanner(new FileReader("maze1.txt"));
		makeMaze();
		System.out.println("Maze 1");
		System.out.println("------");
		print();
		solution();
		System.out.println("Press any key and press enter...");
		console.next();

		//Maze 2
		infile = new Scanner(new FileReader("maze2.txt"));
		makeMaze();
		System.out.println("Maze 2");
		System.out.println("------");
		print();
		solution();
		System.out.println("Press any key and press enter...");
		console.next();

		//Maze 3
		infile = new Scanner(new FileReader("maze3.txt"));
		makeMaze();
		System.out.println("Maze 3");
		System.out.println("------");
		print();
		solution();
		System.out.println("Press any key and press enter...");
		console.next();

		//Maze 4
		infile = new Scanner(new FileReader("maze4.txt"));
		makeMaze();
		System.out.println("Maze 4");
		System.out.println("------");
		print();
		solution();
	}

	//Fills the array from data file which creates the maze
	public static void makeMaze()throws FileNotFoundException,
												IOException
	{
		rows    = infile.nextInt();
		columns = infile.nextInt();
		infile.nextLine();
		maze    = new char[rows][columns];


		for(int x = 0; x < rows; x++)
		{
			String line = infile.nextLine();
			for(int y = 0; y < columns; y++)
				maze[x][y] = line.charAt(y);
		}

		infile.close();
	}

	//Prints the maze
	public static void print()
	{
		for(int x = 0; x < rows; x++)
		{
			for(int y = 0; y < columns; y++)
				System.out.print(maze[x][y]);
			System.out.println();
		}
	}

	//Returns what row the Start is in
	public static int findSx()
	{
		int answer = 0;
		for(int x = 0; x < rows; x++)
			for(int y = 0; y < columns; y++)
				if(maze[x][y] == 'S')
					answer = x;
		return answer;
	}

	//Returns what column the Start is in
	public static int findSy()
	{
		int answer = 0;
		for(int x = 0; x < rows; x++)
			for(int y = 0; y < columns; y++)
				if(maze[x][y] == 'S')
					answer = y;
		return answer;
	}

	//Determines weather or not the maze can be solved
	//If it can be it prints the maze
	public static void solution()
	{
		if(move(findSx(), findSy()))
		{
			System.out.println("\nSolution");
			System.out.println("--------");
			print();
		}
		else
			System.out.println("There is no solution to this maze");
	}

	//Navigates through the maze and finds the if there is a solution
	//Marks its path through the maze with a '+'
	public static boolean move(int row, int col)
	{
		try
		{
			if(maze[row][col] == 'G')
				return true;
			else if(maze[row][col] == '#')
				return false;
			else if(maze[row][col] == '.' || maze[row][col] == 'S')
			{
				if(maze[row][col] != 'S')
					maze[row][col] = '+';

				//North
				if(move(row - 1, col))
				{
					return true;
				}
				//East
				else if(move(row, col + 1))
				{
					return true;
				}
				//South
				else if(move(row + 1, col))
				{
					return true;
				}
				//West
				else if(move(row, col - 1))
				{
					return true;
				}
				//Can't move
				else
				{
					if(maze[row][col] != 'S')
						maze[row][col] = '.';
					return false;
				}
			}
			else
				return false;
		}
		//Moved outside of the maze
		catch(ArrayIndexOutOfBoundsException e)
		{
			return false;
		}
	}
}