题解 | #矩阵最长递增路径#

class Solution {
	int drow[4] = { -1, 0, 1, 0 };//上右下左
	int dcol[4] = { 0, 1, 0, -1 };//上右下左
public:
	int solve(vector<vector<int> >& matrix) {
		// write code here
		int rows = matrix.size();
		int cols = matrix[0].size();
		if (rows == 0 || cols == 0)
			return 0;

		vector<vector<int> > outdegrees(rows, vector<int>(cols, 0));//标记每个cell的入度
		for (int i = 0; i < rows; ++i)
		{
			for (int j = 0; j < cols; ++j)
			{
				for (int k = 0; k < 4; ++k)
				{
					int curRow = i + drow[k];
					int curCol = j + dcol[k];
					if (curRow >= 0 && curRow < rows&&curCol >= 0 && curCol < cols&&matrix[i][j] < matrix[curRow][curCol])
					{
						++outdegrees[curRow][curCol];//入度++
					}
				}
			}
		}

		queue<pair<int, int> > q;//队列存数组下标
		for (int i = 0; i < rows; ++i)
		{
			for (int j = 0; j < cols; ++j)
			{
				if (outdegrees[i][j] == 0)
					q.push({ i, j });//入度为0的加入队列
			}
		}

		int ans=0;
		while (!q.empty())
		{
			++ans;//广度遍历，最长有向无环路径即结果
			int size = q.size();
			for (int i = 0; i < size; ++i)
			{
				auto cell = q.front();
				q.pop();
				int cellRow = cell.first, cellCol = cell.second;
				for (int k = 0; k < 4; ++k)
				{
					int curRow = cellRow + drow[k];
					int curCol = cellCol + dcol[k];
					if (curRow >= 0 && curRow < rows&&curCol >= 0 && curCol < cols&&matrix[cellRow][cellCol] < matrix[curRow][curCol])
					{
						--outdegrees[curRow][curCol];//出度++
						if (outdegrees[curRow][curCol] == 0)//判断是否入读为0
							q.push({ curRow, curCol });
					}
				}

			}
		}

		return ans;
	}
};