leetcode200. 岛屿数量

举报
兔老大 发表于 2021/04/23 00:02:11 2021/04/23
【摘要】 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1: 输入: 11110 11010 11000 00000 输出: 1 示例 2: 输入: 11000 11000 00100 00011 输出: ...

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

思路:深搜入门题。

对所有位置进行dfs:

dfs:对于能达到的‘1’,全部赋值为‘0’


  
  1. class Solution {
  2. void dfs(char[][] grid, int r, int c) {
  3. int nr = grid.length;
  4. int nc = grid[0].length;
  5. if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
  6. return;
  7. }
  8. grid[r][c] = '0';
  9. dfs(grid, r - 1, c);
  10. dfs(grid, r + 1, c);
  11. dfs(grid, r, c - 1);
  12. dfs(grid, r, c + 1);
  13. }
  14. public int numIslands(char[][] grid) {
  15. if (grid == null || grid.length == 0) {
  16. return 0;
  17. }
  18. int nr = grid.length;
  19. int nc = grid[0].length;
  20. int ans = 0;
  21. for (int r = 0; r < nr; ++r) {
  22. for (int c = 0; c < nc; ++c) {
  23. if (grid[r][c] == '1') {
  24. ++ans;
  25. dfs(grid, r, c);
  26. }
  27. }
  28. }
  29. return ans;
  30. }
  31. }

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/104358880

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。