leetcode 200. Number of Islands

不念不忘少年蓝@ 2022-07-27 14:57 177阅读 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 条评论，177人围观）

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

相关阅读

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

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

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

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

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

相关 LeetCode200—Number of Islands

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

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

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

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

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

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

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

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

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

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