Description

Submission

class Solution {
    int m, n;
    vector<vector<int>> visited;
    vector<vector<int>> grid;
    vector<int> dirs;
    int ret;

    void dfs(int x, int y, int sum) {
        if(visited[x][y]) return;
        ret = max(ret, sum);
        if(!grid[x][y]) return;
        visited[x][y] = 1;
        
        for(int i = 0; i < 4; ++i) {
            int x1 = x + dirs[i];
            int y1 = y + dirs[i+1];

            if(x1 < 0 || x1 >= m || y1 < 0 || y1 >= n || visited[x1][y1] || !grid[x1][y1]) continue;

            dfs(x1, y1, sum + grid[x1][y1]);
        }

        visited[x][y] = 0;
    }
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        visited.resize(m, vector<int>(n, 0));
        dirs = {-1, 0, 1, 0, -1};
        this->grid = grid;
        ret = 0;

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                dfs(i, j, grid[i][j]);
            }
        }
        
        return ret;
    }
};