Downhill Maze Solver A downhill maze is given as a series of rows of space separated digits from 0 to 9 inclusive, plus one "S" and one "X", where the S denotes the start and the X denotes the finish.  In a downhill maze, you may only go to a space that is adjacent to you to the north, south, east, or west (no diagonals), and you may only go to spaces with a value less than or equal to the value you are currently on.

The program should output a path to navigate through the maze in the same format as the input, only all traversed spaces should have a "." in them, and all unvisited spaces should have a "#" in them.  The starting and ending cells should also keep their "S" and "X", respectively.  You can assume there is always a solution to the maze.

Example input:

3 3 3 3 2 1 S 8 9
3 1 1 3 3 0 6 8 7
1 2 2 4 3 2 5 9 7
1 2 1 5 4 3 4 4 6
1 1 X 6 4 4 5 5 5


Example output:

. . . . # # S . #
. # # . . # # . .
. # # # . # # # .
. # # # . # # # .
. . X # . . . . .
C# - 463

Accepts input via STDIN, and should produce an optimal path, tested for the given test case, but not otherwise. Assumes there is always a solution.

I'm in a bit of a hurry, I have a deadline in 7 hours, but this just looked like too much fun to miss out on. I'm also out of practice. It could be very embarrassing if this goes wrong, but it's reasonably golfed.



using C=System.Console;class P{static void Main(){var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+');int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L;var K=new int[L];for(K[s]=s+2;j--&gt;0;)for(i=0;i&lt;L;i+=2){System.Action&lt;int&gt;M=z=&gt;{if((z+=i)&gt;=0&amp;z&lt;L&amp;&amp;S[z]&lt;=S[i]&amp;K[z]&lt;1&amp;K[i]&gt;0&amp;(i%w==z%w|i/w==z/w))K[z]=i+1;};M(2);M(-2);M(w);M(-w);}for(w=e;w!=s+1;w=i){i=K[w]-1;K[w]=-1;}for(;++j&lt;L;)C.Write(j%2&lt;1?K[j]&lt;0?j==s?'S':j==e?'X':'.':'#':S[j]);}}


Code with comments:

using C=System.Console;

class P
{
    static void Main()
    {
        var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+'); // read in the map, replace X with + because + &lt; 0
        int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L; // find start, end, width, length

        var K=new int[L]; // this stores how we got to each point as loc+1 (0 means we havn't visited it)

        for(K[s]=s+2; // can't risk this being 0
            j--&gt;0;) // do L passes
            for(i=0;i&lt;L;i+=2) // each pass, look at every location
            {
                // if a whole load of bouds checks, point new location (i+z) at i
                System.Action&lt;int&gt;M=z=&gt;{if((z+=i)&gt;=0&amp;z&lt;L&amp;&amp;S[z]&lt;=S[i]&amp;K[z]&lt;1&amp;K[i]&gt;0&amp;(i%w==z%w|i/w==z/w))K[z]=i+1;};
                // try and move in each direction
                M(2);
                M(-2);
                M(w);
                M(-w);
            }

        for(w=e;w!=s+1;w=i) // find route back
        {
            i=K[w]-1; // previous location
            K[w]=-1; // set this so we know we've visited it
        }

        for(;++j&lt;L;) // print out result
            C.Write(j%2&lt;1?K[j]&lt;0?j==s?'S':j==e?'X':'.':'#':S[j]); // if K &lt; 0, we visit it, otherwise we don't
    }
}