二维数组路径中最大值最小

Question

问题

一个二维数组（样例如下）
6，6（行列）
{0,0,0,0,0,0
1,2,3,4,5,6
2,3,4,5,6,7
3,4,5,6,7,8
1,1,3,6,5,4
0,0,0,0,0,0
}
取一条从左上到右下路径，找出路径元素的最大值，让这个最大值最小。
输出：3（路径：0,1,2,3,1,0,0,0,0,0,0）

我的尝试

#include<bits/stdc++.h>
using namespace std;

int maxest(int a,int b)//取最大值
{
    return a>b?a: b;
}
int minPathSum(vector<vector<int>> &grid)
{
    int row=grid.size(),col=grid[0].size();
    for(int i=1; i<col;++i)
    {
        grid[0][i]=maxest(grid[0][i],grid[0][i - 1]);
    }
    for(int i=1; i<row;++i)
    {
        grid[i][0]=maxest(grid[i][0],grid[i - 1][0]);
    }
    for(int i=1;i<row;++i)
    {
        for(int j=1;j<col;++j)
        {
            grid[i][j]=maxest(min(grid[i - 1][j], grid[i][j - 1]),grid[i][j]);
        }
    }
    return grid[row - 1][col - 1];
}
int input()
{
    int a;
    cin>>a;
    return a;
}
int main()
{
    vector<vector<int>> arr;
    vector<int> a;
    
    int n,m;
    cin>>n>>m;
    int temp=0;
    for (int i=0;i<n;i++)
    {
        a.clear();
        for(int j=0;j<m;j++)
        {
            cin>>temp;
            a.push_back(temp);
        }
        arr.push_back(a);
    }
    int ans=minPathSum(arr);
    cout<<ans<<endl;
    return 0;
}

输入：

4 2
0 0
3 5
2 4
0 0

输出：

3

过程：

0->3->2->0->0

求解

Answer 1

动态规划，从左上角开始往下走，每走一步记录一次