1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
void dfs(int x, int y, vector<vector<int>>& grid, int st[110][110], int sum, int& res)
{
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
res = max(res, sum);
for (int i = 0; i < 4; ++i)
{
int nx = dx[i] + x, ny = dy[i] + y;
if (nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid[0].size()) continue;
if (st[nx][ny] || grid[nx][ny] == 0) continue;
st[nx][ny] = true;
dfs(nx, ny, grid, st, sum + grid[nx][ny], res);
st[nx][ny] = false;
}
}
int getMaximumGold(vector<vector<int>>& grid) {
int st[110][110];
memset(st, false, sizeof st);
int res = 0;
for (int i = 0; i < grid.size(); ++i)
{
for (int j = 0; j < grid[0].size(); ++j)
{
if (grid[i][j] == 0) continue;
st[i][j] = true;
dfs(i, j, grid, st, grid[i][j], res);
st[i][j] = false;
}
}
return res;
}
};
|