企业官网建设流程全解析

对于每个单元格，你可以往上、下、左、右四个方向移动。不能沿对角线移动，也不能移动到矩阵边界外。

输入描述

第一行输入两个整数m和n，表示矩阵的行数和列数。

接下来输入m行，每行n个整数。

输出描述

输出最长递增路径的长度。

示例 1

输入

text

3 3 9 9 4 6 6 8 2 1 1

输出

text

4

说明

最长递增路径为1 -> 2 -> 6 -> 9。

C++ 解法

cpp

#include <bits/stdc++.h> using namespace std; int m, n; vector<vector<int>> matrix, memo; int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int dfs(int x, int y) { if (memo[x][y] != -1) return memo[x][y]; int best = 1; for (auto& d : dirs) { int nx = x + d[0]; int ny = y + d[1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) { best = max(best, 1 + dfs(nx, ny)); } } return memo[x][y] = best; } int main() { cin >> m >> n; matrix.assign(m, vector<int>(n)); memo.assign(m, vector<int>(n, -1)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> matrix[i][j]; } } int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { ans = max(ans, dfs(i, j)); } } cout << ans << endl; return 0; }