Поиск цепочки возрастания, вариант на волновых алгоритмах

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Program
{
    struct Point
    {
        public Point(int x, int y)
        {
            this.X = x;
            this.Y = y;
        }
        public readonly int X,Y;

        public int GetValue(int[,] arr)
        {
            return arr[X, Y];
        }
    }

    public static void Main(String[] args)
    {
        //arr = new int[,] {{2,5,1,0}, {3,3,1,9}, {4,4,7,8}};

        int size1 = 4000, size2 = 4000;
        arr = new int[size1,size2];

        Random random = new Random();
        for (int x = 0; x < size1; x++)
            for (int y = 0; y < size2; y++)
                arr[x, y] = random.Next();

        var timer = new Stopwatch();
        timer.Start();

        map = InitializeMap();

        var path = new List<Point>();
        BacktracePath(path, longestPathEnd.X, longestPathEnd.Y);
        path.Reverse();

        timer.Stop();

        Console.WriteLine("Длина пути: {0}", path.Count);
        Console.WriteLine("Память: {0} MiB", Process.GetCurrentProcess().WorkingSet64 / (1024 * 1024));
        Console.WriteLine("Временя: {0} ms", timer.ElapsedMilliseconds);

        //path.ForEach(x => Console.WriteLine(arr[x.X, x.Y]));
    }

    private static int[,] arr, map;
    private static Point longestPathEnd;

    private static int[,] InitializeMap()
    {
        map = new int[arr.GetLength(0),arr.GetLength(1)];
        for (int x = 0; x < map.GetLength(0); x++)
            for (int y = 0; y < map.GetLength(1); y++)
                map[x, y] = -1;

        for (int x = 0; x < map.GetLength(0); x++)
            for (int y = 0; y < map.GetLength(1); y++)
                WaveExpansion(x, y);

        return map;
    }

    private static void WaveExpansion(int x, int y, int range = 0)
    {
        if (map[x, y] < range)
        {
            map[x, y] = range;

            if (range > longestPathEnd.GetValue(map))
                longestPathEnd = new Point(x, y);

            int thisCellValue = arr[x, y];

            if (x > 0)
            if (arr[x - 1, y] > thisCellValue)
                WaveExpansion(x - 1, y, range + 1);


            if (x < map.GetLength(0) - 1)
            if (arr[x + 1, y] > thisCellValue)
                WaveExpansion(x + 1, y, range + 1);


            if (y > 0)
            if (arr[x, y - 1] > thisCellValue)
                WaveExpansion(x, y - 1, range + 1);

            if (y < map.GetLength(1) - 1)
            if (arr[x, y + 1] > thisCellValue)
                WaveExpansion(x, y + 1, range + 1);
        }
    }

    private static void BacktracePath(List<Point> path, int x, int y)
    {
        path.Add(new Point(x, y));
        int soughtCellValue = map[x, y] - 1;

        if (x > 0)
        if (map[x - 1, y] == soughtCellValue)
            BacktracePath(path, x - 1, y);


        if (x < map.GetLength(0) - 1)
        if (map[x + 1, y] == soughtCellValue)
            BacktracePath(path, x + 1, y);


        if (y > 0)
        if (map[x, y - 1] == soughtCellValue)
            BacktracePath(path, x, y - 1);

        if (y < map.GetLength(1) - 1)
        if (map[x, y + 1] == soughtCellValue)
            BacktracePath(path, x, y + 1);
    }
}