leetcode 200. Number of Islands

不念不忘少年蓝@ 2022-07-27 14:57 116阅读 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:

11110
    11010
    11000
    00000

Answer: 1

Example 2:

11000
    11000
    00100
    00011

Answer: 3

找最大联通量

class Solution {
    public:
    	int numIslands(vector<vector<char>>& grid) {
    		if (grid.empty() || grid[0].empty())
    			return 0;
    		int cnt = 0;
    		for (int i = 0; i < grid.size(); i++)
    		{
    			for (int j = 0; j < grid[0].size(); j++)
    			{
    				if (grid[i][j] == '1')
    				{
    					cnt++;
    					vector<pair<int, int>>quene;//(x,y)
    					grid[i][j] = '0';
    					quene.push_back(pair<int, int>(j, i));
    					while (!quene.empty())
    					{
    						int x = quene.back().first;
    						int y = quene.back().second;
    						quene.pop_back();
    						if (x - 1 >= 0 && grid[y][x - 1] == '1')
    						{
    							grid[y][x - 1] = '0';
    							quene.push_back(pair<int, int>(x - 1, y));
    						}
    						if (y - 1 >= 0 && grid[y-1][x ] == '1')
    						{
    							grid[y-1][x] = '0';
    							quene.push_back(pair<int, int>(x , y-1));
    						}
    						if (x + 1 <grid[0].size() && grid[y][x + 1] == '1')
    						{
    							grid[y][x + 1] = '0';
    							quene.push_back(pair<int, int>(x + 1, y));
    						}
    						if (y + 1 <grid.size() && grid[y+1][x] == '1')
    						{
    							grid[y+1][x] = '0';
    							quene.push_back(pair<int, int>(x, y+1));
    						}
    					}
    				}
    			}
    		}
    		return cnt;
    	}
    };

accepted

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 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 赞/ 134 阅读

相关 LeetCode200—Number of Islands

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

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

相关 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 赞/ 113 阅读

相关 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 赞/ 117 阅读

相关【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 赞/ 121 阅读

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

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

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

相关 LeetCode：200. Number of Islands（查找岛屿的个数）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

布满荆棘的人生/ 2022年04月05日 08:55/ 0 赞/ 146 阅读

相关 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 赞/ 168 阅读

相关 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 赞/ 161 阅读