图

图算法领域10大经典算法

图像渲染

示例 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，
因为它不是在上下左右四个方向上与初始点相连的像素点。

深度搜索+递归

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int initColor=image[sr][sc];    
           if(newColor == initColor)return image;//原来的颜色和渲染后的颜色竟然一样？！
        dfs(image ,sr,sc,newColor,initColor);
        return image;
    }
    private void dfs(int[][] image, int sr, int sc, int newColor,int initColor){
        image[sr][sc]=newColor;
        if(sr>0&& image[sr - 1][sc] == initColor)
            dfs(image ,sr-1,sc,newColor,initColor);
          if(sr<image.length-1&& image[sr + 1][sc] == initColor)
            dfs(image ,sr+1,sc,newColor,initColor);
          if(sc>0&& image[sr][sc-1] == initColor)
            dfs(image ,sr,sc-1,newColor,initColor);
          if(sc<image[0].length-1&& image[sr][sc+1] == initColor)
            dfs(image ,sr,sc+1,newColor,initColor);
    }
}

太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
输出坐标的顺序不重要
m 和 n 都小于150

这个题第一眼看到觉得是一个很简单DFS搜索题。
第一个想法肯定是对每一个点进行dfs，
看他是否能够走到太平洋或者大西洋。
显然这样，时间复杂度会很高。
我们可以对其优化，每一次得到一条路径后，
将路径上的所有点都记录下来，
这样可以减少很多次dfs的过程，但优化效果不明显。
这个题，我们采用倒推法的思路。
从大西洋、太平洋向内搜索，
每次找比当前节点高的或者相同的节点，
将这些节点设置为True。最终将大西洋中为True的，
太平洋中也为True的节点作为最终的答案。

class Solution {
public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(); //矩阵行数
        int n = matrix[0].size(); //矩阵列数
        vector<pair<int,int>> res; //最终结果
        vector<vector<bool>> pacific(m, vector<bool>(n, false)); //太平洋
        vector<vector<bool>> atlantic(m, vector<bool>(n, false)); //大西洋
        
        //遍历第一行，最底下一行
        for(int i=0;i<m;i++){ 
            dfs(matrix,pacific,i,0,matrix[i][0]);
            dfs(matrix,atlantic,i,n-1,matrix[i][n-1]);
        }
        
        //遍历第一列，最右边一列
        for(int i=0;i<n;i++){
            dfs(matrix,pacific,0,i,matrix[0][i]);
            dfs(matrix,atlantic,m-1,i,matrix[m-1][i]);
        }
        
        //将pacific与atlantic重合的部分 作为最终结果
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(atlantic[i][j] && pacific[i][j])
                    res.push_back(make_pair(i,j));
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& matrix,vector<vector<bool>> &visited,int x,int y,int val){
        //越界 被访问 或者 当前值小于上一个值的都直接返回
        if (x<0 || x>matrix.size()-1 || y<0 || y>matrix[0].size()-1 || visited[x][y] || matrix[x][y] < val) return;
        //将该坐标设置为访问过
        visited[x][y] = true;
        dfs(matrix,visited,x+1,y,matrix[x][y]);
        dfs(matrix,visited,x-1,y,matrix[x][y]);
        dfs(matrix,visited,x,y+1,matrix[x][y]);
        dfs(matrix,visited,x,y-1,matrix[x][y]);
    }
};