题目简介：
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
1
2
3
4
5
6
7
8
| 输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
|
示例 2:
1
2
3
4
5
6
7
8
| 输入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
|
思路：
首先将这个矩阵看做有向图，有向边为数字大的元素指向数字小的元素，这样子问题转化成在有向图中寻找最长路径(关键路径)。
然后计算矩阵每个元素的入度，并将入度为0的元素入队(即从最大的元素开始)
从所有入度为 0 的单元格开始广度优先搜索，每一轮搜索都会遍历当前层的所有单元格，更新其余单元格的入度，并将入度变为 0 的单元格加入下一层搜索(即拓扑排序)。当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度。
tips:
- 计算每个元素的入度或者出度都可以。
- 注意边界的控制，防止溢出。
- 可以预先定义一个数组来保存四个方向，即
int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0)
return 0;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int row = matrix.size();
int column = matrix[0].size();
vector<vector<int>> indegree(row, vector<int>(column, 0));
for(int i = 0; i < row; i++){
for(int j = 0; j < column; j++){
for(int k = 0; k < 4; k++){
int newrow = i + directions[k][0];
int newcol = j + directions[k][1];
if(newrow >= 0 && newrow < row && newcol >= 0 && newcol < column && matrix[i][j] > matrix[newrow][newcol])
indegree[i][j]++;
}
}
}
queue<pair<int, int>> qu;
for(int i = 0; i < row; i++){
for(int j = 0; j < column; j++){
if(indegree[i][j] == 0){
qu.push(make_pair(i, j));
}
}
}
int res = 0;
while(!qu.empty()){
res++;
int size = qu.size();
for(int i = 0; i < size; i++){
pair<int, int> node = qu.front();
int node_row = node.first;
int node_col = node.second;
qu.pop();
for(int k = 0; k < 4; k++){
int newrow = node_row + directions[k][0];
int newcol = node_col + directions[k][1];
if(newrow >= 0 && newrow < row && newcol >= 0 && newcol < column && matrix[node_row][node_col] < matrix[newrow][newcol]){
indegree[newrow][newcol]--;
if(indegree[newrow][newcol] == 0)
qu.push(make_pair(newrow, newcol));
}
}
}
}
return res;
}
};
|
