递归算法学习——黄金矿工，不同路径III

目录

​编辑

一，黄金矿工

1.题意

2.题目分析

3.题目接口

4.解题思路及代码

二，不同路径III

1.题意

2.解释

3.题目接口

 4.解题思路及代码

---

 

一，黄金矿工

1.题意

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

• 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
• 矿工每次可以从当前位置向上下左右四个方向走。
• 每个单元格只能被开采（进入）一次。
• 不得开采（进入）黄金数目为 0 的单元格。
• 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

2.题目分析

这道题要我们做的便是找到一条路径，在这条路径上我们能够收集到的黄金的数量是最多的。在这道题里面还有一个前提便是当遇到数字为0的空格时便不能走这一条路径了。

3.题目接口

class Solution {
public:
    int getMaximumGold(vectorint>>& grid) {
 
    }
};

4.解题思路及代码

先来写个代码：

1.第一种写法

class Solution {
public:
    int m,n;
    int path;//表示每一条路径上的黄金数量
    int sum;//记录最大和
    int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};//坐标法表示坐标的上下左右移动
    int getMaximumGold(vectorint>>& grid) {
        m = grid.size(),n = grid[0].size();
        for(int i = 0;i
        {
            for(int j = 0;j
            {
                if(grid[i][j]!=0)//当找到不是0的位置时便可以从这个位置开始递归找结果
                {
 
                    path = grid[i][j];
                    int remark = grid[i][j];
                    grid[i][j]=0;//该位置被寻找了以后便要将该位置置为0
                    dfs(grid,i,j);
                    grid[i][j] = remark;
                    path-=remark;
                }
            }
        }
        return sum;
    }
 
    void dfs(vectorint>>&grid,int i,int j)
    {
        sum = max(sum,path);//找到sum与path中的较大值
        for(int k = 0;k<4;k++)
        {
           int x = i+dx[k],y = j+dy[k];
           if(x>=0&&x=0&&y0)
           {
               path+=grid[x][y];
               int temp = grid[x][y];
               grid[x][y] = 0;
               dfs(grid,x,y);
               path-=temp;
               grid[x][y] = temp;
           }
        }
    }
};

其实这道题的解法和我们之前写的矩阵深搜问题的解题代码是差不多的。小小的不同点便是要比较较大值来对sum进行更新。为了避免麻烦我们便用max在每一次进入递归时就比较一下对sum更新一下，以此来确保sum是最大值。

2.第二种写法

在上面的写法中我们使用的是全局变量path和修改原来的矩阵的方式来标记查找过的位置，在这里我们写一种不同的解法：

class Solution {
public:
    int m,n;
    int sum;
    bool used[15][15];//用相同大小的used数组来标记使用过的位置。
    int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
    int getMaximumGold(vectorint>>& grid) {
        m = grid.size(),n = grid[0].size();
        for(int i = 0;i
        {
            for(int j = 0;j
            {
                if(grid[i][j]!=0)
                {
                  used[i][j] = true;
                  dfs(grid,i,j,grid[i][j]);
                   used[i][j] = false;
                }
            }
        }
        return sum;
    }
 
    void dfs(vectorint>>&grid,int i,int j,int path)
    {
        sum = max(sum,path);
        for(int k = 0;k<4;k++)
        {
           int x = i+dx[k],y = j+dy[k];
           if(x>=0&&x=0&&y0&&!used[x][y])
           {
               used[x][y] = true;
              dfs(grid,x,y,path+grid[x][y]);
              used[x][y] = false;
           }
        }
    }
};

二，不同路径III

1.题意

在二维网格 grid 上，有 4 种类型的方格：

• 1 表示起始方格。且只有一个起始方格。
• 2 表示结束方格，且只有一个结束方格。
• 0 表示我们可以走过的空方格。
• -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

2.解释

这道题要我们做的便是在将数值为0的空格遍历完了以后到达数值为2的空格的路径有几条。还是深度优先搜索的问题。在这道题里数值为-1的格子是一个障碍物，不能去遍历。并且，每个空格只能遍历一次。

3.题目接口

class Solution {
public:
    int uniquePathsIII(vectorint>>& grid) {
 
    }
};

 4.解题思路及代码

先写代码：

class Solution {
public:
    int count ;//记录路径的个数
    int step;//记录要走的步数
    int num ;//记录当前走了多少步
    int m,n;
    bool used[20][20];
    int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
    int uniquePathsIII(vectorint>>& grid) {
       
       m = grid.size();
       n = grid[0].size();
       
       int beginx,beginy;
       for(int i = 0;i
       {
           for(int j = 0;j
           {
               if(grid[i][j]==0)
               {
                   step++;//找到0的个数
               }
               if(grid[i][j] == 1)//记录入口的下标
               {
                   beginx = i;
                   beginy = j;
               }
 
           }
       }
       
       step+=1;//算上2这一步
       used[beginx][beginy] = true;
       dfs(grid,beginx,beginy);
       return count;
    }
 
    void dfs(vectorint>>&grid,int i,int j)
    {
       
        
        if(num == step)
        {
            if(grid[i][j] == 2)
            {
                count++;
            }
            return;
        }
 
        for(int k = 0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
           
            if(x>=0&&x=0&&y-1&&!used[x][y])
            {
               
                 num++;
                 used[x][y] = true;
                 dfs(grid,x,y);
                 num--;
                 used[x][y] = false;
            }
 
        }
    }
};

样子还是和之前的题目的的解题代码相像但是在这里就要一个主动的递归出口了，也就是当所有的0都被遍历完了以后到了2这一步就得到了一个结果了。