#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <vector>

void openInputFile(char *filename, std::vector<std::vector<int> > &map)
{
	FILE *fp = fopen(filename, "r");
	if (!fp) {
		fprintf(stderr, "can't open %s\n", filename);
		exit(0);
	}

	for(;;) {
		const int N = 1024;
		char buf[N];

		if (fgets(buf, N, fp) == NULL) {
			break;
		}

		std::vector<int> line;
		for(int i = 0; i < N; ++i) {
			if (buf[i] == 0) {
				break;
			}

			line.push_back(buf[i]);
		}

		map.push_back(line);
	}
}

void printMap(std::vector<std::vector<int> > &map)
{
	for(int y = 0; y < map.size(); ++y) {
		std::vector<int> &line = map[y];
		for(int x = 0; x < line.size(); ++x) {
			fprintf(stdout, "%c", line[x]);
			if (line[x] == '\n') {
				break;
			}
		}
	}
}

void findChar(const std::vector<std::vector<int> > &map, char c, int &sx, int &sy)
{
	for(int y = 0; y < map.size(); ++y) {
		const std::vector<int> &line = map[y];
		for(int x = 0; x < line.size(); ++x) {
			if (line[x] == c) {
				sx = x;
				sy = y;
				return;
			}
		}
	}
}

void findRouteSub(const std::vector<std::vector<int> > &map, std::vector<std::vector<int> > &route, int cx, int cy, int d)
{
	if (d < route[cy][cx]) {
		route[cy][cx] = d;
	} else {
		return;
	}

	if (cy - 1 >= 0 && map[cy - 1][cx] == ' ') {
		findRouteSub(map, route, cx, cy - 1, d + 1);
	}
	if (cy + 1 < map.size() && map[cy + 1][cx] == ' ') {
		findRouteSub(map, route, cx, cy + 1, d + 1);
	}
	if (cx - 1 >= 0 && map[cy][cx - 1] == ' ') {
		findRouteSub(map, route, cx - 1, cy, d + 1);
	}
	if (cx + 1 < map[cy].size() && map[cy][cx + 1] == ' ') {
		findRouteSub(map, route, cx + 1, cy, d + 1);
	}
}

void findRoute(const std::vector<std::vector<int> > &map, std::vector<std::vector<int> > &route)
{
	for(int i = 0; i < map.size(); ++i) {
		std::vector<int> line(map[i].size(), INT_MAX);
		route.push_back(line);
	}

	int sx;
	int sy;
	findChar(map, 'S', sx, sy);
	findRouteSub(map, route, sx, sx, 0);
}

void updateMap(std::vector<std::vector<int> > &map, const std::vector<std::vector<int> > &route)
{
	int cx;
	int cy;
	findChar(map, 'G', cx, cy);

	for(;;) {
		if (cy - 1 >= 0 && route[cy - 1][cx] < route[cy][cx]) {
			cy = cy - 1;
		} else if (cy + 1 < map.size() && route[cy + 1][cx] < route[cy][cx]) {
			cy = cy + 1;
		} else if (cx - 1 >= 0 && route[cy][cx - 1] < route[cy][cx]) {
			cx = cx - 1;
		} else if (cx + 1 < map[cy].size() && route[cy][cx + 1] < route[cy][cx]) {
			cx = cx + 1;
		}

		if (map[cy][cx] == 'S') {
			break;
		}

		map[cy][cx] = '$';
	}
}

int main(int argc, char *argv[])
{
	std::vector<std::vector<int> > map;
	std::vector<std::vector<int> > route;
	openInputFile(argv[1], map);
	findRoute(map, route);
	updateMap(map, route);
	printMap(map);
	return 0;
}