朝阳无限好 - Morning Sun Community

 找回密码
 注册
查看: 220|回复: 1

[中等] 200. 岛屿数量

[复制链接]
发表于 2020-3-30 21:48:03 | 显示全部楼层 |阅读模式
给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 楼主| 发表于 2020-3-30 21:48:34 | 显示全部楼层
本帖最后由 yzhms 于 2020-3-30 21:52 编辑

  1. void step(int row, int col, char **grid2, int gridSize, int *gridColSize) {
  2.     if ((row < 0) || (row >= gridSize) || (col < 0) || col >= (*gridColSize)) {
  3.         return;
  4.     }
  5.     if (grid2[row][col] == '0') {
  6.         return;
  7.     }
  8.     //printf("step[%d][%d]='%c'\n", row, col, grid2[row][col]);
  9.     grid2[row][col] = '0';
  10.     //up
  11.     step(row - 1, col, grid2, gridSize, gridColSize);
  12.     //down
  13.     step(row + 1, col, grid2, gridSize, gridColSize);
  14.     //left
  15.     step(row, col - 1, grid2, gridSize, gridColSize);
  16.     //right
  17.     step(row, col + 1, grid2, gridSize, gridColSize);
  18. }

  19. int numIslands(char** grid, int gridSize, int* gridColSize){
  20.     char **grid2;
  21.     int i, j;
  22.     int sum = 0;

  23.     if (!grid || !gridSize || !gridColSize || !grid[0] || !gridColSize[0]) {
  24.         return 0;
  25.     }
  26.    
  27.     i=grid[0][0];
  28.     grid2 = (char**)malloc(sizeof(char*) * gridSize);
  29.     for (i = 0; i < gridSize; i++) {
  30.         grid2[i] = (char*)malloc(*gridColSize);
  31.         memcpy(grid2[i], grid[i], *gridColSize);
  32.     }

  33.     for (i = 0; i < gridSize; i++) {
  34.         for (j = 0; j < *gridColSize; j++) {
  35.             //printf("grid[%d][%d]='%c'\n", i, j, grid2[i][j]);
  36.             if (grid2[i][j] != '0') {
  37.                 step(i, j, grid2, gridSize, gridColSize);
  38.                 sum++;
  39.             }
  40.         }
  41.     }


  42.     for (i = 0; i < gridSize; i++) {
  43.         free(grid2[i]);
  44.     }
  45.     free(grid2);
  46.     return sum;
  47. }
复制代码


执行结果:通过
显示详情

执行用时 :8 ms, 在所有 C 提交中击败了99.97%的用户
内存消耗 :7.4 MB, 在所有 C 提交中击败了100.00%的用户
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|手机版|Archiver|朝阳无限好 ( 琼ICP备19005269号-1 )

GMT+8, 2020-10-25 10:29 , Processed in 0.055285 second(s), 16 queries .

快速回复 返回顶部 返回列表