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

/// <summary>
/// Пара индексов для двумерного Int32 массива.
/// </summary>
public struct XY
{
	public XY(int x, int y)
	{
		this.x = x;
		this.y = y;
	}

	public int x, y;

	public int GetValue(int[,] arr)
	{
		return arr[x, y];
	}

	public override string ToString()
	{
		return x.ToString() + ", " + y.ToString();
	}
}

public class Program
{
	public static void Main(String[] args)
	{
		int size1 = 4000, size2 = 4000;
		int[,] 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();
		Console.WriteLine("Длина пути: " + GetLongestPathInArray(arr).Count);
		timer.Stop();
		Console.WriteLine("Память: " + (Process.GetCurrentProcess().WorkingSet64 / (1024 * 1024)).ToString() + " MB");
		Console.WriteLine("Временя: " + timer.ElapsedMilliseconds);

		//GetLongestPathInArray(arr).ForEach(x => Console.WriteLine(x.GetValue(arr)));
	}

	/// <summary>
	/// Возвращает список элементов, обарзующих наиболее длинную цепочку возрастания в данном массиве.
	/// </summary>
	public static List<XY> GetLongestPathInArray(int[,] arr)
	{
		List<XY> longestPath = new List<XY>();
		List<XY>[,] foundWays = new List<XY>[arr.GetLength(0),arr.GetLength(1)]; //Инициализируем вспомогательный массив уже найденных цепочек

		for (int x = 0; x < arr.GetLength(0); x++)
			for (int y = 0; y < arr.GetLength(1);y++)
			{
				List<XY> path = GetLongestPathFrom(arr, new XY(x, y), foundWays);

				if (path.Count > longestPath.Count)
					longestPath = path;
			}

		return longestPath;
	}

	/// <summary>
	/// Возвращает цепочку возрастания наибольшей длины от указанного элемента, включая его самого.
	/// </summary>
	private static List<XY> GetLongestPathFrom(int[,] arr, XY pos, List<XY>[,] foundWays)
	{
		if (foundWays[pos.x, pos.y] == null) //Если мы еще не искали цепочку для этого элемента
		{
			List<XY> neighbours = GetNeighbours(arr, pos).FindAll(n => n.GetValue(arr) > pos.GetValue(arr)); //Получаем возможные направления поиска
			List<XY> longestPath = new List<XY>();

			foreach (XY neighbour in neighbours)
			{
				List<XY> tmpPath = GetLongestPathFrom(arr, neighbour, foundWays); //Ищем наиболее "перспективного" соседа

				if (tmpPath.Count > longestPath.Count)
					longestPath = tmpPath;
			}

			longestPath = new List<XY>(longestPath); //Необходимо клонировать, т.к. иначе будет изменяться сохраненный путь у соседа.
			longestPath.Insert(0, pos); //Добавляем себя к пути соседа и сохраняем
			foundWays[pos.x, pos.y] = longestPath;
			return longestPath;
		}
		else
			return foundWays[pos.x, pos.y];
		//Такое "кэширование" позволяет ускорить алгоритм в несколько раз, избегая повторных рассчетов одинаковых цепочек.
	}

	/// <summary>
	/// Возвращает всех соседей указанного элемента (от 2 до 4, в зависимости от индексов).
	/// </summary>
	private static List<XY> GetNeighbours(int[,] arr, XY indexes)
	{
		List<XY> result = new List<XY>(2);

		if (indexes.x > 0)
			result.Add(new XY(indexes.x - 1, indexes.y));
		if (indexes.x < arr.GetLength(0) - 1)
			result.Add(new XY(indexes.x + 1, indexes.y));

		if (indexes.y > 0)
			result.Add(new XY(indexes.x, indexes.y - 1));
		if (indexes.y < arr.GetLength(1) - 1)
			result.Add(new XY(indexes.x, indexes.y + 1));

		return result;
	}
}