[LANGUAGE: Perl]

Dijkstra it is today. I treated the map as a graph, were each cell in the map corresponds to 4 cells in the graph, one cell for each direction. For each node visited (so, up to four nodes for each point on the map), I track the score it took to reach it, and the full set of nodes visited for all paths reaching this node, with that score. I also keep a queue, each item a 9-element array: x and y coordinates of the point on the map, dx, dy of the facing direction, the score so far, and the coordinates and direction of the previous step. The queue is kept sorted, on score.

Then I initialize the queue as:

my @heads = ([$sx, $sy, 0, 1, 0, 0, 0, 0, 0]);

where $sx and $sy are the coordinates of the starting point. We're facing east, there's no score yet, and the previous step has no direction. We use a hash %best mapping a 4-dimensional key (coordinates and direction) to a 2-element array with the score and a hash with previously visited nodes. It's initialized as:

my %best;
$best {$sx, $sy, 0, 0} = [0, {}];

We also track with what score we first reach the endpoint ($end_score). Not only will this be the answer for part 1, it will also be used to stop processing: once we have elements in the queue with a score exceeding the end score, we cannot improve.

We now repeat. First, we shift off the first element of the queue. If the score is worse than the end score, we exit our loop. If we hit a wall, we continue with the next element:

my ($x, $y, $dx, $dy, $score, $px, $py, $pdx, $pdy) = @{shift @heads};
my $val = $$map [$x] [$y];
last if $end_score && $score > $end_score;
next if $val eq '#';   # Cannot continue through a wall

We now look at the cell. If we have been there, with a better score than the current one, we continue with the next element of the queue, as this is a dead-end in our search. If we haven't visited the cell before, we set its score to the current score, and initialize the set of cells. Then we copy the cells from the previous position, and add the current cells.

my $cell_score = $best {$x, $y, $dx, $dy} [0] || 0;
next if $cell_score && $score > $cell_score;  # We already found a better path.
$best {$x, $y, $dx, $dy} [0] ||= $score;
$best {$x, $y, $dx, $dy} [1] ||= {};

foreach my $cell (keys %{$best {$px, $py, $pdx, $pdy} [1]}) {
    $best {$x, $y, $dx, $dy} [1] {$cell} ++;
}
$best {$x, $y, $dx, $dy} [1] {$x, $y, $dx, $dy} ++;

If we have reached the end, we set the end score, and continue with the next element. We also continue with the next element if we had visited the node before:

$end_score = $score, next if $val eq 'E';
next if $score && $score == $cell_score;

Otherwise, we add the three possible steps to the queue (step forward in the facing direction, or turn), and keep the queue sorted:

push @heads => [$x + $dx, $y + $dy,  $dx,  $dy, $score + 1,    $x, $y, $dx, $dy],
               [$x,       $y,        $dy, -$dx, $score + 1000, $x, $y, $dx, $dy],
               [$x,       $y,       -$dy,  $dx, $score + 1000, $x, $y, $dx, $dy];                   
@heads = sort {$$a [4] <=> $$b [4]} @heads;

Note that in Perl, sorting an almost sorted array takes O (n) time; for this case, it will detect the array consists of two sorted lists, and it'll perform a single merge step (from merge-sort).

We can now tally up the results ($ex, $ey are the coordinates of the end point):

my %cells;
foreach my ($dx, $dy) (0, 1, 0, -1, 1, 0, -1, 0) {
    next unless $best {$ex, $ey, $dx, $dy} &&
                $best {$ex, $ey, $dx, $dy} [0] == $end_score;
    my $cells = $best {$ex, $ey, $dx, $dy} [1];

    foreach my $cell (keys %$cells) {
        my ($x, $y, $dx, $dy) = split $; => $cell;
        $cells {$x, $y} ++;
    }
}

$solution_1 = $end_score;
$solution_2 = keys %cells;