我们这里主要探讨 权值为1 的最短路问题。
而对于 权值为1的最短路问题 ：即不考虑每个路径点的值，只考虑最短的路径是什么即可。
关于如何用dfs或bfs算法对二维数组进行搜索，可以看下面的一篇文章：
【算法】bfs与dfs算法解决FloodFill（洪流）问题（C++）
思路
代码
class Solution {
public:
int dx[4] = {0, 0, -1, 1}; // 标记x, y 坐标的四个方向走向
int dy[4] = {-1, 1, 0, 0};
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int step = 0; // 记录走过的步数
int a = entrance[0], b = entrance[1]; // 提取起始位置坐标
int m = maze.size(), n = maze[0].size();
vector<vector<bool>> visit; // 标记是否被遍历过
visit.resize(m, vector<bool>(n, false)); // 初始化
visit[a][b] = true;
queue<pair<int, int>> q; // 存储位置坐标
q.push({a, b});
while(!q.empty())
{
++step;
int sz = q.size(); // 按层遍历当前队中元素
for(int j = 0; j < sz; ++j)
{
auto [_x, _y] = q.front(); // 提取队头元素坐标
q.pop();
for(int i = 0; i < 4; ++i) // 搜索上下左右四个位置
{
int x = _x + dx[i];
int y = _y + dy[i];
if((x < m && x >= 0) && (y < n && y >= 0) && !visit[x][y] && maze[x][y] == '.')
{
// 判断此时是否是终点
if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
q.push({x, y});
visit[x][y] = true;
}
}
}
}
return -1;
}
};
思路
题意分析 ：通过将字符串startGene 转化为 endGene，且每次变化都在数组bank中存在，求转化的最少次数。
当我们把startGene 转化 求得最终结果endGene时，如下图所示，其本质上属于 边权为1的最路径问题，据此我们有以下思路：
解法 ： 哈希表 + 队列 BFS
代码
对于下面的代码，主要就一处进行解释：
为什么要用临时字符串tmp ?
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> visited; // 用于记录所有检索过的状态
unordered_set<string> hash(bank.begin(), bank.end()); // 记录基因库中的所有序列
string change = "ACGT"; // 用于对序列中字符进行更改
// 处理边界情况
if(startGene == endGene) return 0;
if(!hash.count(endGene)) return -1;
queue<string> q; // 创建队列存储满足条件的序列变化
q.push(startGene);
visited.insert(startGene);
int minCount = 0; // 最小变化次数（最终结果）
while(q.size())
{
++minCount;
int sz = q.size();
while(sz--) // 队列大小即为 下一次待变化的序列数
{
string t = q.front(); // 提取当前序列
q.pop();
for(int i = 0; i < 8; ++i) // 每个序列有8个字符，对所有字符进行转化
{
string tmp = t; // 每次循环只对一个字符进行更改，使用临时字符串tmp，使不对t一直进行更改（比如GAAA->TAAA后，继续进）
for(int j = 0; j < 4; ++j) // 每个字符进行"ACGT"四种变化
{
tmp[i] = change[j]; // 更改字符
if(hash.count(tmp) && !visited.count(tmp)) // 此时序列是合法的更改（在bank中）
{
if(tmp == endGene) return minCount; // 此时的合法序列为最终结果，返回
q.push(tmp);
visited.insert(tmp);
}
}
}
}
}
return -1;
}
思路
代码
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> hash(wordList.begin(), wordList.end());
unordered_set<string> visited;
if(!hash.count(endWord)) return 0;
queue<string> q;
q.push(beginWord);
visited.insert(beginWord);
int minCount = 1; // 首先加上beginWord自身
while(q.size())
{
++minCount;
int sz = q.size();
while(sz--)
{
string t = q.front();
q.pop();
for(int i = 0; i < t.size(); ++i) // 对每个单词的每一位进行改变
{
string tmp = t;
for(char ch = 'a'; ch <= 'z'; ++ch)
{
tmp[i] = ch;
if(!visited.count(tmp) && hash.count(tmp))
{
if(tmp == endWord) return minCount;
q.push(tmp);
visited.insert(tmp);
}
}
}
}
}
return 0;
}
思路
代码
class Solution {
public:
int m, n; // 定义全局变量便于访问
int cutOffTree(vector<vector<int>>& forest) {
m = forest.size(), n = forest[0].size();
// 1. 通过容器存储 需要砍的树
vector<pair<int, int>> trees;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
if(forest[i][j] > 1) trees.push_back({i, j}); // 大于1的是待砍的树
// 1.5 排序，找出 砍树顺序
sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2){
return forest[p1.first][p1.second] < forest[p2.first][p2.second];
});
// 2. 砍树步骤
int bx = 0, by = 0; // 起始位置 坐标
int minCount = 0;
for(auto &[a, b] : trees)
{
// step : 从当前位置到下一位置的步数
int step = bfs(forest, bx, by, a, b); // 后四个参数分别为起始位置的x, y坐标以及目标位置的x, y坐标
if(step == -1) return -1; // 其中一棵树无法砍到，最终就无法砍掉所有的树
minCount += step;
bx = a, by = b; // 更新下一次的起始位置
}
return minCount;
}
bool visited[51][51]; // 用于记录当前位置是否被检索过
int dx[4] = {0, 0, -1, 1}; // 用于x坐标的上下左右方向更新
int dy[4] = {-1, 1, 0, 0}; // 用于y坐标的上下左右方向更新
int bfs(vector<vector<int>> &forest, int beginX, int beginY, int endX, int endY)
{
if(beginX == endX && beginY == endY) return 0;
memset(visited, false, sizeof(visited));
queue<pair<int, int>> q; // 创建队列用于搜索
q.push({beginX, beginY});
visited[beginX][beginY] = 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) && !visited[x][y] && forest[x][y]) // 在合法范围内对所有未被检索的位置执行：
{
if(x == endX && y == endY) return step;
q.push({x, y});
visited[x][y] = true;
}
}
}
}
return -1;
}
};