via http://twitter.com/koizuka/status/7629753830

nenryo2.pl

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

my @text = map {+[grep {!/\n/} split //, $_]} grep /\*/, <DATA>;
my %points;

for my $y (0..$#text) {
    for my $x (0..$#{$text[$y]}) {
	my $char = $text[$y][$x];
	if ($char ne ' ' && $char ne '*') {
	    $points{$char} = {x => $x, y => $y};
	}
    }
}

my $map2 = travarsal(\@text);
my $route = draw(@$map2, $points{'G'});
for my $c (@$route) {
    $text[$c->{y}][$c->{x}] = '$';
}
print join "\n", map {join "", @$_} @text;
print "\n";

sub travarsal {
    my $map = shift;
    while (1) {
	my @curmap;
	for my $y (0..$#{$map}) {
	    $curmap[$y] = [];
	    for my $x (0..$#{$map->[$y]}) {
		my $s = $map->[$y][$x];
		if ($s eq ' ') {
		    my @cands = sort {$a cmp $b} (grep {defined $_ && /^(?:\d+|S)$/} (
			$map->[$y-1][$x],
			$map->[$y+1][$x],
			$map->[$y][$x-1],
			$map->[$y][$x+1],
		    ));
		    if (@cands) {
			$curmap[$y][$x] = ($cands[0] eq 'S') ? 1 : $cands[0] + 1;
		    }
		    else {
			$curmap[$y][$x] = ' ';
		    }
		}
		elsif ($s eq 'G') {
		    if (my @lastnum = grep {defined $_ && /^(\d+)$/} (
			$map->[$y-1][$x],
			$map->[$y+1][$x],
			$map->[$y][$x-1],
			$map->[$y][$x+1],
		    )) {
			return [$lastnum[0], $map];
		    }
		    $curmap[$y][$x] = $s;
		}
		else {
		    $curmap[$y][$x] = $s;
		}
	    }
	}
	$map = \@curmap;
    }
}

sub draw {
    my $next = shift;
    my $map = shift;
    my $p = shift;
    my @route;
    while ($next) {
	push @route, $p;
	for my $d ([0, -1],[-1, 0],[0, 1],[1, 0]) {
	    my $c = $map->[$p->{y}+$d->[1]][$p->{x}+$d->[0]]; 
	    if (defined $c && $c =~ /^\d+$/ && $c == $next) {
		$next = $c - 1;
		$p = {x => $p->{x}+$d->[0], y => $p->{y}+$d->[1]};
		last;
	    }
	}
	
    }
    
    return \@route;
}

__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************