Description

200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 用DFS函數，用於標記已訪問的陸地
void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {
    // 檢查邊界條件和是否是陸地,(i,j)超出範圍或是當前水域為0則直接返回
    if (i < 0 || i >= gridSize || j < 0 || j >= gridColSize[i] || grid[i][j] == '0') {
        return;
    }

    // 將當前陸地標記為visited(將1改成0)
    grid[i][j] = '0';

    // 遞迴用DFS visit上下左右四個方向，
    dfs(grid, gridSize, gridColSize, i - 1, j); // 上
    dfs(grid, gridSize, gridColSize, i + 1, j); // 下
    dfs(grid, gridSize, gridColSize, i, j - 1); // 左
    dfs(grid, gridSize, gridColSize, i, j + 1); // 右
}

// 計算島嶼數量的函數
int numIslands(char** grid, int gridSize, int* gridColSize) {
    if (grid == NULL || gridSize == 0 || gridColSize == NULL) {
        return 0;
    } //輸入的grid為空或是大小為0則返回0

    int num_islands = 0;

    // 遍歷整個網格
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            // 如果遇到一個未訪問的陸地塊
            if (grid[i][j] == '1') {
                num_islands++;
                dfs(grid, gridSize, gridColSize, i, j);
            }
        }
    }

    return num_islands;
}

// 初始化字元網格函數(字元二維陣列)
char** createGrid(char* grid[], int gridSize, int* gridColSize) {
    char** newGrid = (char**)malloc(gridSize * sizeof(char*));
    for (int i = 0; i < gridSize; i++) {
        gridColSize[i] = strlen(grid[i]);
        newGrid[i] = (char*)malloc(gridColSize[i] * sizeof(char));
        for (int j = 0; j < gridColSize[i]; j++) {
            newGrid[i][j] = grid[i][j]; //複製字元
        }
    }
    return newGrid; //回傳新的陣列
}

// 釋放字元網格記憶體的函數
void freeGrid(char** grid, int gridSize) {
    for (int i = 0; i < gridSize; i++) {
        free(grid[i]);//釋放空間
    }
    free(grid);
}

Testing

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 用DFS函數，用於標記已訪問的陸地
void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {
    // 檢查邊界條件和是否是陸地,(i,j)超出範圍或是當前水域為0則直接返回
    if (i < 0 || i >= gridSize || j < 0 || j >= gridColSize[i] || grid[i][j] == '0') {
        return;
    }

    // 將當前陸地標記為visited(將1改成0)
    grid[i][j] = '0';

    // 遞迴用DFS visit上下左右四個方向，
    dfs(grid, gridSize, gridColSize, i - 1, j); // 上
    dfs(grid, gridSize, gridColSize, i + 1, j); // 下
    dfs(grid, gridSize, gridColSize, i, j - 1); // 左
    dfs(grid, gridSize, gridColSize, i, j + 1); // 右
}

// 計算島嶼數量的函數
int numIslands(char** grid, int gridSize, int* gridColSize) {
    if (grid == NULL || gridSize == 0 || gridColSize == NULL) {
        return 0;
    } //輸入的grid為空或是大小為0則返回0

    int num_islands = 0;

    // 遍歷整個網格
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            // 如果遇到一個未訪問的陸地塊
            if (grid[i][j] == '1') {
                num_islands++;
                dfs(grid, gridSize, gridColSize, i, j);
            }
        }
    }

    return num_islands;
}

// 初始化字元網格函數(字元二維陣列)
char** createGrid(char* grid[], int gridSize, int* gridColSize) {
    char** newGrid = (char**)malloc(gridSize * sizeof(char*));
    for (int i = 0; i < gridSize; i++) {
        gridColSize[i] = strlen(grid[i]);
        newGrid[i] = (char*)malloc(gridColSize[i] * sizeof(char));
        for (int j = 0; j < gridColSize[i]; j++) {
            newGrid[i][j] = grid[i][j]; //複製字元
        }
    }
    return newGrid; //回傳新的陣列
}

// 釋放字元網格記憶體的函數
void freeGrid(char** grid, int gridSize) {
    for (int i = 0; i < gridSize; i++) {
        free(grid[i]);//釋放空間
    }
    free(grid);
}

// 主測試函數，測試不同的測試範例
int main() {
    // 測試範例1
    char* grid1[] = {
        "11110",
        "11010",
        "11000",
        "00000"
    };
    int gridSize1 = 4;
    int gridColSize1[gridSize1];
    char** newGrid1 = createGrid(grid1, gridSize1, gridColSize1);
    printf("測試範例 1 輸出: %d\n", numIslands(newGrid1, gridSize1, gridColSize1)); // 輸出: 1
    freeGrid(newGrid1, gridSize1);

    // 測試範例2
    char* grid2[] = {
        "11000",
        "11000",
        "00100",
        "00011"
    };
    int gridSize2 = 4;
    int gridColSize2[gridSize2];
    char** newGrid2 = createGrid(grid2, gridSize2, gridColSize2);
    printf("測試範例 2 輸出: %d\n", numIslands(newGrid2, gridSize2, gridColSize2)); // 輸出: 3
    freeGrid(newGrid2, gridSize2);

    return 0;
}