目录
为⾼尔夫⽐赛砍树（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
你被请来给⼀个要举办⾼尔夫⽐赛的树林砍树。树林由⼀个 m x n 的矩阵表⽰，在这个矩阵中：
◦ 0 表⽰障碍，⽆法触碰
◦ 1 表⽰地⾯，可以⾏⾛
◦ ⽐ 1 ⼤的数 表⽰有树的单元格，可以⾏⾛，数值表⽰树的⾼度
每⼀步，你都可以向上、下、左、右四个⽅向之⼀移动⼀个单位，如果你站的地⽅有⼀棵树，那么你可以决定是否要砍倒它。
你需要按照树的⾼度从低向⾼砍掉所有的树，每砍过⼀颗树，该单元格的值变为 1 （即变为地⾯）。
你将从 (0, 0) 点开始⼯作，返回你砍完所有树需要⾛的最⼩步数。如果你⽆法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的⾼度是相同的，并且你⾄少需要砍倒⼀棵树。
⽰例1：
输⼊：forest=[[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上⾯的路径，你可以⽤6步，按从最矮到最⾼的顺序砍掉这些树。⽰例2：
输⼊：forest=[[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间⼀⾏被障碍阻塞，⽆法访问最下⾯⼀⾏中的树。⽰例3：
输⼊：forest=[[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与⽰例1相同的路径来砍掉所有的树。
提⽰：
◦ m == forest.length
◦ n == forest[i].length
◦ 1 <= m, n <= 50
◦ 0 <= forest[i][j] <= 10^9
讲解算法原理
解法：
算法思路：
a. 先找出砍树的顺序；
b. 然后按照砍树的顺序，⼀个⼀个的⽤ bfs 求出最短路即可。
编写代码
c++算法代码：
class Solution
{
int m, n;
public:
int cutOffTree(vector<vector<int>>& f)
{
m = f.size(), n = f[0].size();
// 1. 准备⼯作：找出砍树的顺序
vector<pair<int, int>> trees;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(f[i][j] > 1) trees.push_back({i, j});
sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const
pair<int, int>& p2)
{
return f[p1.first][p1.second] < f[p2.first][p2.second];
});
// 2. 按照顺序砍树
int bx = 0, by = 0;
int ret = 0;
for(auto& [a, b] : trees)
{
int step = bfs(f, bx, by, a, b);
if(step == -1) return -1;
ret += step;
bx = a, by = b;
}
return ret;
}
bool vis[51][51];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey)
{
if(bx == ex && by == ey) return 0;
queue<pair<int, int>> q;
memset(vis, 0, sizeof vis); // 清空之前的数据
q.push({bx, by});
vis[bx][by] = true;
int step = 0;
while(q.size())
{
step++;
int sz = q.size();
while(sz--)
{
auto [a, b] = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if(x >= 0 && x < m && y >= 0 && y < n && f[x][y] && !vis[x]
[y])
{
if(x == ex && y == ey) return step;
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};java算法代码：
class Solution
{
int m, n;
public int cutOffTree(List<List<Integer>> f)
{
m = f.size(); n = f.get(0).size();
List<int[]> trees = new ArrayList<>();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(f.get(i).get(j) > 1)
trees.add(new int[]{i, j});
Collections.sort(trees, (a, b) ->
{
return f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
});
int bx = 0, by = 0;
int ret = 0;
for(int[] next : trees)
{
int a = next[0], b = next[1];
int step = bfs(f, bx, by, a, b);
if(step == -1) return -1;
ret += step;
bx = a; by = b;
}
return ret;
}
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0 ,0};
public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey)
{
if(bx == ex && by == ey) return 0;
Queue<int[]> q = new LinkedList<>();
boolean[][] vis = new boolean[m][n];
q.add(new int[]{bx, by});
vis[bx][by] = true;
int step = 0;
while(!q.isEmpty())
{
int sz = q.size();
step++;
while(sz-- != 0)
{
int[] t = q.poll();
int a = t[0], b = t[1];
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if(x >= 0 && x < m && y >= 0 && y < n && f.get(x).get(y)
!= 0 && !vis[x][y])
{
if(x == ex && y == ey) return step;
q.add(new int[]{x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
}01矩阵（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个由0和1组成的矩阵mat，请输出⼀个⼤⼩相同的矩阵，其中每⼀个格⼦是mat中对应位置元素到最近的0的距离。
两个相邻元素间的距离为1。
⽰例1：
输⼊：mat=[[0,0,0],[0,1,0],[0,0,0]]输出：[[0,0,0],[0,1,0],[0,0,0]]
⽰例2：
输⼊：mat=[[0,0,0],[0,1,0],[1,1,1]]输出：[[0,0,0],[0,1,0],[1,2,1]]
提⽰：
m==mat.length
n==mat[i].length
1<=m,n<=104
1<=m*n<=104
mat[i][j]iseither0or1.
mat中⾄少有⼀个0
讲解算法原理
解法（bfs）（多个源头的最短路问题）
算法思路：
对于求的最终结果，我们有两种⽅式：
• 第⼀种⽅式：从每⼀个 1 开始，然后通过层序遍历找到离它最近的 0 。
这⼀种⽅式，我们会以所有的 1 起点，来⼀次层序遍历，势必会遍历到很多重复的点。并且如果矩阵中只有⼀个 0 的话，每⼀次层序遍历都要遍历很多层，时间复杂度较⾼。
• 换⼀种⽅式：从 0 开始层序遍历，并且记录遍历的层数。当第⼀次碰到 1 的时候，当前的层数
就是这个 1 离 0 的最短距离。
这⼀种⽅式，我们在遍历的时候标记⼀下处理过的 1 ，能够做到只⽤遍历整个矩阵⼀次，就能得到最终结果。
但是，这⾥有⼀个问题， 0 是有很多个的，我们怎么才能保证遇到的 1 距离这⼀个 0 是最近的呢？
其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成⼀个整体，每次把当前队列⾥⾯的所有元素向外扩展⼀次。
编写代码
c++算法代码：
class Solution
{
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
int m = mat.size(), n = mat[0].size();
// dist[i][j] == -1 表⽰：没有搜索过
// dist[i][j] != -1 表⽰：最短距离
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
// 1. 把所有的源点加⼊到队列中
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(mat[i][j] == 0)
{
q.push({i, j});
dist[i][j] = 0;
}
// 2. ⼀层⼀层的往外扩
while(q.size())
{
auto [a, b] = q.front(); q.pop();
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
}
}
}
return dist;
}
};java算法代码：
class Solution
{
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
public int[][] updateMatrix(int[][] mat)
{
int m = mat.length, n = mat[0].length;
// dist[i][j] == -1：标记当前位置没有被搜索过
// dist[i][j] != -1：存的是最短距离
int[][] dist = new int[m][n];
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
dist[i][j] = -1;
Queue<int[]> q = new LinkedList<>();
// 1. 把所有的源点加⼊到队列⾥⾯
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(mat[i][j] == 0)
{
dist[i][j] = 0;
q.add(new int[]{i, j});
}
}
// 2. ⼀层⼀层的往外扩
while(!q.isEmpty())
{
int[] t = q.poll();
int a = t[0], b = t[1];
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
q.add(new int[]{x, y});
}
}
}
return dist;
}
}