LeetCode 75 Level 1 - Day 9 Graph/BFS/DFS

200. Number of Islands

• 題目連結
• 難易度：Medium

題目敘述

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.

預設函數

int numIslands(char** grid, int gridSize, int* gridColSize){

}

題目限制

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

解題過程及程式碼

本題給一個二維陣列，內部資料是以字元代表陸地或海洋 ('0'為海洋、'1'為陸地)，要求出陣列裡不相連的陸地總共有幾塊，所謂相連的定義是上下左右，像是右下、左下斜角這種是不相連的，如下圖Fig.1這是一整片相連的陸地 (回傳是1)，如下圖Fig.2有3片彼此上下左右沒有相連的陸地 (回傳是3)。

解題想法是先產生一個同樣大小的二維陣列標記該位置是否檢查過，接著從開頭(0, 0)開始：

• 若是遇到陸地則COUNTER++，接著用上下左右擴散的方式找出所有相鄰的陸地並標記已檢查過，若是在上下左右擴散過程中遇到海洋就停止這個方向的擴散。
• 若是遇到海洋也是上下左右擴散的方式找出所有相鄰的海洋並標記已檢查過，遇到陸地就停止。
• 再來找到陣列中下一個未檢查過的位置(i, j)重複上述二個過程直到所有的位置都被檢查過。
• 程式碼上傳

int total, row, col;
int **dynArr2D;

int numIslands(char** grid, int gridSize, int* gridColSize){
    int number = 0, counter = 0;

    total = gridSize * gridColSize[0];
    row = gridSize;
    col = gridColSize[0];

    dynArr2D = (int **)malloc(sizeof(int *) * gridSize);
    for (int i=0; i<gridSize; i++) {
        dynArr2D[i] = (int *)calloc(gridColSize[0], sizeof(int));
    }

    while (number != -1) {
        char is_land = grid[number / col][number % col];

        if (is_land == 49) {  /* 若是為字元'1'的話就將計數+1 */
            counter++;
        }

        find_adjacent_area(number / col, number % col, grid, is_land);
        number = find_unchecked(number);
    }
    return counter;
}
/* 找出還未被檢查過的位置 */
int find_unchecked(int num) {
    int ret = -1;
    for (int i=num; i<total; i++) {
        if (dynArr2D[i / col][i % col] == 0) {
            ret = i;
            break;
        }
    }
    return ret;
}
/* 用來標記所有相鄰的位置 */
void find_adjacent_area(int a, int b, char **map, char is_land) {
    if (map[a][b] != is_land) {
        return;
    }
    dynArr2D[a][b] = 1;  // 標記已檢查過

    if (check_b_range(b + 1) && (dynArr2D[a][b + 1] != 1)) {  // 向右塗滿
        find_adjacent_area(a, b + 1, map, is_land);
    }

    if (check_a_range(a - 1) && (dynArr2D[a - 1][b] != 1)) {  // 向上塗滿
        find_adjacent_area(a - 1, b, map, is_land);
    }

    if (check_b_range(b - 1) && (dynArr2D[a][b - 1] != 1)) {  // 向左塗滿
        find_adjacent_area(a, b - 1, map, is_land);
    }

    if (check_a_range(a + 1) && (dynArr2D[a + 1][b] != 1)) {  // 向下塗滿
        find_adjacent_area(a + 1, b, map, is_land);
    }
}

int check_a_range(int a) {
    if ((a < row) && (a >= 0)) {
        return 1;
    } else {
        return 0;
    }
}

int check_b_range(int b) {
    if ((b < col) && (b >= 0)) {
        return 1;
    } else {
        return 0;
    }
}

金牌18天到這裡，謝謝大家!