leetcode 329. Longest Increasing Path in a Matrix

我不是女神ヾ 2022-08-21 01:28 120阅读 0赞

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

  1. nums = [
  2. [9,9,4],
  3. [6,6,8],
  4. [2,1,1]
  5. ]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

  1. nums = [
  2. [3,4,5],
  3. [3,2,6],
  4. [2,2,1]
  5. ]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

思路:找到一个不比周围数大的点作为起点,然后dfs得到以改点为起点的最长路径,同时在此次dfs中被访问的点就不可能作为起点了,遍历得到解。结果超时。

  1. class Solution {
  2. bool notlessthan_around(int y, int x, vector<vector<int>>&matrix)
  3. {
  4. if (y - 1 >= 0 && matrix[y - 1][x] > matrix[y][x])
  5. return false;
  6. if (x - 1 >= 0 && matrix[y][x - 1] > matrix[y][x])
  7. return false;
  8. if (y + 1 < matrix.size() && matrix[y + 1][x] > matrix[y][x])
  9. return false;
  10. if (x + 1 < matrix[0].size() && matrix[y][x + 1] > matrix[y][x])
  11. return false;
  12. return true;
  13. }
  14. public:
  15. int longestIncreasingPath(vector<vector<int>>& matrix) {
  16. if (matrix.empty())
  17. return 0;
  18. if (matrix[0].empty())
  19. return 0;
  20. int maxlen = 0;
  21. int col(matrix[0].size()), row(matrix.size());
  22. vector<int>starter(col*row);
  23. for (int i = 0; i < matrix.size(); i++)
  24. {
  25. for (int j = 0; j < matrix[0].size(); j++)
  26. {
  27. if (starter[i*col+j]==0lessthan_around(i, j, matrix))
  28. {
  29. vector<vector<pair<int, int>>>canque;//pair<int,int>(y,x)
  30. vector<pair<int, int>>que;
  31. que.push_back(pair<int, int>(i, j));
  32. while (true)
  33. {
  34. vector<pair<int, int>>tempque;
  35. starter[que.back().first*col + que.back().second] = 1;
  36. if (que.size()>maxlen)
  37. maxlen = que.size();
  38. if (que.back().first - 1 >= 0 && find(que.begin(), que.end(), pair<int, int>(que.back().first - 1, que.back().second)) == que.end() &&
  39. matrix[que.back().first][que.back().second] > matrix[que.back().first - 1][que.back().second])
  40. tempque.push_back(pair<int, int>(que.back().first - 1, que.back().second));
  41. if (que.back().first + 1 < row && find(que.begin(), que.end(), pair<int, int>(que.back().first + 1, que.back().second)) == que.end() &&
  42. matrix[que.back().first][que.back().second] > matrix[que.back().first + 1][que.back().second])
  43. tempque.push_back(pair<int, int>(que.back().first + 1, que.back().second));
  44. if (que.back().second - 1 >= 0 && find(que.begin(), que.end(), pair<int, int>(que.back().first, que.back().second - 1)) == que.end() &&
  45. matrix[que.back().first][que.back().second] > matrix[que.back().first][que.back().second - 1])
  46. tempque.push_back(pair<int, int>(que.back().first, que.back().second - 1));
  47. if (que.back().second + 1 < col && find(que.begin(), que.end(), pair<int, int>(que.back().first, que.back().second + 1)) == que.end() &&
  48. matrix[que.back().first][que.back().second] > matrix[que.back().first][que.back().second + 1])
  49. tempque.push_back(pair<int, int>(que.back().first, que.back().second + 1));
  50. if (tempque.empty())
  51. {
  52. que.pop_back();
  53. while (!canque.empty()&&canque.back().empty())
  54. {
  55. canque.pop_back();
  56. que.pop_back();
  57. }
  58. if (canque.empty())
  59. break;
  60. que.push_back(canque.back().back());
  61. canque.back().pop_back();
  62. }
  63. else
  64. {
  65. que.push_back(tempque.back());
  66. tempque.pop_back();
  67. canque.push_back(tempque);
  68. }
  69. }
  70. }
  71. }
  72. }
  73. return maxlen;
  74. }
  75. };

发表评论

表情:
评论列表 (有 0 条评论,120人围观)

还没有评论,来说两句吧...

相关阅读