leetcode329

  1 public class Solution
  2     {
  3         bool[,] tags;//用于标记是否已经访问过，false未访问，true已访问
  4         int[,] records;//用于标记以当前为起点的最长升序列长度(上下左右四向最长的)
  5 
  6         private int MaxOfFour(int a, int b, int c, int d)
  7         {
  8             return Math.Max(Math.Max(a, b), Math.Max(c, d));
  9         }
 10 
 11         private int GetLongestFromPoint(int[,] matrix, int i, int j, int prenum)
 12         {
 13             var row = matrix.GetLength(0);
 14             var column = matrix.GetLength(1);
 15 
 16             if (i < 0 || i >= row || j < 0 || j >= column)
 17             {
 18                 //坐标不合法
 19                 return 0;
 20             }
 21 
 22             var curnum = matrix[i, j];//当前坐标
 23             if (prenum >= curnum)
 24             {
 25                 return 0;
 26             }
 27             else
 28             {
 29                 if (tags[i, j])//当前节点已经访问，直接返回结果
 30                 {
 31                     return records[i, j];
 32                 }
 33 
 34                 //当前节点尚未访问过
 35                 tags[i, j] = true;//当前节点未访问,将当前节点标记为已经访问
 36 
 37                 //向上
 38                 var maxup = 0;
 39                 var up_i = i - 1;
 40                 var up_j = j;
 41                 if (up_i >= 0)
 42                 {
 43                     maxup = GetLongestFromPoint(matrix, up_i, up_j, curnum);
 44                 }
 45 
 46                 //向下
 47                 var maxdown = 0;
 48                 var down_i = i + 1;
 49                 var down_j = j;
 50                 if (down_i < row)
 51                 {
 52                     maxdown = GetLongestFromPoint(matrix, down_i, down_j, curnum);
 53                 }
 54 
 55 
 56                 //向左
 57                 var maxleft = 0;
 58                 var left_i = i;
 59                 var left_j = j - 1;
 60                 if (left_j >= 0)
 61                 {
 62                     maxleft = GetLongestFromPoint(matrix, left_i, left_j, curnum);
 63                 }
 64 
 65 
 66                 //向右
 67                 var maxright = 0;
 68                 var right_i = i;
 69                 var right_j = j + 1;
 70                 if (right_j < column)
 71                 {
 72                     maxright = GetLongestFromPoint(matrix, right_i, right_j, curnum);
 73                 }
 74 
 75                 var max = 1 + MaxOfFour(maxup, maxdown, maxleft, maxright);
 76                 records[i, j] = max;//标记当前节点的最大升序列长度
 77                 return max;
 78             }
 79         }
 80 
 81         public int LongestIncreasingPath(int[,] matrix)
 82         {
 83             var row = matrix.GetLength(0);
 84             var column = matrix.GetLength(1);
 85             if (row == 0 && column == 0)
 86             {
 87                 return 0;
 88             }
 89             tags = new bool[row, column];
 90             records = new int[row, column];
 91             for (int i = 0; i < row; i++)
 92             {
 93                 for (int j = 0; j < column; j++)
 94                 {
 95                     tags[i, j] = false;
 96                     records[i, j] = 1;
 97                 }
 98             }
 99             int maxlen = 1;//用于记录全局最长升序列长度
100 
101             for (int i = 0; i < row; i++)
102             {
103                 for (int j = 0; j < column; j++)
104                 {
105                     if (!tags[i, j])//当前节点还没有计算过
106                     {
107                         GetLongestFromPoint(matrix, i, j, matrix[i, j] - 1);
108                     }
109                     maxlen = Math.Max(maxlen, records[i, j]);//更新全局最大升序列长度
110                 }
111             }
112 
113             return maxlen;
114         }
115     }