做食品生产的网站,网站评估 源码,用 php网站建设打出一首古诗,岳阳建设局网站目录
一BFS解决FloodFill算法
1图像渲染
2岛屿数量
3岛屿的最大面积
4被环绕的区域
二BFS解决蛋源最短路径问题
1迷宫中离入口最近的出口
2最小基因变化
3单词接龙
4为高尔夫比赛砍树
三BFS解决多源最短路径问题
1 01矩阵
2飞地的数量 3地图中的最高点
4地图分…目录
一BFS解决FloodFill算法
1图像渲染
2岛屿数量
3岛屿的最大面积
4被环绕的区域
二BFS解决蛋源最短路径问题
1迷宫中离入口最近的出口
2最小基因变化
3单词接龙
4为高尔夫比赛砍树
三BFS解决多源最短路径问题
1 01矩阵
2飞地的数量 3地图中的最高点
4地图分析 一BFS解决FloodFill算法
floodfill算法中文名洪水灌溉这类问题都是要来找出性质相同的联通块解决好一道后后面遇到类型的题目代码也是类似的
1图像渲染
oj链接图像渲染 解法bfs 1.先把开始的坐标{srsc}放进队列中 2.取出队头坐标{xy}直接将它改成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(vectorvectorint 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);}}}vectorvectorint floodFill(vectorvectorint 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:vectorvectorint floodFill(vectorvectorint 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主逻辑queuepairint, 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(vectorvectorchar 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(vectorvectorchar 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;queuepairint, int q;void bfs(vectorvectorchar 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(vectorvectorchar 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;queuepairint, int q;void bfs(vectorvectorint 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(vectorvectorint 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;queuepairint, int q;void bfs(vectorvectorchar 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(vectorvectorchar 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(vectorvectorchar maze, vectorint entrance){m maze.size(), n maze[0].size();queuepairint, 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, vectorstring bank){char arr[4] {A, G, C, T};unordered_mapstring, bool vis;for (auto s : bank)vis[s] false;if(!vis.count(endGene)) return -1;// 不存在直接返回queuestring 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, vectorstring wordList){string t qwertyuiopasdfghjklzxcvbnm;unordered_mapstring, bool vis;for (auto word : wordList)vis[word] false;if (!vis.count(endWord))return 0;int ans 1;queuestring 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 pairint, int PII;int n, m;int cutOffTree(vectorvectorint forest){// 先预处理砍树顺序vectorPII 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(vectorvectorint forest, int bx, int by, int ex, int ey){if (bx ex by ey)return 0;int step 0;queuePII 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;vectorvectorint updateMatrix(vectorvectorint mat){m mat.size(), n mat[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, 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 step0;while (q.size()){// step;// int szq.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(x0xmy0yn!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(vectorvectorint grid){m grid.size(), n grid[0].size();queuepairint, 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 szq.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 pairint,int PII;int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};vectorvectorint highestPeak(vectorvectorint isWater) {queuePII qe;int nisWater.size(),misWater[0].size();vectorvectorint hight(n,vectorint(m,-1));for(int i0;in;i){for(int j0;jm;j){if(isWater[i][j]1){qe.push({i,j});hight[i][j]0;}}}while(qe.size()){int szqe.size();while(sz--){auto[a,b]qe.front();qe.pop();for(int i0;i4;i){int xdx[i]a,ydy[i]b;if(x0xny0ymhight[x][y]-1){hight[x][y]hight[a][b]1;qe.push({x,y});}}}}return hight;}
};
4地图分析
oj链接地图分析 与01矩阵的思路一样~ //用dist数组
class Solution
{
public:typedef pairint, int PII;int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int maxDistance(vectorvectorint grid){int n grid.size(), m grid[0].size();vectorvectorint dist(n, vectorint(m, -1));queuePII 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(vectorvectorint grid){m grid.size(), n grid[0].size();queuepairint, 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;}
}; 以上便是全部内容有问题欢迎在评论区指出感谢观看
