solution.cs

using System.Diagnostics;

var sw = Stopwatch.StartNew();
int s = FindSmallestMaxPathUDLR64(new[]
{
    new []{ 1, 1, 1, 1, 1, 1, 1 },
    new []{ 9, 9, 9, 9, 9, 9, 1 },
    new []{ 9, 1, 1, 1, 1, 9, 1 },
    new []{ 9, 1, 9, 9, 1, 1, 1 },
    new []{ 9, 1, 9, 9, 9, 9, 9 },
    new []{ 9, 1, 1, 1, 1, 7, 1 },
    new []{ 9, 7, 7, 7, 1, 8, 1 },
});
// big O is very slow for a large grid.
// 5x7 grid has ~ 38  million calls
// 6x7 grid has ~ 1.2 billion calls
// 7x7 grid has ~ 41  billion calls
// adding 7 elements increases the calls by roughly 33.
Console.WriteLine(s);
Console.WriteLine(sw.Elapsed);
Console.Read();

static int FindSmallestMaxPathUDLR64(int[][] grid)
{
    // provided you have less than 64 positions in your grid, encode in a ulong
    // where position of tile (i, k) in an N x M grid is i * M + k.
    if(grid.Length == 0 || grid[0].Length == 0)
    {
        return int.MinValue;
    }
    int max = grid[0][0];
    return Math.Min(
            Helper(grid, 1, 0, max, visited: 1),
            Helper(grid, 0, 1, max, visited: 1));

    static int Helper(int[][] grid, int r, int c, int max, ulong visited)
    {
        int bit = r * grid[0].Length + c;
        ulong mask = 1ul << bit;

        if ((visited & mask) == mask
            || (uint)r >= (uint)grid.Length
            || (uint)c >= (uint)grid[r].Length)
        {
            return int.MaxValue;
        }
        visited |= mask;
        max = Math.Max(max, grid[r][c]);
        if (r == grid.Length - 1 && c == grid[r].Length - 1)
        {
            return max;
        }
        int right = Helper(grid, r, c + 1, max, visited);
        int left = Helper(grid, r, c - 1, max, visited);
        int down = Helper(grid, r + 1, c, max, visited);
        int up = Helper(grid, r - 1, c, max, visited);
        return Math.Min(Math.Min(Math.Min(right, left), down), up);
    }
}