200. 岛屿数量

yzhms

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

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

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

yzhms

1. 
   
2. void step(int row, int col, char **grid2, int gridSize, int *gridColSize) {
   
3.     if ((row < 0) || (row >= gridSize) || (col < 0) || col >= (*gridColSize)) {
   
4.         return;
   
5.     }
   
6.     if (grid2[row][col] == '0') {
   
7.         return;
   
8.     }
   
9.     //printf("step[%d][%d]='%c'\n", row, col, grid2[row][col]);
   
10.     grid2[row][col] = '0';
    
11.     //up
    
12.     step(row - 1, col, grid2, gridSize, gridColSize);
    
13.     //down
    
14.     step(row + 1, col, grid2, gridSize, gridColSize);
    
15.     //left
    
16.     step(row, col - 1, grid2, gridSize, gridColSize);
    
17.     //right
    
18.     step(row, col + 1, grid2, gridSize, gridColSize);
    
19. }
    
20. 
    
21. int numIslands(char** grid, int gridSize, int* gridColSize){
    
22.     char **grid2;
    
23.     int i, j;
    
24.     int sum = 0;
    
25. 
    
26.     if (!grid || !gridSize || !gridColSize || !grid[0] || !gridColSize[0]) {
    
27.         return 0;
    
28.     }
    
29.    
    
30.     i=grid[0][0];
    
31.     grid2 = (char**)malloc(sizeof(char*) * gridSize);
    
32.     for (i = 0; i < gridSize; i++) {
    
33.         grid2[i] = (char*)malloc(*gridColSize);
    
34.         memcpy(grid2[i], grid[i], *gridColSize);
    
35.     }
    
36. 
    
37.     for (i = 0; i < gridSize; i++) {
    
38.         for (j = 0; j < *gridColSize; j++) {
    
39.             //printf("grid[%d][%d]='%c'\n", i, j, grid2[i][j]);
    
40.             if (grid2[i][j] != '0') {
    
41.                 step(i, j, grid2, gridSize, gridColSize);
    
42.                 sum++;
    
43.             }
    
44.         }
    
45.     }
    
46. 
    
47. 
    
48.     for (i = 0; i < gridSize; i++) {
    
49.         free(grid2[i]);
    
50.     }
    
51.     free(grid2);
    
52.     return sum;
    
53. }

复制代码

执行结果：通过
显示详情

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