leetcode329 矩阵中的最长递增路径

思路：

拓扑排序或者记忆化搜索。

实现1：

 1 class Solution
 2 {
 3 public:
 4     const vector<int> dx{0, 1, 0, -1};
 5     const vector<int> dy{1, 0, -1, 0};
 6     int longestIncreasingPath(vector<vector<int>>& matrix)
 7     {
 8         queue<pair<int, int>> q;
 9         if (matrix.empty()) return 0;
10         int n = matrix.size(), m = matrix[0].size();
11         vector<int> d(n * m, 0), dis(n * m, 1);
12         for (int i = 0; i < n; i++)
13         {
14             for (int j = 0; j < m; j++)
15             {
16                 bool flg = true;
17                 for (int k = 0; k < 4; k++)
18                 {
19                     int nx = i + dx[k], ny = j + dy[k];
20                     if (nx >= 0 and nx < n and ny >= 0 and ny < m)
21                     {
22                         if (matrix[nx][ny] < matrix[i][j]) flg = false;
23                         else if (matrix[nx][ny] > matrix[i][j])
24                         {
25                             int tmp = nx * m + ny;
26                             d[tmp]++;
27                         }
28                     }
29                 }
30                 if (flg) q.push(make_pair(i, j));
31             }
32         }
33         while (!q.empty())
34         {
35             auto tmp = q.front(); q.pop();
36             int x = tmp.first, y = tmp.second;
37             for (int i = 0; i < 4; i++)
38             {
39                 int nx = x + dx[i], ny = y + dy[i]; 
40                 if (nx >= 0 and nx < n and ny >= 0 and ny < m and matrix[nx][ny] > matrix[x][y])
41                 {
42                     d[nx * m + ny]--;
43                     if (d[nx * m + ny] == 0)
44                     {
45                         q.push(make_pair(nx, ny)); dis[nx * m + ny] = dis[x * m + y] + 1;
46                     }
47                 }
48             }
49         }
50         return *max_element(dis.begin(), dis.end());
51     }
52 };

实现2：

 1 class Solution
 2 {
 3 public:
 4     const vector<int> dx{0, 1, 0, -1};
 5     const vector<int> dy{1, 0, -1, 0};
 6     int dfs(int x, int y, vector<vector<int>>& a, vector<vector<int>>& dp, vector<vector<bool>>& vis)
 7     {
 8         if (dp[x][y] != -1) return dp[x][y];
 9         int n = a.size(), m = a[0].size(), maxn = 0;
10         for (int i = 0; i < 4; i++)
11         {
12             int nx = x + dx[i], ny = y + dy[i];
13             if (nx >= 0 and nx < n and ny >= 0 and ny < m and a[nx][ny] < a[x][y] and !vis[nx][ny])
14             {
15                 vis[nx][ny] = true;
16                 maxn = max(maxn, dfs(nx, ny, a, dp, vis));
17                 vis[nx][ny] = false;
18             }
19         }
20         return dp[x][y] = maxn + 1;
21     }
22     int longestIncreasingPath(vector<vector<int>>& matrix)
23     {
24         if (matrix.empty()) return 0;
25         int n = matrix.size(), m = matrix[0].size();
26         int res = 1;
27         vector<vector<int>> dp(n, vector<int>(m, -1));
28         vector<vector<bool>> vis(n, vector<bool>(m, false));
29         for (int i = 0; i < n; i++)
30         {
31             for (int j = 0; j < m; j++)
32             {
33                 vis[i][j] = true;
34                 res = max(res, dfs(i, j, matrix, dp, vis));
35                 vis[i][j] = false;
36             }
37         }
38         return res;
39     }
40 };