leetcode 329. Longest Increasing Path in a Matrix

我不是女神ヾ 2022-08-21 01:28 13阅读 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:

nums = [
      [9,9,4],
      [6,6,8],
      [2,1,1]
    ]

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

Example 2:

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

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

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

class Solution {
    	bool notlessthan_around(int y, int x, vector<vector<int>>&matrix)
    	{
    		if (y - 1 >= 0 && matrix[y - 1][x] > matrix[y][x])
    			return false;
    		if (x - 1 >= 0 && matrix[y][x - 1] > matrix[y][x])
    			return false;
    		if (y + 1 < matrix.size() && matrix[y + 1][x] > matrix[y][x])
    			return false;
    		if (x + 1 < matrix[0].size() && matrix[y][x + 1] > matrix[y][x])
    			return false;
    		return true;
    	}
    public:
    	int longestIncreasingPath(vector<vector<int>>& matrix) {
    		if (matrix.empty())
    			return 0;
    		if (matrix[0].empty())
    			return 0;
    		int maxlen = 0;
    		int col(matrix[0].size()), row(matrix.size());
    		vector<int>starter(col*row);
    		for (int i = 0; i < matrix.size(); i++)
    		{
    			for (int j = 0; j < matrix[0].size(); j++)
    			{
    				if (starter[i*col+j]==0&¬lessthan_around(i, j, matrix))
    				{
    					vector<vector<pair<int, int>>>canque;//pair<int,int>(y,x)
    					vector<pair<int, int>>que;
    					que.push_back(pair<int, int>(i, j));
    					while (true)
    					{
    						vector<pair<int, int>>tempque;
    						starter[que.back().first*col + que.back().second] = 1;
    						if (que.size()>maxlen)
    							maxlen = que.size();
    						if (que.back().first - 1 >= 0 && find(que.begin(), que.end(), pair<int, int>(que.back().first - 1, que.back().second)) == que.end() &&
    							matrix[que.back().first][que.back().second] > matrix[que.back().first - 1][que.back().second])
    							tempque.push_back(pair<int, int>(que.back().first - 1, que.back().second));
    						if (que.back().first + 1 < row && find(que.begin(), que.end(), pair<int, int>(que.back().first + 1, que.back().second)) == que.end() &&
    							matrix[que.back().first][que.back().second] > matrix[que.back().first + 1][que.back().second])
    							tempque.push_back(pair<int, int>(que.back().first + 1, que.back().second));
    						if (que.back().second - 1 >= 0 && find(que.begin(), que.end(), pair<int, int>(que.back().first, que.back().second - 1)) == que.end() &&
    							matrix[que.back().first][que.back().second] > matrix[que.back().first][que.back().second - 1])
    							tempque.push_back(pair<int, int>(que.back().first, que.back().second - 1));
    						if (que.back().second + 1 < col && find(que.begin(), que.end(), pair<int, int>(que.back().first, que.back().second + 1)) == que.end() &&
    							matrix[que.back().first][que.back().second] > matrix[que.back().first][que.back().second + 1])
    							tempque.push_back(pair<int, int>(que.back().first, que.back().second + 1));
    						if (tempque.empty())
    						{
    							que.pop_back();
    							while (!canque.empty()&&canque.back().empty())
    							{
    								canque.pop_back();
    								que.pop_back();
    							}
    							if (canque.empty())
    								break;
    							que.push_back(canque.back().back());
    							canque.back().pop_back();
    						}
    						else
    						{
    							que.push_back(tempque.back());
    							tempque.pop_back();
    							canque.push_back(tempque);
    						}
    					}
    				}
    			}
    		}
    		return maxlen;
    	}
    };