#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));
}