解いた

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
解いた。かかった時間は一時間ぐらい(実際問題を見つけてから1日以上経ってるけど)。

参考にされたようなので簡単な解説。
　最短経路探索アルゴリズムとして，アルゴリズムの教科書とかによくのってるダイクストラ法を使ってる。(*Queueを書くのが面倒だったのでダイクストラ法で深さ優先探索とかキモいことになってるけど，動くので気にしない。)未探索の頂点への距離は一般的に無限大だが，-1で代用。cost関数でスタートから全体への距離を求めて，route関数でゴールからスタートへの経路をマップに書いてる。

以下殴り書きなソース。

#include<stdio.h>
#include<string.h>

#define MAX_SIZE 256
char m[MAX_SIZE][MAX_SIZE];
int d[MAX_SIZE][MAX_SIZE];

void cost(int x, int y)
{
	if(m[x-1][y] != '*' && (d[x-1][y] == -1 || d[x-1][y] > d[x][y] + 1))
	{
		d[x-1][y] = d[x][y] + 1;
		cost(x-1, y);
	}
	if(m[x][y-1] != '*' && (d[x][y-1] == -1 || d[x][y-1] > d[x][y] + 1))
	{
		d[x][y-1] = d[x][y] + 1;
		cost(x, y-1);
	}
	if(m[x+1][y] != '*' && (d[x+1][y] == -1 || d[x+1][y] > d[x][y] + 1))
	{
		d[x+1][y] = d[x][y] + 1;
		cost(x+1, y);
	}
	if(m[x][y+1] != '*' && (d[x][y+1] == -1 || d[x][y+1] > d[x][y] + 1))
	{
		d[x][y+1] = d[x][y] + 1;
		cost(x, y+1);
	}
}

void route(int x, int y)
{
	int n = d[x][y] - 1;
	if(m[x][y] == ' ')
		m[x][y] = '$';
	if(m[x][y] == 'S')
		return;
	
	if(d[x-1][y] == n)
	{
		route(x-1, y);
		return;
	}
	if(d[x][y-1] == n)
	{
		route(x, y-1);
		return;
	}
	if(d[x+1][y] == n)
	{
		route(x+1, y);
		return;
	}
	if(d[x][y+1] == n)
	{
		route(x, y+1);
		return;
	}
}

int main(int argc, char **argv)
{
	int sx, sy, i, j;
	FILE *fp;
	fp = fopen(argv[1], "r");
	sx = 0;
	while(fgets(m[sx++], MAX_SIZE, fp) != NULL)
	sy = strlen(m[0]);
	fclose(fp);
	for(i = 0; i < sx; i++)
		for(j = 0; j < sy; j++)
			d[i][j] = -1;
	
	for(i = 0; i < sx; i++)
		for(j = 0; j < sy; j++)
			if(m[i][j] == 'S')
			{
				d[i][j] = 0;
				cost(i, j);
			}
	
	for(i = 0; i < sx; i++)
		for(j = 0; j < sy; j++)
			if(m[i][j] == 'G')
				route(i, j);
	
	
	fp = fopen(argv[2], "w");
	for(i = 0; i < sy; i++)
		fputs(m[i], fp);
	fclose(fp);
	return 0;
}