算法/BFS/DFS_bfs 上下左右 csdn

BFS/DFS常用于二维阵的遍历中，需要根据移动规则（上下左右）来找到所有满足条件且相邻的位置。

BFS:常借助队列实现

DFS:常递归实现。

1.733. 图像渲染

题目描述：

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例：

示例 1:
 
输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

解答描述：

该题是很典型的采用深度优先搜索或者广度优先搜索进行二维矩阵的遍历的题。

在这里采用的是结合队列的广度优先搜索BFS，先令起始点入队，并记录起始点的颜色,

1)如果起始点的颜色和新的颜色相同，则不用更新颜色，直接返回image即可

2)否则的话，遍历当前队头位置的上下左右位置，看是否在范围内且颜色和起始点位置相同，若符合要求，则入队并更新颜色。

3）当队列为空时，说明已经搜索完毕，返回更新后的image即可。

代码：

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int d_x[4]={0,0,1,-1};//用来上下左右移动
        int d_y[4]={1,-1,0,0};
        int rows=image.size();//二维矩阵的行列
        int cols=image[0].size();
        //BFS
        int cur_color=image[sr][sc];
        if(cur_color==newColor)//此时不需要更新颜色
        {
            return image;
        }
        queue<pair<int,int> > q;
        q.emplace(sr,sc);//起始点入队
        image[sr][sc]=newColor;
 
        while(!q.empty())
        {
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++)
            {
                int new_x=x+d_x[i];
                int new_y=y+d_y[i];
                if(new_x>=0 && new_x<rows && new_y>=0 && new_y<cols && image[new_x][new_y]==cur_color)
                {
                    q.emplace(new_x,new_y);
                    image[new_x][new_y]=newColor;
                }
            }
        }
        return image;
    }
};

2.695. 岛屿的最大面积

题目描述：

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例：

 

解答描述：

该题也是很典型的BFS/DFS的题，但是和上题不同的是，该题存在多个岛屿的情况，即存在符合要求的图不是连通的情况，所以需要在上一题BFS的基础上进行多次BFS，进行的次数就是连通图的个数。（遍历二维阵，每找到一个符合要求且未被访问的点，就以该点为起点进行一次BFS）.

代码：

class Solution {
public: 
 
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    int BFS(vector<vector<int> > &grid,int sr,int sc)
    {
        int rows=grid.size();
        int cols=grid[0].size();
        
        int d_x[4]={0,0,1,-1};
        int d_y[4]={1,-1,0,0};
 
        int island=0;
 
        queue<pair<int,int> > q;
        q.emplace(sr,sc);
        grid[sr][sc]=0;//访问过后就置0，表示下回不可再用
        island++;
 
        while(!q.empty())
        {
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++)
            {
                int new_x=x+d_x[i];
                int new_y=y+d_y[i];
                if(new_x>=0 && new_x<rows && new_y>=0 && new_y<cols && grid[new_x][new_y]==1 )
                {
                    island++;
                    q.emplace(new_x,new_y);
                    grid[new_x][new_y]=0;
                }
            }
        }  
        return island;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int rows=grid.size();
        int cols=grid[0].size();
        
        int max_island=0;
 
        //多个连通子图的BFS
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(grid[i][j]==1)
                {
                    int island=BFS(grid,i,j);
                    max_island=max(max_island,island);
                }
            }
        }
        return max_island;
    }
};