class Solution {
public:
int ret = 0, m = 0, n = 0, tempret = 0;
    bool isLegal(vector<vector<int>>& grid, int m_, int n_) {
        if (m_ < 0 || n_ < 0) return false;
        if (m_ >= m || n_ >= n) return false;
        if (!grid[m_][n_]) return false;
        return true;
    }
    void DFS(vector<vector<int>>& grid, bool **vis, int nowm, int nown) {
        tempret += grid[nowm][nown];
        ret = tempret > ret ? tempret : ret;
        if (isLegal(grid, nowm-1, nown) && !vis[nowm-1][nown]) {
            vis[nowm-1][nown] = true;
            DFS(grid, vis, nowm-1, nown);
            vis[nowm-1][nown] = false;
        }
        if (isLegal(grid, nowm, nown-1) && !vis[nowm][nown-1]) {
            vis[nowm][nown-1] = true;
            DFS(grid, vis, nowm, nown-1);
            vis[nowm][nown-1] = false;
        }
        if (isLegal(grid, nowm+1, nown) && !vis[nowm+1][nown]) {
            vis[nowm+1][nown] = true;
            DFS(grid, vis, nowm+1, nown);
            vis[nowm+1][nown] = false;
        }
        if (isLegal(grid, nowm, nown+1) && !vis[nowm][nown+1]) {
            vis[nowm][nown+1] = true;
            DFS(grid, vis, nowm, nown+1);
            vis[nowm][nown+1] = false;
        }
        tempret -= grid[nowm][nown];
    }
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        bool** vis = new bool*[m];
        for (int i = 0; i < m; i++) {
            vis[i] = new bool[n];
            for (int j = 0; j < n; j++)
                vis[i][j] = false;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    tempret = 0;
                    vis[i][j] = true;
                    DFS(grid, vis, i, j);
                    vis[i][j] = false;
                }
            }
        }
        return ret;
    }
};