Anonymous

#!/usr/local/bin/perl
use strict;

my $g_display=1; # true:ON false:OFF

my @g_ins=grep $_,split /\n/,join "",<DATA>; # input
my @g_outs=(); # output
my @g_min_length=(9999999) x 10000; # buffer 100x100

main();
exit 0;

sub main
{
	check(search_start_x_y('x'),search_start_x_y('y'),0);
	
	print join "\n","\n","result",@g_outs,"\n";
	<STDIN>; # pause
}

sub check
{
	my($x,$y,$len)=@_;
	
	return if $len>=$g_min_length[$x+$y*100];
	
	$g_min_length[$x+$y*100]=$len;
	my $under=substr $g_ins[$y],$x,1;
	
	if($under eq 'G')
	{
		@g_outs=@g_ins;
		return;
	}
	return if $under eq '*';
	return if $under eq '$';
	return if $under eq 'S' && $len;
	
	replace_str($x,$y,' ','$');
	
	if($g_display)
	{
		print join "\n",@g_ins,"\n";
		print "\n";
		select undef,undef,undef,0.01; # wait display
	}
	
	check($x+1,$y,$len+1);
	check($x-1,$y,$len+1);
	check($x,$y+1,$len+1);
	check($x,$y-1,$len+1);
	
	replace_str($x,$y,'',' ');
	return;
}

sub replace_str
{
	my($x,$y,$from,$to)=@_;
	
	if($from eq '' || substr($g_ins[$y],$x,1) eq $from)
	{
		return $g_ins[$y]=substr($g_ins[$y],0,$x).$to.substr($g_ins[$y],$x+1);
	}
	return $g_ins[$y];
}

sub search_start_x_y
{
	my($type)=@_;
	
	my $y=0;
	foreach my $in (@g_ins)
	{
		my $pos=index($in,"S");
		return $pos if $pos>=0 && $type eq 'x';
		return $y if $pos>=0 && $type eq 'y';
		$y++;
	}
	return 0;
}

__DATA__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************