class Solution {
public:
    int xx[4]={0,0,1,-1};
    int yy[4]={1,-1,0,0};
    int m,n;
    //vector<vector<bool>> st(16,vector<bool>(16,false));
    bool st[16][16];
    int getMaximumGold(vector<vector<int>>& grid) {
        int ans=0;
        m=grid.size(),n=grid[0].size();
        memset(st,false,sizeof st);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                st[i][j]=true;
                if(grid[i][j]!=0)ans=max(ans,dfs(i,j,grid));
                st[i][j]=false;
            }
        }
        return ans;
    }

    int dfs(int x,int y,vector<vector<int>>& grid){
        int tmp=grid[x][y];
        for(int i=0;i<4;i++){
            int dx=x+xx[i];
            int dy=y+yy[i];
            if(dx>=0&&dy>=0&&dx<m&&dy<n&&grid[dx][dy]!=0&&st[dx][dy]==false){
                st[dx][dy]=true;
                tmp=max(tmp,grid[x][y]+dfs(dx,dy,grid));
                st[dx][dy]=false;
            }
        }
        return tmp;
    }

};