LC 岛屿数量(C++ 实现)

问题描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围

示例

1. 输入 [ [‘1’,‘1’,‘1’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘0’,‘0’] ] 输出: 1

2. 输入

[ [‘1’,‘1’,‘0’,‘0’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘1’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘1’,‘1’] ]

输出: 3

题解

思路1：广度优先遍历

#include <iostream> #include <vector> #include <queue> using namespace std; class Solution { public: int numIslands(vector<vector<char>>& grid) { // -------- 1.初始化数组的行数/列数,以及岛屿的个数 -------- // int nr = grid.size(); if (!nr) return 0; int nc = grid[0].size(); int island_num = 0; // -------- 2.遍历数组，使用广度优先搜索将1的位置标记为0，广度优先搜索次数即为岛屿数量 -------- // for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { // ---- 2.1 若下标为[r, c]的数组元素值为1， 则将其置0， 并++island_num ---- // if (grid[r][c] == '1') { grid[r][c] = '0'; island_num++; // ---- 2.1.1 将 (r, c) 存入队列中 ---- // queue<pair<int, int>> neighbors; // * 1 * // neighbors.push({r, c}); // ---- 2.1.2 若队列不为空,迭代计算 ---- // while (!neighbors.empty()) { // ---- 将第一个元素出队,令该元素四周标记为1的元素入队 ---- // auto rc = neighbors.front(); neighbors.pop(); int row = rc.first, col = rc.second; if (row - 1 >= 0 && grid[row - 1][col] == '1') { neighbors.push({row - 1, col}); grid[row - 1][col] = '0'; } if (row + 1 < nr && grid[row + 1][col] == '1') { neighbors.push({row + 1, col}); grid[row + 1][col] = '0'; } if (col - 1 >= 0 && grid[row][col - 1] == '1') { neighbors.push({row, col - 1}); grid[row][col - 1] = '0'; } if (col + 1 < nc && grid[row][col + 1] == '1') { neighbors.push({row, col + 1}); grid[row][col + 1] = '0'; } } } } } return island_num; } };

用例测试

int main() { // -------- 示例 1 ------- //: vector<vector<char>> grid1; grid1.push_back({ '1', '1', '1', '1', '0' }); grid1.push_back({ '1', '1', '0', '1', '0' }); grid1.push_back({ '1', '1', '0', '1', '0' }); grid1.push_back({ '1', '1', '0', '0', '0' }); grid1.push_back({ '0', '0', '0', '0', '0' }); // -------- 示例 2 -------- // vector<vector<char>> grid2; grid2.push_back({ '1', '1', '0', '0', '0' }); grid2.push_back({ '1', '1', '0', '0', '0' }); grid2.push_back({ '0', '0', '1', '0', '0' }); grid2.push_back({ '0', '0', '0', '1', '1' }); Solution solution; cout << "result1 = " << solution.numIslands(grid1) << endl; cout << "result2 = " << solution.numIslands(grid2) << endl; return 0; }