目录
一BFS解决FloodFill算法
1图像渲染
2岛屿数量
3岛屿的最大面积
4被环绕的区域
二BFS解决蛋源最短路径问题
1迷宫中离入口最近的出口
2最小基因变化
3单词接龙
4为高尔夫比赛砍树
三BFS解决多源最短路径问题
1 01矩阵
2飞地的数量
3地图中的最高点
4地图分析
一BFS解决FloodFill算法
floodfill算法中文名：洪水灌溉：这类问题都是要来找出性质相同的联通块；解决好一道后，后面遇到类型的题目代码也是类似的！
1图像渲染
oj链接：图像渲染
解法：bfs
1.先把开始的坐标{sr，sc}放进队列中；
2.取出队头坐标{x，y}，直接将它改成color(队列坐标都是合法的，待改的)，再把它上下左右的坐标(等于image[sr][sc])放到队列中...
//dfs
class Solution
{
public:
int target, newcolor, m, n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void dfs(vector<vector<int>> &image, int i, int j)
{
image[i][j] = newcolor;
for (int a = 0; a < 4; a++)
{
int x = i + dx[a], y = j + dy[a];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target)
{
dfs(image, x, y);
}
}
}
vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int color)
{
if (image[sr][sc] == color)
return image; // 特殊判断
m = image.size(), n = image[0].size();
target = image[sr][sc];
newcolor = color;
dfs(image, sr, sc);
return image;
}
};
//bfs
class Solution
{
public:
vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int color)
{
if (image[sr][sc] == color)
return image; // 特殊判断
// bfs前准备
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int m = image.size(), n = image[0].size();
int target = image[sr][sc];
// bfs主逻辑
queue<pair<int, int>> qe;
qe.push({sr, sc});
while (qe.size())
{
int sz = qe.size();
for (int i = 0; i < sz; i++)
{
auto &[a, b] = qe.front();
qe.pop();
if (image[a][b] == target)
image[a][b] = color;
for (int j = 0; j < 4; j++)
{
int x = a + dx[j], y = b + dy[j];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target)
{
qe.push({x, y});
}
}
}
}
return image;
}
};2岛屿数量
oj链接：岛屿数量
解法：bfs
1. 两层for循环找‘1’&&该位置没被标记，将该坐标进队列，执行一次bfs；
2.bfs的主逻辑与上题类似：但在这里要注意：坐标进队列后要立刻马上进行标记！如果是取出节点后标记的话，会有重复节点进队列导致超时！！
//dfs
class Solution
{
public:
bool vis[300][300] = {false};
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int m, n;
void dfs(vector<vector<char>> &grid, int i, int j)
{
vis[i][j] = true;
for (int a = 0; a < 4; a++)
{
int x = i + dx[a], y = j + dy[a];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
{
dfs(grid, x, y);
}
}
}
int numIslands(vector<vector<char>> &grid)
{
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1' && !vis[i][j])
{
ret++;
dfs(grid, i, j);
}
}
}
return ret;
}
};
//bfs
class Solution
{
public:
bool vis[300][300] = {false};
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int m, n;
queue<pair<int, int>> q;
void bfs(vector<vector<char>> &grid, int i, int j)
{
//进队列后必须立刻进行标记！
q.push({i, j});
vis[i][j] = true;
while (q.size())
{
auto [a, b] = q.front();
q.pop();
// vis[a][b]=true;节点会重复进队列，导致超时
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
{
q.push({x, y});
vis[x][y] = true;
}
}
}
}
int numIslands(vector<vector<char>> &grid)
{
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1' && !vis[i][j])
{
ret++;
bfs(grid, i, j);
}
}
}
return ret;
}
};3岛屿的最大面积
oj链接：岛屿的最大面积
与上题思路类似：只不过我们要求的是最大面积，我们可以：进行dfs后把岛屿的面积带出来
class Solution
{
public:
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
bool vis[50][50] = {false};
int m, n;
queue<pair<int, int>> q;
void bfs(vector<vector<int>> &grid, int i, int j, int *area)
{
q.push({i, j});
vis[i][j] = true;
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
{
q.push({x, y});
vis[x][y] = true;
(*area)++;
}
}
}
}
int maxAreaOfIsland(vector<vector<int>> &grid)
{
m = grid.size(), n = grid[0].size();
int MaxArea = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1 && !vis[i][j])
{
int area = 1; // 从该位置进行bfs：找出该位置处岛屿的面积
bfs(grid, i, j, &area);
MaxArea = max(MaxArea, area);
}
}
}
return MaxArea;
}
};4被环绕的区域
oj链接：被围绕的区域
解法：bfs
此题在递归 搜索与回溯算法题
class Solution
{
public:
bool vis[200][200];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int m, n;
queue<pair<int, int>> q;
void bfs(vector<vector<char>> &board, int i, int j)
{
q.push({i, j});
vis[i][j] = true;
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !vis[x][y])
{
q.push({x, y});
vis[x][y] = true;
}
}
}
}
void solve(vector<vector<char>> &board)
{
m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++)
{
if (board[i][0] == 'O')
bfs(board, i, 0);
if (board[i][n - 1] == 'O')
bfs(board, i, n - 1);
}
for (int j = 0; j < n; j++)
{
if (board[0][j] == 'O')
bfs(board, 0, j);
if (board[m - 1][j] == 'O')
bfs(board, m - 1, j);
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'O' && !vis[i][j])
board[i][j] = 'X';
}
}
}
};二BFS解决蛋源最短路径问题
1迷宫中离入口最近的出口
oj链接：迷宫中离入口最近的出口
从开始粗来一次bfs遍历即可；如果进队列的坐标是出口，直接返回遍历的层数ret即可！
class Solution
{
public:
bool vis[100][100];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int m, n;
int nearestExit(vector<vector<char>> &maze, vector<int> &entrance)
{
m = maze.size(), n = maze[0].size();
queue<pair<int, int>> q;
int beginx = entrance[0], beginy = entrance[1];
q.push({beginx, beginy});
vis[beginx][beginy] = true;
int ret = 0;
while (q.size())
{
ret++; // 往外扩
int sz = q.size();
for (int i = 0; i < sz; i++)
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' &&!vis[x][y])
{
if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
return ret; // 找到出口了，直接返回遍历的层数,即最短路径
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};2最小基因变化
oj链接：最小基因变化
class Solution
{
public:
int minMutation(string startGene, string endGene, vector<string> &bank)
{
char arr[4] = {'A', 'G', 'C', 'T'};
unordered_map<string, bool> vis;
for (auto &s : bank)
vis[s] = false;
if(!vis.count(endGene)) return -1;// 不存在直接返回
queue<string> q;
q.push(startGene);
vis[startGene] = true; // 有可能基因库也有这个，提前标记
int ret = 0;
while (q.size())
{
ret++;
int sz = q.size();
for (int i = 0; i < sz; i++)
{
string s = q.front();
q.pop();
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 4; j++)
{
string tmp = s;
tmp[i] = arr[j]; // 这里就没必要判断tmp[i]是否与arr[j]相等:因为前面我们已经标记过了
if (vis.count(tmp) && !vis[tmp])
{
if (tmp == endGene)
return ret;
q.push(tmp);
vis[tmp] = true;
}
}
}
}
}
return -1;
}
};3单词接龙
oj链接：单词接龙
与上题思路类似
class Solution
{
public:
int ladderLength(string beginWord, string endWord, vector<string> &wordList)
{
string t = "qwertyuiopasdfghjklzxcvbnm";
unordered_map<string, bool> vis;
for (auto &word : wordList)
vis[word] = false;
if (!vis.count(endWord))
return 0;
int ans = 1;
queue<string> qe;
qe.push(beginWord);
vis[beginWord] = true;
while (qe.size())
{
ans++;
int sz = qe.size();
while (sz--)
{
string s = qe.front();
qe.pop();
for (int i = 0; i < s.size(); i++)
{
char ch = s[i];
for (int j = 0; j < 26; j++)
{
s[i] = t[j];
if (vis.count(s) && !vis[s])
{
if (s == endWord)
return ans;
qe.push(s);
vis[s] = true;
}
}
s[i] = ch;
}
}
}
return 0;
}
};4为高尔夫比赛砍树
oj链接：为高尔夫比赛砍树
注意：
不是说一定要砍，当初做的时候就是看劈叉了~
class Solution
{
public:
typedef pair<int, int> PII;
int n, m;
int cutOffTree(vector<vector<int>> &forest)
{
// 先预处理砍树顺序
vector<PII> trees;
n = forest.size(), m = forest[0].size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (forest[i][j] > 1)
trees.push_back({i, j});
}
}
sort(trees.begin(), trees.end(), [&](const PII &p1, const PII &p2)
{ return forest[p1.first][p1.second] < forest[p2.first][p2.second]; });
// 若干个迷宫问题的最小步数累加
int dx = 0, dy = 0;
int ret = 0;
for (auto &[a, b] : trees)
{
int step = bfs(forest, dx, dy, a, b);
if (step == -1)
return -1;
ret += step;
dx = a, dy = b; // 更新位置
}
return ret;
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int bfs(vector<vector<int>> &forest, int bx, int by, int ex, int ey)
{
if (bx == ex && by == ey)
return 0;
int step = 0;
queue<PII> qe;
bool vis[50][50] = {false};
// 层序遍历主逻辑
qe.push({bx, by});
vis[bx][by] = true;
while (qe.size())
{
step++;
int size = qe.size();
while (size--)
{
auto [a, b] = qe.front();
qe.pop();
for (int i = 0; i < 4; i++)
{
int x = dx[i] + a, y = dy[i] + b;
if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && forest[x][y] != 0)
{
if (x == ex && y == ey)
return step;
vis[x][y] = true;
qe.push({x, y});
}
}
}
}
return -1;
}
};三BFS解决多源最短路径问题
1 01矩阵
oj链接：01 矩阵
解法：BFS + 正难则反
如果从1作为起点走到终点0，那等到终点时记录距离时就不知道是从哪一个1为起点的
所以我们从0为起点开始，走到不是0的位置就进行距离记录，同时把它
class Solution
{
public:
// bool vis[1000][1000];//开10000会溢出?
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int m, n;
vector<vector<int>> updateMatrix(vector<vector<int>> &mat)
{
m = mat.size(), n = mat[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (mat[i][j] == 0)
{
dist[i][j] = 0;
q.push({i, j});
}
}
}
// 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 = dx[i] + a, y = dy[i] + b;
// if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y])
if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
// dist[x][y]=cnt;
// vis[x][y]=true;
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
}
}
// }
}
return dist;
}
};2飞地的数量
oj链接：飞地的数量
解法：dfs + 正难则反
a先把边界上的1进入队列并进行标记；
b进行dfs遍历(上下左右找合法坐标)只要它是1并且没被标记，就把它加入到队列中并进行标记；
c再次对grid进行遍历，只要坐标的值是1并且没别标记就代表它走不出边界，进行统计即可
class Solution
{
public:
bool vis[500][500];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int m, n;
int numEnclaves(vector<vector<int>> &grid)
{
m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
// 边上1统计
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
{
if (grid[i][j] == 1)
{
q.push({i, j});
vis[i][j] = true;
}
}
}
}
// bfs进行遍历
while (q.size())
{
// int sz=q.size();
// while(sz--)
// {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = dx[k] + a, y = dy[k] + b;
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
{
q.push({x, y});
vis[x][y] = true;
}
}
// }
}
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (!vis[i][j] && grid[i][j] == 1)
ret++;
}
}
return ret;
}
};3地图中的最高点
oj链接：地图中的最高点
解法：bfs
安排高度时，任意相邻的格子高度差至多为1，也就是既可以设计成0，也可以设计成1；
但题目要我们返回的是高度值最大的情况，所以我们贪心地把所有高度差都设计成1即可；
也就是从所有水域位置为起点来来依次bfs遍历即可完成任务~
class Solution {
public:
typedef pair<int,int> PII;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
{
queue<PII> qe;
int n=isWater.size(),m=isWater[0].size();
vector<vector<int>> hight(n,vector<int>(m,-1));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(isWater[i][j]==1)
{
qe.push({i,j});
hight[i][j]=0;
}
}
}
while(qe.size())
{
int sz=qe.size();
while(sz--)
{
auto[a,b]=qe.front();
qe.pop();
for(int i=0;i<4;i++)
{
int x=dx[i]+a,y=dy[i]+b;
if(x>=0&&x<n&&y>=0&&y<m&&hight[x][y]==-1)
{
hight[x][y]=hight[a][b]+1;
qe.push({x,y});
}
}
}
}
return hight;
}
};4地图分析
oj链接：地图分析
与01矩阵的思路一样~
//用dist数组
class Solution
{
public:
typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int maxDistance(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<PII> qe;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == 1)
{
qe.push({i, j});
dist[i][j] = 0;
}
}
}
if (qe.size() == 0 || qe.size() == n * m)
return -1; // 边界情况
int ans = 0;
while (qe.size())
{
auto [a, b] = qe.front();
qe.pop();
for (int i = 0; i < 4; i++)
{
int x = dx[i] + a, y = dy[i] + b;
if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
qe.push({x, y});
ans = max(ans, dist[x][y]);
}
}
}
return ans;
}
};
//统计遍历层数
class Solution
{
public:
bool vis[100][100];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int m, n, ret = -1;
int maxDistance(vector<vector<int>> &grid)
{
m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1)
{
q.push({i, j});
vis[i][j] = true;
}
}
}
if (q.size() == 0 || q.size() == m * n)
return ret;
while (q.size())
{
ret++;
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 && !vis[x][y])
{
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return ret;
}
};四BFS解决拓扑排序
0拓扑排序简介
1课程表
oj链接：课程表
此题是拓扑排序的应用：判断有向图中是否有环
1 建图
根据数据量的稠密来选择用邻接矩阵还是邻接表（此题选择它）
2 代码如何建邻接表？
灵活使用STL中的容器：vector/hash 来储存每个点的边（出度）
再用vector来储存每个点的入度情况
3进行拓扑排序
来一次BFS遍历即可！
class Solution
{
public:
bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
{
// vector建图
vector<vector<int>> edge(numCourses);
vector<int> in(numCourses);
for (auto &p : prerequisites)
{
int a = p[0], b = p[1]; // b->a
edge[b].push_back(a);
in[a]++;
}
queue<int> q;
// 入度为0存队列
for (int i = 0; i < numCourses; i++)
{
if (in[i] == 0)
q.push(i);
}
// BFS拓扑排序
while (q.size())
{
int e = q.front();
q.pop();
// 该点指向的点的入度--
for (auto &i : edge[e])
{
in[i]--;
// 入度为0加队列
if (in[i] == 0)
q.push(i);
}
}
// 点对应的入度情况是否全为0
for (auto &a : in)
{
if (a != 0)
return false;
}
return true;
}
};2课程表Ⅱ
oj链接：课程表 II
与上题思路类似
class Solution
{
public:
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
{
// hash建图
unordered_map<int, vector<int>> edge;
vector<int> in(numCourses);
for (auto &p : prerequisites)
{
int a = p[0], b = p[1]; // b->a
edge[b].push_back(a);
in[a]++;
}
queue<int> q;
// 入度为0存队列
for (int i = 0; i < numCourses; i++)
{
if (in[i] == 0)
q.push(i);
}
// BFS拓扑排序
vector<int> ret;
while (q.size())
{
int e = q.front();
q.pop();
ret.push_back(e);
// 该点指向的点的入度--
for (auto &i : edge[e])
{
in[i]--;
// 入度为0加队列
if (in[i] == 0)
q.push(i);
}
}
// 是否是有环图
for (auto &i : in)
{
if (i != 0)
return {};
}
return ret;
}
};3火星词典
oj链接：火星词典
注意这种情况：
细节：
如果是words = {"ab","abc"}：则有合法顺序返回（此时abc随便一种顺序返回）
如果是words = {"abc","ab"}：这种情况是不合法的(s.length > t.length)，返回“”
class Solution
{
public:
// 用unordered_set去重方便
unordered_map<char, unordered_set<char>> edges;
// 用unordered_map统计方便
unordered_map<char, int> in;
// 标记非法情况
bool check = false;
void Add(string &s1, string &s2)
{
int n = min(s1.size(), s2.size());
int i = 0;
while (i < n && s1[i] == s2[i])
i++;
if ((i == s2.size() && i < s1.size()))
check = true; // 解决这种{"abc","ab"}非法情况
else if (i < s2.size() && i < s1.size())
{
char a = s1[i], b = s2[i]; // a->b
if (!edges[a].count(b))
{
edges[a].insert(b);
in[b]++;
}
}
}
string alienOrder(vector<string> &words)
{
int m = words.size();
// 先进行初始化(后面入度为0才能统计)
for (auto &s : words)
for (auto &ch : s)
in[ch] = 0;
for (int i = 0; i < m; i++)
{
for (int j = i + 1; j < m; j++)
{
Add(words[i], words[j]);
if (check)
return "";
}
}
// 拓扑排序
queue<char> q;
string ret;
for (auto &[ch, cnt] : in)
{
if (cnt == 0)
q.push(ch);
}
while (q.size())
{
char ch = q.front();
q.pop();
ret += ch;
for (auto &s : edges[ch])
{
in[s]--;
if (in[s] == 0)
q.push(s);
}
}
for (auto &[ch, cnt] : in)
{
if (cnt != 0)
return "";
}
return ret;
}
};以上便是全部内容，有问题欢迎在评论区指出，感谢观看！
