黄金矿工
这一题是经典的网格dfs问题，三叶以及其小迷妹的做法中，有两个很精妙的简化：
- 一个五维数组
[-1,0,1,0,-1]可以描述当前位置的左上右下四个方向 优化used
/// 1219. 黄金矿工/// 这是仿照java的写法，最暴力的一种，结果也比较差pub fn get_maximum_gold(mut grid: Vec<Vec<i32>>) -> i32 {fn dfs(grid: &mut Vec<Vec<i32>>, res: &mut i32, row: usize, col: usize, mut temp: i32, used: &mut Vec<Vec<bool>>) {// 不论如何我们下来的时候已经是肯定有矿的temp += grid[row][col];*res = temp.max(*res);// 这一步很有意思，走四面的一种简化，左上右下的顺序！！！！let d: Vec<i32> = vec![-1, 0, 1, 0, -1];for x in 0..4 {let next_r = row as i32 + d[x];let next_c = col as i32 + d[x + 1];// 使用used为了保持usize时的复杂转换if next_c < 0 || next_r < 0 || next_c >= (grid[0].len() as i32) || next_r >= (grid.len() as i32) {continue;}let next_r = next_r as usize;let next_c = next_c as usize;if used[next_r][next_c] { continue; }// 还有个神奇的剪枝，为0的就不走了！！！！if grid[next_r][next_c] == 0 {continue;}used[next_r][next_c] = true;dfs(grid, res, next_r, next_c, temp, used);used[next_r][next_c] = false;}}let mut used = vec![vec![false; grid[0].len()]; grid.len()];let mut res = 0;(0..grid.len()).for_each(|i| (0..grid[i].len()).for_each(|j| {if grid[i][j] != 0 {used[i][j] = true;dfs(&mut grid, &mut res, i, j, 0, &mut used);used[i][j] = false;}}));res}
三叶小迷妹对这种做法进行了深一点的优化，没有使用used，简化了usize的转换： ```rust pub fn get_maximum_gold(mut grid: Vec
(0..grid.len()).for_each(|r| (0..grid[r].len()).for_each(|c| if grid[r][c] > 0 {
Solution::bt(0, r, c, &mut grid, &mut res);
}));
res }
fn bt(mut curr_gold: i32, r: usize, c: usize, grid: &mut Vec
let t_gold = grid[r][c];
// 防止走回来
grid[r][c] = 0;
let to = [-1, 0, 1, 0, -1];
(0..4).for_each(|i| {
let n_r = (r as i32 + to[i]) as usize;
let n_c = (c as i32 + to[i+1]) as usize;
if n_r < grid.len() && n_c < grid[n_r].len() && grid[n_r][n_c] != 0 {
Solution::bt(curr_gold, n_r, n_c, grid, max_gold);
}
});
grid[r][c] = t_gold;
}
注意，这样可行是因为rust的safe转换，比如：
```rust
#[test]
fn test() {
let x = -1;
println!("{}", x);
let r = -1;
let x = 0;
let x = (x + r) as usize;
println!("{}", x);
}
// 输出
-1
18446744073709551615
岛屿数量
类似黄金矿工，网格类dfs的解法都是，从某一个点出发，遍历周围的四个节点，是为进入下一层问题，虽然看着图是网格，但其实本质上是回溯，只是阶数不再一样了
岛屿数量这题也一样，我们从中遍历，如果遇到一个1的话，就从中散开，找到所有的1，然后将整个遍历过的岛屿标记为2，防止重复遍历即可。那么每找到一个1就是一个岛屿：
/// 200. 岛屿数量
pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
fn dfs(grid: &mut Vec<Vec<char>>, row: usize, col: usize) {
// if grid[row][col] == '2' {
// return;
// } 不再需要其他判断了！！！
let d = vec![-1, 0, 1, 0, -1];
for x in 0..4 {
let nr = (row as i32 + d[x]) as usize;
let nc = (col as i32 + d[x + 1]) as usize;
// 由于黄金矿工那题的解释，我们可以这么写，如果小于0的话，会被安全转换为较大的数
if nr >= grid.len() || nc >= grid[0].len() || grid[nr][nc] != '1' {
continue;
}
// 注意这里修改为2，比0保险一些，但是这题没影响
grid[nr][nc] = '2';
dfs(grid, nr, nc);
}
}
let mut res = 0;
(0..grid.len()).for_each(|i| (0..grid[i].len()).for_each(|j| {
if grid[i][j] == '1' {
res += 1;
dfs(&mut grid, i, j);
}
}));
res
}
与黄金矿工的区分
注意到了吗，黄金矿工是完整的dfs，而岛屿数量不是，因为黄金矿工在中途其实是用了一个额外的数组来进行存储走过的地方，而岛屿问题由于在走的过程中就修改了编号，所以就导致了dfs相比黄金矿工来说少了很多。
写法上面，由于使用到了used，黄金矿工用到了经典的修改-dfs-回溯写法
而岛屿问题是：修改-dfs，没有回溯！！！
岛屿最大面积
这一题思路和上一题一样，但是按照上一题的写法存在两个bug：
- 我们标记该岛屿被访问过的时刻不对，存在问题
我们应该标记的是当前被访问过，而不是接下来被访问过（上一题是nr nc）
pub fn max_area_of_island(mut grid: Vec<Vec<i32>>) -> i32 { fn dfs(grid: &mut Vec<Vec<i32>>, row: usize, col: usize) -> usize { // 注意位置应该在这里，而且应该是row，col grid[row][col] = 2; let d = vec![-1, 0, 1, 0, -1]; let mut temp = 1; for x in 0..4 { let nr = (row as i32 + d[x]) as usize; let nc = (col as i32 + d[x + 1]) as usize; // 由于黄金矿工那题的解释，我们可以这么写，如果小于0的话，会被安全转换为较大的数 if nr >= grid.len() || nc >= grid[0].len() || grid[nr][nc] != 1 { continue; } temp += dfs(grid, nr, nc); } temp } let mut res = 0; (0..grid.len()).for_each(|i| (0..grid[i].len()).for_each(|j| { if grid[i][j] == 1 { let temp = dfs(&mut grid, i, j); res = res.max(temp); } })); res as i32 }bug解析
为什么会有bug呢？
如果我们是像上一题一样在dfs前面才标记的话，对于岛屿的最后一个节点，比如
[[1,1][1,1]]，我们访问顺序是[0,0]-[0,1]-[1,0]-[1,1]，此时的标记为[2]-[2]-[2]-[1]为什么最后一位是1，导致多算一次呢，其实就在于前面的判断，当我们执行到最后一个位置的时候，因为此时四周都是不可达节点，导致走不到dfs，也就走不到重置当前值为2的位置，自然最后一个位置就是[1]而不是[2]，所以在回溯过程中，第一个节点还会检查其下面的节点，所以就多一个了第二个位置上面，更是严重，如果像上一题标记的是下一个的话，直接导致多找一次’
827. 最大人工岛
这一题的思路没见过不一定想得到，但是见过就发现，好tm简单
第一遍DFS，查找所有岛屿修改其标号，同时记录其大小
第二遍DFS，查找所有海洋区域，遍历海洋周围的四个节点，根据编号获取到如果连接获得的最大值
/// 827. 最大人工岛 pub fn largest_island(mut grid: Vec<Vec<i32>>) -> i32 { use std::collections::HashMap; fn dfs_island(grid: &mut Vec<Vec<i32>>, row: usize, col: usize, index: i32) -> usize{ grid[row][col] = index; let d = vec![-1, 0, 1, 0, -1]; let mut temp = 1; for x in 0..4 { let nr = (row as i32 + d[x]) as usize; let nc = (col as i32 + d[x+1]) as usize; if nr>=grid.len() || nc>=grid[0].len() || grid[nr][nc] != 1 { continue; } temp += dfs_island(grid, nr, nc, index); } temp } let mut index = 2; // 存储 <编号， 面积> let mut map = HashMap::new(); (0..grid.len()).for_each(|i| (0..grid[i].len()).for_each(|j| { // 找到一个人工岛 if grid[i][j] == 1 { let temp = dfs_island(&mut grid, i, j, index); map.insert(index, temp); index += 1; } })); // 没有陆地的特殊情况 let mut res = match map.get(&2) { None => { 0 } Some(x) => { *x as i32 } }; let d = vec![-1, 0, 1, 0, -1]; // 第二次遍历，遍历海洋 (0..grid.len()).for_each(|i| (0..grid[i].len()).for_each(|j| { // 找到每一个海洋 if grid[i][j] == 0 { // 查询周围的值 let mut used = vec![0; map.len() + 2]; let mut temp = 1; for x in 0..4 { let nr = (i as i32 + d[x]) as usize; let nc = (j as i32 + d[x+1]) as usize; if nr>=grid.len() || nc>=grid[0].len() || grid[nr][nc] == 0{ continue; } if used[grid[nr][nc] as usize] != 0 { continue; } temp += (*map.get(&grid[nr][nc]).expect("位置有问题")) as i32; used[grid[nr][nc] as usize] = 1; } res = res.max(temp); } })); res }这一题的边界很多，主要来说是三个：
注意中间的match，为了应对全0或者全1的情况
- 注意第二次遍历中的used，用来处理
[[1,1],[1,0]]这种被岛屿包围的海水的情况 注意上面记号的index，从2开始，并且应该是每一次找到岛屿后才++
华为题：如果是至多填两个呢
```rust // 最后结果 private int res = 0; public int largestIsland(int[][] grid) { if (grid==null || grid.length == 0){
return 1;}
int index = 2;//index表示岛屿的编号，0是海洋1是陆地，从2开始遍历 //岛屿编号：岛屿面积 HashMap
// 计算每个岛屿的面积，并标记是第几个岛屿 for (int r=0;r<grid.length;r++){
for (int c=0;c<grid[0].length;c++){ if (grid[r][c] == 1){//遍历没有访问过的岛屿格子 int area = area(grid, r, c, index);//返回每个岛屿的面积，dfs indexAndAreas.put(index, area);//存入岛屿编号、岛屿面积 index++;//岛屿编号增加 res = Math.max(res, area);//记录最大的岛屿面积 } }} //res=0表示没有陆地，那么造一块，则返回2即可 if (res == 0) return 2; System.out.println(res); res = 0; // 第二次dfs，负责查找其中的海洋节点，然后查看连接起来的时候能够得到的最大面积 for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) { // 如果为海洋节点的话，尝试标记，注意去重一次 if (grid[i][j] == 0) { two_size(grid, i, j, indexAndAreas); } }} return res; } // 尝试插入两个海洋节点，并返回其值 private void two_size(int[][] grid, int row, int col, HashMap
used = new HashSet<>(); // 获取并计算第一个元素连接起来的区域大小 System.out.println(“[—-]当前处理的为0节点为：[“+row+”,”+col+”]”); int temp = 1; HashSet set = findNeighbour(grid, row, col); if (set.size() != 0) { for (Integer index : set) { temp += indexAndAreas.get(index); used.add(index); }} int last = temp; // 查找第二个为0的元素,防止往回遍历，因此写两个for，查找四周 int[] d = new int[]{-1, 0, 1, 0, -1, 0}; for (int i = 0; i < 4; i++) {
int r = d[i] + row; int c = d[i+1] + col; // 防止重复 if (r == row && c <= col) continue; if (!inArea(grid, r, c)) continue; if (grid[r][c] == 0) { temp ++; System.out.println("[--]内部处理的节点为：["+r+","+c+"]"); set = findNeighbour(grid, r, c); if (set.size() != 0) { for (Integer index : set) { if (!used.contains(index)) temp += indexAndAreas.get(index); } } res = Math.max(res, temp); System.out.println("[--]更新得到res值为："+res); temp = last; }} System.out.println(“[——]out：”); }
/**
- 对于海洋格子，找到上下左右
- 每个方向，都要确保有效inArea以及是陆地格子，则表示是该海洋格子的陆地邻居
*/
private HashSet
findNeighbour(int[][] grid, int r, int c){ HashSet hashSet = new HashSet<>(); if (inArea(grid,r-1,c) && grid[r-1][c] != 0){
} if (inArea(grid,r+1,c) && grid[r+1][c] != 0){hashSet.add(grid[r-1][c]);
} if (inArea(grid,r,c-1) && grid[r][c-1] != 0){hashSet.add(grid[r+1][c]);
} if (inArea(grid,r,c+1) && grid[r][c+1] != 0){hashSet.add(grid[r][c-1]);
} return hashSet; }hashSet.add(grid[r][c+1]);
/**
- dfs方法，将格子填充为index，即表示这个格子属于哪个岛的
- 计算岛屿面积，上下左右，当然这个可以优化的，因为不需要计算上面的，会有重复
*/
private int area(int[][] grid, int r, int c,int index){
if (!inArea(grid,r,c)){
} //不为1，表示为海洋格子或者已经遍历过了 if (grid[r][c] != 1){return 0;
} grid[r][c] = index;//设置当前格子为某个岛屿编号 return 1 + area(grid,r-1,c,index) + area(grid,r+1,c,index) + area(grid,r,c-1,index) + area(grid,r,c+1,index); }return 0;
/**
判断grid[r][c]是否大小合适 */ private boolean inArea(int[][] grid,int r,int c){ return r>=0 && r
<a name="MALnm"></a> # 最短路径长度(黄金矿工类型dfs) 华为题，输入是五行，第一行是地图大小，第二行是起点，第三行终点，第四行水池数量，第五行水池位置。<br />求从起点到终点的最短路径长度，一共有多少条，其中，不可以走有水的地方。 ```rust public int res = 0; // 记录最终数量 public int least_len = Integer.MAX_VALUE; // 记录最短路径 // 输入分别为地图、起点、终点以及临时长度 public void dfs(int[][] area, int s_r, int s_c, int e_r, int e_d, int temp_len) { if (!judge(s_r, s_c, area)) return; if (s_r == e_r && s_c == e_d) { if (temp_len == least_len){ res += 1; System.out.println("原数据更新res"+res); }else if (temp_len < least_len) { least_len = temp_len; res = 1; System.out.println("另起炉灶"+res+" "+least_len); } return; } int[] d = new int[]{-1, 0, 1, 0, -1, 0}; for (int i = 0; i < 4; i++) { int nr = s_r + d[i]; int nc = s_c + d[i + 1]; System.out.println(s_r+","+s_c+"->"+nr+","+nc); // 否则该单元格可以走 area[s_r][s_c] = 2; dfs(area, nr, nc, e_r, e_d, temp_len + 1); // 否则该单元格可以走 area[s_r][s_c] = 0; } } private boolean judge(int r, int c, int[][] area) { if (r < 0 || c < 0 || r > area.length-1 || c > area[0].length-1){ return false; } return area[r][c] < 1; }
若有收获，就点个赞吧
0 人点赞
