public class Solution
{
bool[,] tags;//用于标记是否已经访问过，false未访问，true已访问
int[,] records;//用于标记以当前为起点的最长升序列长度(上下左右四向最长的) private int MaxOfFour(int a, int b, int c, int d)
{
return Math.Max(Math.Max(a, b), Math.Max(c, d));
} private int GetLongestFromPoint(int[,] matrix, int i, int j, int prenum)
{
var row = matrix.GetLength();
var column = matrix.GetLength(); if (i < || i >= row || j < || j >= column)
{
//坐标不合法
return ;
} var curnum = matrix[i, j];//当前坐标
if (prenum >= curnum)
{
return ;
}
else
{
if (tags[i, j])//当前节点已经访问，直接返回结果
{
return records[i, j];
} //当前节点尚未访问过
tags[i, j] = true;//当前节点未访问,将当前节点标记为已经访问 //向上
var maxup = ;
var up_i = i - ;
var up_j = j;
if (up_i >= )
{
maxup = GetLongestFromPoint(matrix, up_i, up_j, curnum);
} //向下
var maxdown = ;
var down_i = i + ;
var down_j = j;
if (down_i < row)
{
maxdown = GetLongestFromPoint(matrix, down_i, down_j, curnum);
} //向左
var maxleft = ;
var left_i = i;
var left_j = j - ;
if (left_j >= )
{
maxleft = GetLongestFromPoint(matrix, left_i, left_j, curnum);
} //向右
var maxright = ;
var right_i = i;
var right_j = j + ;
if (right_j < column)
{
maxright = GetLongestFromPoint(matrix, right_i, right_j, curnum);
} var max = + MaxOfFour(maxup, maxdown, maxleft, maxright);
records[i, j] = max;//标记当前节点的最大升序列长度
return max;
}
} public int LongestIncreasingPath(int[,] matrix)
{
var row = matrix.GetLength();
var column = matrix.GetLength();
if (row == && column == )
{
return ;
}
tags = new bool[row, column];
records = new int[row, column];
for (int i = ; i < row; i++)
{
for (int j = ; j < column; j++)
{
tags[i, j] = false;
records[i, j] = ;
}
}
int maxlen = ;//用于记录全局最长升序列长度 for (int i = ; i < row; i++)
{
for (int j = ; j < column; j++)
{
if (!tags[i, j])//当前节点还没有计算过
{
GetLongestFromPoint(matrix, i, j, matrix[i, j] - );
}
maxlen = Math.Max(maxlen, records[i, j]);//更新全局最大升序列长度
}
} return maxlen;
}
}