1. Every time you reach a cell, you collect all the gold present in that cell. 2. You can go one step left, right, up, or down from your current cell’s position. 3. You can’t visit the cell which you have already visited. 4. You can’t visit a cell with 0 gold. 5. You can choose any cell to start and stop collecting gold.
The first line of the input contains an integer T denoting the number of test cases. Each test case’s first line contains two space-separated integers N and M, denoting the rows and columns in the grid respectively. The next N lines of each test case contain M space-separated integers denoting the amount of gold present in a cell.
For every test case, print a single line containing a single integer denoting the maximum amount of gold you can collect. The output of each test case will be printed in a separate line.
You do not need to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 5 1 <= N, M <= 10 0 <= GRID[i][j] <= 10 ^ 5 Time limit: 1 sec.
We will perform dfs from each non-zero cell. For each cell with non-zero gold that we visit, we’ll visit it’s four possible neighbours and choose the maximum out of these four to get the maximum amount of gold that we collect using backtracking. Since we can’t revisit any cell, we’ll mark that as visited and won’t revisit it.