200. Number of Islands

╰半橙微兮° 2022-02-12 11:47 216阅读 0赞

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
    
    Example 1:
    
    Input:
    11110
    11010
    11000
    00000
    
    Output: 1
    Example 2:
    
    Input:
    11000
    11000
    00100
    00011
    
    Output: 3

本题是一个非常经典的深度优先搜索的题目（代码我都能背出来了）。代码如下：

int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
    
        public int numIslands(char[][] grid) {
            int ans = 0;
            for(int i = 0; i < grid.length; ++i) {
                for(int j = 0; j < grid[0].length; ++j) {
                    if(grid[i][j] == '1') {
                        ++ans;
                        grid[i][j] = '0';
                        dfs(i, j, grid);
                    }
                }
            }
            return ans;
        }
    
        private void dfs(int i, int j, char[][] grid) {
            for(int k = 0; k < 4; ++k) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(0 <= x && x < grid.length && 0 <= y && y < grid[0].length && grid[x][y] == '1') {
                    grid[x][y] = '0';
                    dfs(x, y, grid);
                }
            }
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 200. Number of Islands

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An

阳光穿透心脏的1/2处/ 2023年07月01日 10:56/ 0 赞/ 1 阅读

相关 leetcode 200. Number of Islands（岛屿的数量）

[https://leetcode.com/problems/number-of-islands/][https_leetcode.com_problems_number-of

小咪咪/ 2022年12月03日 09:17/ 0 赞/ 169 阅读

相关 leetcode 200. Number of Islands | 200. 岛屿数量（Java）

题目 [https://leetcode-cn.com/problems/number-of-islands/][https_leetcode-cn.com_proble

深碍√TFBOYSˉ_/ 2022年10月05日 05:46/ 0 赞/ 174 阅读

相关 LeetCode200—Number of Islands

LeetCode200—Number of Islands 原题 [https://leetcode.com/problems/number-of-islands/

﹏ヽ暗。殇╰゛Y/ 2022年09月21日 13:12/ 0 赞/ 138 阅读

相关 LeetCode－－200. Number of Islands

Problem： > Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number > of

缺乏、安全感/ 2022年08月20日 15:22/ 0 赞/ 154 阅读

相关 leetcode 200. Number of Islands

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An

不念不忘少年蓝@/ 2022年07月27日 14:57/ 0 赞/ 167 阅读

相关【LeetCode with JavaScript】 200. Number of Islands

原题网址：[https://leetcode.com/problems/number-of-islands][https_leetcode.com_problems_numbe

客官°小女子只卖身不卖艺/ 2022年05月24日 08:42/ 0 赞/ 164 阅读

相关 LeetCode 200.Number of Islands (岛屿的个数)

题目描述：给定一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假

深藏阁楼爱情的钟/ 2022年04月15日 01:06/ 0 赞/ 169 阅读

相关 200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An

╰半橙微兮°/ 2022年02月12日 11:47/ 0 赞/ 217 阅读

相关 200. Number of Islands

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An

曾经终败给现在/ 2021年11月16日 11:58/ 0 赞/ 205 阅读