【每日刷题】Day142
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 1219. 黄金矿工 - 力扣（LeetCode）
2. 980. 不同路径 III - 力扣（LeetCode）
3. 733. 图像渲染 - 力扣（LeetCode）
1. 1219. 黄金矿工 - 力扣（LeetCode）
//思路：dfs+哈希
//本题思路与 Day 141 中的 "单词搜索" 十分相似
class Solution {
public:
int ans = 0;
//这里tmp是形参，回溯时自动恢复现场
void dfs(vector<vector<int>>& grid,int i,int j,vector<vector<bool>>& hash,int tmp)
{
if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||!grid[i][j])//这里判断能否继续搜索的条件：1. 越界访问 2. 当前位置为0
{
ans = ans>tmp?ans:tmp;//记录较大值
return;
}
tmp+=grid[i][j];
hash[i][j] = true;
if(i-1>=0&&!hash[i-1][j])
dfs(grid,i-1,j,hash,tmp);
if(i+1<=grid.size()&&!hash[i+1][j])//这里就知道为什么哈希要多开一格了，因为 i+1<=grid.size()，如果不多开一格会越界
dfs(grid,i+1,j,hash,tmp);
if(j-1>=0&&!hash[i][j-1])
dfs(grid,i,j-1,hash,tmp);
if(j+1<=grid[0].size()&&!hash[i][j+1])
dfs(grid,i,j+1,hash,tmp);
hash[i][j] = false;
}
int getMaximumGold(vector<vector<int>>& grid)
{
vector<vector<bool>> hash(16,vector<bool>(16));
for(int i = 0;i<grid.size();i++)
{
for(int j = 0;j<grid[0].size();j++)
{
if(grid[i][j])//寻找非0元素进行dfs
{
hash[i][j] = true;
dfs(grid,i,j,hash,0);
hash[j][j] = false;
}
}
}
return ans;
}
};
2. 980. 不同路径 III - 力扣（LeetCode）
//思路：dfs+哈希
class Solution {
public:
int ans = 0;
void dfs(vector<vector<int>>& grid,int i,int j,int sum,int tmp,vector<vector<bool>>& hash)//tmp变量用于记录走过0位置的数量
//哈希表用于记录已经走过的位置，防止重复走过
//sum就是0的总数
{
if((i>=grid.size()||i<0||j>=grid[0].size()||j<0)||(grid[i][j] == -1 || (grid[i][j]==2&&tmp!=sum)))//剪枝操作：也就是此路不通，另寻他路
return;
if(grid[i][j]==2&&tmp==sum)//走完了所有的0位置，并且最终所处位置为2
{
ans++;
return;
}
tmp++;//每走过一个0位置tmp++
hash[i][j] = true;//将当前位置标记为 "已访问"
//上、下、左、右递归
if(i-1>=0&&!hash[i-1][j])
dfs(grid,i-1,j,sum,tmp,hash);
if(i+1<=grid.size()&&!hash[i+1][j])
dfs(grid,i+1,j,sum,tmp,hash);
if(j-1>=0&&!hash[i][j-1])
dfs(grid,i,j-1,sum,tmp,hash);
if(j+1<=grid[0].size()&&!hash[i][j+1])
dfs(grid,i,j+1,sum,tmp,hash);
hash[i][j] = false;//恢复现场
}
int uniquePathsIII(vector<vector<int>>& grid)
{
vector<vector<bool>> hash(21,vector<bool>(21));
int sum = 0;
for(int i = 0;i<grid.size();i++)
for(int j = 0;j<grid[0].size();j++)
if(!grid[i][j]) sum++;//统计0的个数
for(int i = 0;i<grid.size();i++)
{
for(int j = 0;j<grid[0].size();j++)
{
if(grid[i][j]==1)
{
dfs(grid,i,j,sum,-1,hash);//从1位置开始 dfs
break;
}
}
}
return ans;
}
};
3. 733. 图像渲染 - 力扣（LeetCode）
//思路：floodfill算法。实际上还是dfs+哈希
class Solution {
public:
void dfs(vector<vector<int>>& image, int i, int j, int color,int flag, vector<vector<bool>>& hash)
{
if(i>=image.size()||i<0||j>=image[0].size()||j<0||image[i][j]!=flag)//剪枝操作同时是递归结束条件：1. 越界 2. 当前区域颜色与原始颜色不相同
return;
image[i][j] = color;//将与原始颜色相同的区域更改为 color
hash[i][j] = true;//将当前位置设为 "已访问"
//上、下、左、右递归
if(i-1>=0&&!hash[i-1][j])
dfs(image,i-1,j,color,flag,hash);
if(i+1<=image.size()&&!hash[i+1][j])
dfs(image,i+1,j,color,flag,hash);
if(j-1>=0&&!hash[i][j-1])
dfs(image,i,j-1,color,flag,hash);
if(j+1<=image[0].size()&&!hash[i][j+1])
dfs(image,i,j+1,color,flag,hash);
hash[i][j] = false;//恢复现场
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
{
vector<vector<bool>> hash(51,vector<bool>(51));
dfs(image,sr,sc,color,image[sr][sc],hash);//从 [sr,sc] 位置开始 dfs
return image;
}
};
