奇安信笔试第二题C++版本2021-87

#include <stdio.h>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
//奇安信笔试题第二题
//二维矩阵,找出最大的一条路径和,如:
//0 3 4
//8 5 0
//0 9 0
//最大的路径即是:9->5->8 最大路径和为22
struct Point{
    int x;
    int y;
    Point(int x_,int y_){
        x=x_;
        y=y_;
    }
};
int main_x(vector<vector<int>>& mat);
int dfs(vector<vector<int>>& mat,int i,int j);
int main(int argc, char **argv){
    vector<vector<int>> mat={
        {0,3,4},
        {8,5,0},
        {0,9,0}
    };
    cout<<main_x(mat)<<endl;
}
int main_x(vector<vector<int>>& mat)
{
    int row=mat.size();
    int col=mat[0].size();
    int res=0;
    stack<Point> st;
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            if(mat[i][j]!=0){
                st.push(Point(i,j));
            }
        }
    }
    while(!st.empty()){
        Point p=st.top();
        vector<vector<int>> temp=mat;
        st.pop();
        res=max(res,dfs(temp,p.x,p.y));
    }
    return res;
}
int dfs(vector<vector<int>>& mat,int i,int j){
    int row=mat.size();
    int col=mat[0].size();
    int sum=mat[i][j];
    mat[i][j]=0;
    int up=0,bottom=0,left=0,right=0;
    if(i+1<row&&i+1>=0&&mat[i+1][j]!=0){
        vector<vector<int>> temp=mat;
        up=dfs(temp,i+1,j);
    }
    if(j+1<col&&j+1>=0&&mat[i][j+1]!=0){
        vector<vector<int>> temp=mat;
        bottom=dfs(temp,i,j+1);
    }
    if(j-1<col&&j-1>=0&&mat[i][j-1]!=0){
        vector<vector<int>> temp=mat;
        left=dfs(temp,i,j-1);
    }
    if(i-1<row&&i-1>=0&&mat[i-1][j]!=0){
        vector<vector<int>> temp=mat;
        right=dfs(temp,i-1,j);
    }
    return sum+max(max(left,right),max(up,bottom));
}

#奇安信笔试##奇安信##笔经#
全部评论

相关推荐

昨天 00:42
已编辑
南京大学 Java
国家一级废话选手:同时收到offer,厉害! 但是有一个小问题:谁问你了?😡我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了
点赞 评论 收藏
分享
09-25 13:56
门头沟学院 Java
我的金10银11:直接外包给你还不要出钱,完美
点赞 评论 收藏
分享
2 5 评论
分享
牛客网
牛客企业服务