精华内容
下载资源
问答
  • floodfill

    2021-03-15 22:07:47
    floodfill 1. floodfill原理 原理 洪水灌溉算法,基本问题是:有一个池塘,池塘内有几块陆地,找出这几块陆地。 可以通过宽搜或者深搜实现,最常用的是宽搜。 深搜可能会出现爆栈的风险。 可能出现的问题:(1...

    floodfill

    1. floodfill原理

    原理

    • 洪水灌溉算法,基本问题是:有一个池塘,池塘内有几块陆地,找出这几块陆地。

    在这里插入图片描述

    • 可以通过宽搜或者深搜实现,最常用的是宽搜。
    • 深搜可能会出现爆栈的风险。
    • 可能出现的问题:(1)找出陆地的个数;(2)计算陆地的面积;(3)计算陆地的周长; 等

    代码模板

    // BFS
    #include <iostream>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1010, M = N * N;
    
    int n, m;
    char g[N][N];  // 存储地图
    PII q[M];
    bool st[N][N];  // 判重数组
    
    void bfs(int sx, int sy) {
        
        int hh = 0, tt = 0;
        q[0] = {sx, sy};
        st[sx][sy] = true;
        
        while (hh <= tt) {
            auto t = q[hh++];
            for (int i = t.x - 1; i <= t.x + 1; i++)
                for (int j = t.y - 1; j <= t.y + 1; j++) {
                    if (i == t.x && j == t.y) continue;
                    if (i < 0 || i >= n || j < 0 || j >= m) continue;
                    if (g[i][j] == '.' || st[i][j]) continue;
                    
                    q[++tt] = {i, j};
                    st[i][j] = true;
                }
        }
    }
    
    int main() {
        
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%s", g[i]);
        
        int cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 'W' && !st[i][j]) {
                    bfs(i, j);
                    cnt++;
                }
        
        printf("%d\n", cnt);
        
        return 0;
    }
    
    // DFS
    #include <iostream>
    
    #define x first
    #define y second
    
    using namespace std;
    
    const int N = 1010;
    
    int n, m;
    char g[N][N];  // 存储地图
    bool st[N][N];  // 判重数组
    
    void dfs(int sx, int sy) {
        
        st[sx][sy] = true;
        for (int i = sx - 1; i <= sx + 1; i++)
            for (int j = sy - 1; j <= sy + 1; j++) {
                if (i >= 0 && i < n && j >= 0 && j < m && g[i][j] == 'W' && !st[i][j])
                    dfs(i, j);
            }
    }
    
    int main() {
        
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%s", g[i]);
        
        int cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 'W' && !st[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
        
        printf("%d\n", cnt);
        
        return 0;
    }
    

    2. AcWing上的floodfill题目

    AcWing 1098. 城堡问题

    问题描述

    分析

    • 对于某一个方向是否有墙的判断:可以用二进制判断,左上右下分别用0、1、2、3代表,则可以使用g[x][y] >> i & 1判断(这里的i就是刚才的0、1、2、3)。其他直接使用floodfill算法求解即可。

    代码

    • C++
    // BFS
    #include <iostream>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 55, M = N * N;
    
    int n, m;
    int g[N][N];
    PII q[M];
    bool st[N][N];
    
    int bfs(int sx, int sy) {
        
        int hh = 0, tt = 0;
        int area = 0;
        
        int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};  // 左上右下
        
        q[0] = {sx, sy};
        st[sx][sy] = true;
        
        while (hh <= tt) {
            auto t = q[hh++];
            area++;
            
            for (int i = 0; i < 4; i++) {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                if (st[a][b]) continue;
                if (g[t.x][t.y] >> i & 1) continue;
                
                q[++tt] = {a, b};
                st[a][b] = true;
            }
        }
    }
    
    int main() {
        
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> g[i][j];
        
        int cnt = 0, area = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (!st[i][j]) {
                    area = max(area, bfs(i, j));
                    cnt++;
                }
        
        cout << cnt << endl;
        cout << area << endl;
        
        return 0;
    }
    
    // DFS
    #include <iostream>
    
    #define x first
    #define y second
    
    using namespace std;
    
    const int N = 55;
    
    int n, m;
    int g[N][N];
    bool st[N][N];
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};  // 上右下左
    
    int dfs(int sx, int sy) {
        
        st[sx][sy] = true;
        int area = 1;
        for (int i = 0; i < 4; i++) {
            int a = sx + dx[i], b = sy + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && !(g[sx][sy] >> i & 1) && !st[a][b])
                area += dfs(a, b);
        }
        return area;
    }
    
    int main() {
        
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> g[i][j];
        
        int cnt = 0, area = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (!st[i][j]) {
                    area = max(area, dfs(i, j));
                    cnt++;
                }
        
        cout << cnt << endl;
        cout << area << endl;
        
        return 0;
    }
    

    AcWing 1106. 山峰和山谷

    问题描述

    分析

    • floodfill的同时记录每个连通块周围是否有高于或者低于当前连通块的山峰,根据这个就可以判断山峰山谷的个数。

    代码

    • C++
    // BFS
    #include <iostream>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1010, M = N * N;
    
    int n;
    int h[N][N];
    PII q[M];
    bool st[N][N];
    
    void bfs(int sx, int sy, int &has_higher, int &has_lower) {
        
        int hh = 0, tt = 0;
        q[0] = {sx, sy};
        st[sx][sy] = true;
        
        while (hh <= tt) {
            PII t = q[hh++];
            
            for (int i = t.x - 1; i <= t.x + 1; i++)
                for (int j = t.y - 1; j <= t.y + 1; j++) {
                    if (i == t.x && j == t.y) continue;
                    if (i < 0 || i >= n || j < 0 || j >= n) continue;
                    if (h[t.x][t.y] != h[i][j]) {
                        if (h[i][j] > h[t.x][t.y]) has_higher = true;
                        else has_lower = true;
                    } else if (!st[i][j]) {
                        q[++tt] = {i, j};
                        st[i][j] = true;
                    }
                }
        }
    }
    
    int main() {
        
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &h[i][j]);
        
        int peak = 0, valley = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j< n; j++)
                if (!st[i][j]) {
                    int has_higher = false, has_lower = false;
                    bfs(i, j, has_higher, has_lower);
                    if (!has_higher) peak++;
                    if (!has_lower) valley++;
                }
        
        printf("%d %d\n", peak, valley);
        
        return 0;
    }
    
    // DFS
    // 没有通过,原因:Memory Limit Exceeded
    #include <iostream>
    
    #define x first
    #define y second
    
    using namespace std;
    
    const int N = 1010;
    
    int n;
    int h[N][N];
    bool st[N][N];
    
    void dfs(int sx, int sy, int &has_higher, int &has_lower) {
        
        st[sx][sy] = true;
        for (int i = sx - 1; i <= sx + 1; i++)
            for (int j = sy - 1; j <= sy + 1; j++) 
                if (i >= 0 && i < n && j >= 0 && j < n) {
                    if (h[i][j] != h[sx][sy]) {
                        if (h[i][j] > h[sx][sy]) has_higher = true;
                        else has_lower = true;
                    } else if (!st[i][j]) {
                        dfs(i, j, has_higher, has_lower);
                    }
                }
    }
    
    int main() {
        
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &h[i][j]);
        
        int peak = 0, valley = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j< n; j++)
                if (!st[i][j]) {
                    int has_higher = false, has_lower = false;
                    dfs(i, j, has_higher, has_lower);
                    if (!has_higher) peak++;
                    if (!has_lower) valley++;
                }
        
        printf("%d %d\n", peak, valley);
        
        return 0;
    }
    

    AcWing 1113 红与黑

    问题描述

    分析

    • 找到你所在的位置,执行一遍floodfill算法即可。

    代码

    • C++
    // BFS
    #include <iostream>
    #include <queue>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    const int N = 25;
    
    int n, m;  // 行数,列数
    char g[N][N];
    
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    
    int bfs(int sx, int sy) {
    
        queue<PII> q;
        q.push({sx, sy});
        g[sx][sy] = '#';
        int res = 0;
    
        while (q.size()) {
            auto t = q.front();
            q.pop();
            res++;
            for (int i = 0; i < 4; i++) {
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
                g[x][y] = '#';
                q.push({x, y});
            }
        }
        return res;
    }
    
    int main() {
    
        while (cin >> m >> n, n || m) {
            for (int i = 0; i < n; i++) cin >> g[i];
            int x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++)
                    if (g[i][j] == '@') {
                        x = i, y = j;
                        break;
                    }
            }
            cout << bfs(x, y) << endl;
        }
    }
    
    
    // DFS
    #include <iostream>
    
    using namespace std;
    
    const int N = 25;
    
    int n, m;  // 行数,列数
    char g[N][N];
    
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    
    int dfs(int x, int y) {
    
        int res = 1;
        g[x][y] = '#';
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
                res += dfs(a, b);
        }
    
        return res;
    }
    
    int main() {
    
        while (cin >> m >> n, n || m) {
            for (int i = 0; i < n; i++) cin >> g[i];
            int x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++)
                    if (g[i][j] == '@') {
                        x = i, y = j;
                        break;
                    }
            }
            cout << dfs(x, y) << endl;
        }
    }
    
    

    3. 力扣上的floodfill题目

    Leetcode 0200 岛屿数量

    问题描述

    分析

    • 直接使用floodfill算法即可,BFS或者DFS均可

    代码

    • C++
    /**
     * 执行用时:16 ms, 在所有 C++ 提交中击败了98.27%的用户
     * 内存消耗:9.4 MB, 在所有 C++ 提交中击败了93.39%的用户
     */
    class Solution {
    public:
    
        vector<vector<char>> g;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
        int numIslands(vector<vector<char>> &grid) {
    
            g = grid;
            int cnt = 0;
            for (int i = 0; i < g.size(); i++) {
                for (int j = 0; j < g[0].size(); j++)
                    if (g[i][j] == '1') {
                        dfs(i, j);
                        cnt++;
                    }
            }
            return cnt;
        }
    
        void dfs(int x, int y) {
            g[x][y] = '0';
            for (int i = 0; i < 4; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < g.size() && b >= 0 && b < g[0].size() && g[a][b] == '1')
                    dfs(a, b);
            }
        }
    };
    
    • Java
    /**
     * Date: 2020/9/3 16:21
     * Content: 经典的 floodfill 算法
     * 执行用时:2 ms, 在所有 Java 提交中击败了92.58%的用户
     * 内存消耗:40.7 MB, 在所有 Java 提交中击败了84.35%的用户
     */
    class Solution {
    
        int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  // 上右下左
        int n, m;  // 行数,列数
        char[][] g;
        boolean[][] st;
    
        // 从grid[x][y]的位置开始(该位置要求为'1',即陆地),进行 floodfill
        private void dfs(int x, int y) {
            st[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int a = x + d[i][0], b = y + d[i][1];
                if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && g[a][b] == '1')
                    dfs(a, b);
            }
        }
    
        public int numIslands(char[][] grid) {
    
            g = grid;
            n = g.length;
            if (n == 0) return 0;
            m = g[0].length;
            st = new boolean[n][m];
    
            int res = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (grid[i][j] == '1' && !st[i][j]) {
                        res++;
                        dfs(i, j);
                    }
            return res;
        }
    }
    

    Leetcode 0463 岛屿的长度

    问题描述

    分析

    • 如果从陆地开始遍历,出界或者遍历到水,都说明是边界,结果加一

    代码

    • C++
    /**
     * 执行用时:164 ms, 在所有 C++ 提交中击败了44.11%的用户
     * 内存消耗:93.7 MB, 在所有 C++ 提交中击败了59.12%的用户
     */
    class Solution {
    public:
        int islandPerimeter(vector<vector<int>> &grid) {
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            int res = 0;
            for (int i = 0; i < grid.size(); i++)
                for (int j = 0; j < grid[i].size(); j++)
                    if (grid[i][j] == 1) {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dx[k], y = j + dy[k];
                            if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) res++;
                            else if (grid[x][y] == 0) res++;
                        }
                    }
            return res;
        }
    };
    
    • Java
    /**
     * Date: 2020/10/30 10:07
     * Content: Floodfill
     * 执行用时:11 ms, 在所有 Java 提交中击败了32.41%的用户
     * 内存消耗:39.4 MB, 在所有 Java 提交中击败了88.92%的用户
     */
    public class Solution {
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};  // 上右下左
    
        public int islandPerimeter(int[][] grid) {
    
            int res = 0;
            for (int i = 0; i < grid.length; i++)
                for (int j = 0; j < grid[0].length; j++)
                    if (grid[i][j] == 1)
                        for (int k = 0; k < 4; k++) {
                            int a = i + dx[k], b = j + dy[k];
                            if (a < 0 || a >= grid.length || b < 0 || b >= grid[0].length) res++;
                            else if (grid[a][b] == 0) res++;
                        }
            return res;
        }
    }
    

    LeetCode 0695 岛屿的最大面积

    问题描述

    分析

    • 直接使用floodfill算法即可,BFS或者DFS均可

    代码

    • C++
    /**
     * 执行用时:36 ms, 在所有 C++ 提交中击败了21.34%的用户
     * 内存消耗:26.3 MB, 在所有 C++ 提交中击败了9.78%的用户
     */
    class Solution {
    public:
        typedef pair<int, int> PII;
        int n, m;
        vector<vector<int>> g;
        vector<vector<bool>> st;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
        int maxAreaOfIsland(vector<vector<int>> &grid) {
    
            g = grid;
            n = g.size();
            if (n == 0) return 0;
            m = g[0].size();
            if (m == 0) return 0;
            st = vector<vector<bool>>(n, vector<bool>(m, false));
    
            int res = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (!st[i][j] && g[i][j] == 1)
                        res = max(res, bfs(i, j));
            return res;
        }
    
        int bfs(int sx, int sy) {
    
            queue<PII> q;
            q.push({sx, sy});
            st[sx][sy] = true;
    
            int area = 0;
            while (q.size()) {
                auto t = q.front(); q.pop();
                area++;
                for (int i = 0; i < 4; i++) {
                    int a = t.first + dx[i], b = t.second + dy[i];
                    if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 1 && !st[a][b]) {
                        q.push({a, b});
                        st[a][b] = true;
                    }
                }
            }
            return area;
        }
    };
    
    • Java
    /**
     * 执行用时:5 ms, 在所有 Java 提交中击败了18.82%的用户
     * 内存消耗:38.4 MB, 在所有 Java 提交中击败了99.62%的用户
     */
    public class Solution {
    
        private int n, m;
        private int[][] g;
        private final int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  // 上右下左
        private boolean[][] st;  // 记录节点是否访问过
    
        public int maxAreaOfIsland(int[][] grid) {
    
            n = grid.length;
            if (n == 0) return 0;
            m = grid[0].length;
            if (m == 0) return 0;
    
            this.g = grid;
            st = new boolean[n][m];  // 默认为false
    
            int res = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (!st[i][j] && grid[i][j] == 1)
                        res = Math.max(res, dfs(i, j));
    
            return res;
        }
    
        // 返回某个陆地大小
        private int dfs(int sx, int sy) {
            st[sx][sy] = true;
            int res = 1;
            for (int i = 0; i < 4; i++) {
                int a = sx + d[i][0], b = sy + d[i][1];
                if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && g[a][b] == 1)
                    res += dfs(a, b);
            }
            return res;
        }
    }
    
    展开全文
  • FloodFill

    2021-05-18 08:41:56
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) { /*1 1 1 2 2 2 1 1 0 ----> 2 2 0 1 0 1 2 0 1 思路还是深度优先搜索 找和原来位置相同的数一直找下去一篇 替换成新的数 .

    在这里插入图片描述

    class Solution {
        public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    
            /*1 1 1           2   2   2
              1 1 0   ---->   2   2   0  
              1 0 1           2   0   1
              思路还是深度优先搜索  找和原来位置相同的数一直找下去一篇 替换成新的数
            */
    
            if(image == null || image[0].length == 0 ) return image;
    
            //定义搜索的四个方向
            int dx[]={-1,0,1,0};//上左下右的顺序
            int dy[]={0,-1,0,1};
            if(image[sr][sc] == newColor) return image;//防止那种死循环
            int oldColor = image[sr][sc];
            image[sr][sc] = newColor;
            for(int i = 0 ; i<4 ;i++){//然后四个方向搜索
                int x = sr+dx[i];
                int y = sc+dy[i];
                if(x >= 0 && x< image.length && y>=0&& y< image[0].length && image[x][y]==oldColor){
                    floodFill(image,x,y,newColor);
                }
            }
            return image;
        }
    }
    
    展开全文
  • floodfill算法

    千次阅读 2019-10-10 08:08:09
    floodfill算法

    200. 岛屿数量

     https://leetcode-cn.com/problems/number-of-islands/

     

     

    以(0, 0)这个点出发,每一个点的访问顺序为

    //四个方向(顺序不重要)
    //上 右 下 左
    int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

     

    /// 200. Number of Islands
    /// https://leetcode.com/problems/number-of-islands/description/
    /// 时间复杂度: O(n*m)
    /// 空间复杂度: O(n*m)
    class Solution {
        private int d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //行
        private int m;
        //列
        private int n;
        private boolean visited[][];
    
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            m = grid.length;
            n = grid[0].length;
            visited = new boolean[m][n];
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && !visited[i][j]) {
                        dfs(grid, i, j);
                        res++;
                    }
                }
            }
            return res;
        }
        // 从grid[x][y]的位置开始,进行floodfill
        // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
        private void dfs(char[][] grid, int x, int y) {
    
            //assert(inArea(x,y));
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int newx = x + d[i][0];
                int newy = y + d[i][1];
                if (inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1') {
                    dfs(grid, newx, newy);
                }
            }
        }
        /**
         * 判断是否越界
         * @param x m
         * @param y n
         */
        private boolean inArea(int x, int y) {
            return x >= 0 && x < m && y >= 0 && y < n;
        }
    
        //public static void main(String[] args) {
        //    char grid1[][] = {
        //            {'1','1','1','1','0'},
        //            {'1','1','0','1','0'},
        //            {'1','1','0','0','0'},
        //            {'0','0','0','0','0'}
        //    };
        //    System.out.println((new Solution()).numIslands(grid1));
        //    // 1
        //    // ---
        //    char grid2[][] = {
        //            {'1','1','0','0','0'},
        //            {'1','1','0','0','0'},
        //            {'0','0','1','0','0'},
        //            {'0','0','0','1','1'}
        //    };
        //    System.out.println((new Solution()).numIslands(grid2));
        //    // 3
        //}
    }

    Oil Deposits

     https://blog.csdn.net/qq_40794973/article/details/83788155


    130. 被围绕的区域 

     https://leetcode-cn.com/problems/surrounded-regions/

    class Solution {
        private int des[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //行
        private int m;
        //列
        private int n;
        public void solve(char[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0) {
                return;
            }
            m = board.length;
            n = board[0].length;
          
            //1.和四边有关系的都涂上6
            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) {
                        //System.out.println(i + " " + j);
                        if (board[i][j] == 'O') {
                            dfs(board, i, j, '6');
                        }
                    }
                }
            }
            //2.o涂成X即可
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        dfs(board, i, j, 'X');
                    }
                }
            }
            //3.把6涂回来
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == '6') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
        
        private void dfs(char[][] grid, int x, int y, char filChar) {
            grid[x][y] = filChar;
            for (int i = 0; i < 4; i++) {
                int newx = x + des[i][0];
                int newy = y + des[i][1];
                if (areYouOk(newx, newy) && grid[newx][newy] == 'O') {
                    dfs(grid, newx, newy, filChar);
                }
            }
        }
        
        /**
         * 判断是否越界
         * @param x m
         * @param y n
         */
        private boolean areYouOk(int x, int y) {
            return x >= 0 && x < m && y >= 0 && y < n;
        }
    }

    417. 太平洋大西洋水流问题 

    https://leetcode-cn.com/problems/pacific-atlantic-water-flow/

     

     

     从两边往中间走,从低到高走,标记两个数组,最后按照条件添加

    /**
     * 从四周开始,标记
     * 从下往上走
     */
    class Solution {
        private int des[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //行
        private int m;
        //列
        private int n;
    
        public List<List<Integer>> pacificAtlantic(int[][] matrix) {
            List<List<Integer>> res = new ArrayList<>();
            if (matrix == null || matrix.length <= 0) {
                return res;
            }
            m = matrix.length;
            n = matrix[0].length;
            boolean[][] taiPinArr = new boolean[150][150];
            boolean[][] daXiArr = new boolean[150][150];
            //第一行 和最后一行
            for (int j = 0; j < n; j++) {
                //System.out.println("0"+" "+ j);
                //System.out.println(m - 1+" "+ j);
                dfs(0, j, matrix, taiPinArr);
                dfs(m - 1, j, matrix, daXiArr);
            }
            //第一列 和最后一列
            for (int i = 0; i < m; i++) {
                //System.out.println(i + " " + "0");
                //System.out.println(i + " " + (n - 1));
                dfs(i, 0, matrix, taiPinArr);
                dfs(i, n - 1, matrix, daXiArr);
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    //两个数组都标记了
                    if (taiPinArr[i][j] && daXiArr[i][j]) {
                        //System.out.println("[" + i + ", " + j + "]");
                        List<Integer> lis = new ArrayList<>();
                        lis.add(i);
                        lis.add(j);
                        res.add(lis);
                    }
                }
            }
            return res;
        }
        /**
         * @param x       行坐标
         * @param y       列坐标
         * @param matrix  大陆矩阵
         * @param visited 标记数组
         */
        private void dfs(int x, int y, int[][] matrix, boolean[][] visited) {
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int desX = x + des[i][0];
                int desY = y + des[i][1];
                //这点没越界 这点没标记 这点高度要大于等于上一个点(往上走)
                if (areYouOk(desX, desY) && !visited[desX][desY] && matrix[desX][desY] >= matrix[x][y]) {
                    dfs(desX, desY, matrix, visited);
                }
            }
    
        }
        /**
         * 判断是否越界
         * @param x 行坐标
         * @param y 列坐标
         */
        private boolean areYouOk(int x, int y) {
            return x >= 0 && x < m && y >= 0 && y < n;
        }
        //public static void main(String[] args) {
        //    int arr[][] = {
        //            {1, 2, 2, 3, 5},
        //            {3, 2, 3, 4, 4},
        //            {2, 4, 5, 3, 1},
        //            {6, 7, 1, 4, 5},
        //            {5, 1, 1, 2, 4}
        //    };
        //    new Solution().pacificAtlantic(arr);
        //    // System.out.println(new Solution().isTaiPin(4, 5));
        //}
    }

     

    展开全文
  • cvFloodFill

    2012-10-26 12:59:04
    opencv中cvFloodFill函数的用法,实现图像填充的效果
  • floodfill分割

    2018-06-13 23:14:13
    floodfill分割 floodfill泛洪填充算法是在很多图形绘制软件中常用的填充算法,通常来说是自动选中与种子像素相关的区域,利用指定的颜色区域颜色替换,可用于标记或分离图像的某部分。windows的图像编辑软件中的...

    floodfill分割

    floodfill泛洪填充算法是在很多图形绘制软件中常用的填充算法,通常来说是自动选中与种子像素相关的区域,利用指定的颜色区域颜色替换,可用于标记或分离图像的某部分。windows的图像编辑软件中的油漆桶这一功能,以及类似photoshop的魔术棒选择工具,都是通过floodfill泛洪填充来改进和延伸的。
    示例代码如下:

    #include "opencv2/imgproc/imgproc.hpp"
    #include "opencv2/highgui/highgui.hpp"
    #include <iostream>
    using namespace cv;
    using namespace std;
    // 初识化参数
    Mat image, gray, mask;
    int ffillMode = 1;
    int loDiff = 20, upDiff = 20;
    int connectivity = 4;
    int isColor = true;
    bool useMask = false;
    int newMaskVal = 255;
    // 鼠标响应函数
    static void onMouse(int event, int x, int y, int, void*)//鼠标回调函数
    {
        if (event != CV_EVENT_LBUTTONDOWN)
            return;
        // floodfill参数设置
        Point seed = Point(x, y);
        int lo = ffillMode == 0 ? 0 : loDiff;
        int up = ffillMode == 0 ? 0 : upDiff;
        int flags = connectivity + (newMaskVal << 8) +
            (ffillMode == 1 ? CV_FLOODFILL_FIXED_RANGE : 0);
        // 颜色分量随机选取
        int b = (unsigned)theRNG() & 255;
        int g = (unsigned)theRNG() & 255;
        int r = (unsigned)theRNG() & 255;
        Rect ccomp;
        // 颜色选择
        Scalar newVal = isColor ? Scalar(b, g, r)
            : Scalar(r*0.299 + g*0.587 + b*0.114);//判断使用彩色还是灰度值
        Mat dst = isColor ? image : gray;
        int area;
        // 根据标志位选择泛洪填充
        if (useMask)//判断是使用掩码还是非掩码操作
        {
            // 阈值化操作
            threshold(mask, mask, 1, 128, CV_THRESH_BINARY);
            area = floodFill(dst, mask, seed, 
                newVal, &ccomp, Scalar(lo, lo, lo),
                Scalar(up, up, up), flags);
            imshow("mask", mask);
        }
        else
        {
            // 泛洪填充
            area = floodFill(dst, seed, newVal, &ccomp,
                Scalar(lo, lo, lo),
                Scalar(up, up, up), flags);
        }
        imshow("image", dst);
    }
    int main()
    {
        cv::Mat srcImage = cv::imread("..\\images\\sea.jpg");
        if (srcImage.empty())
            return 0;
        srcImage.copyTo(image);
        cvtColor(srcImage, gray, CV_BGR2GRAY);
        mask.create(srcImage.rows + 2, srcImage.cols + 2, CV_8UC1);
        // 鼠标响应回调函数
        namedWindow("image", 0);
        setMouseCallback("image", onMouse, 0);
        for (;;)
        {
            imshow("image", isColor ? image : gray);
            int c = waitKey(0);
            if ((c & 255) == 27)
            {
                cout << "Exiting ...\n";
                break;
            }
            if (c == 'r')//清除操作
            {
                cout << "Original image is restored\n";
                srcImage.copyTo(image);
                cvtColor(image, gray, CV_BGR2GRAY);
                mask = Scalar::all(0);
            }
        }
        return 0;
    }
    
    展开全文
  • FloodFill 算法

    2018-01-07 22:03:01
    你需要输出经过 FloodFill 算法染色后的节点,要求将每个节点按染色结果分类。其中,和之前学习的一样,输入的节点从编号为 00 开始,染色的结果由 11 开始递增。 输入格式 输入的第一行为两个整数 nn 和...
  • floodFill函数

    千次阅读 2015-08-25 09:54:46
    floodFill函数 函数作用: 用指定颜色填充一个连接域 void cvFloodFill( CvArr* image, CvPoint seed_point, CvScalar new_val, CvScalar lo_diff=cvScalarAll(0), CvScalar up_diff=cvScalarAll(0),
  • matlab开发-FloodFill3D

    2019-08-27 08:14:24
    matlab开发-FloodFill3D。该程序在二进制矩阵中填充三维区域。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,874
精华内容 2,349
关键字:

floodFill