1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
// 1254. Number of Closed Islands
#include <stdbool.h>
#include <stdio.h>
/*
* given 2d 'grid' consists of 0's (land) and 1's (water). an island is a
* maximal four directionally connected group of 0's and a closed island is an
* island totally (all left, top, right, bottom) surrouned by 1's. return the
* number of closed islands.
*/
bool dfs(int **grid, int i, int j, int row, int col) {
if (i < 0 || i >= row || j < 0 || j >= col)
return false;
if (grid[i][j])
return true;
grid[i][j] = 1;
bool up = dfs(grid, i - 1, j, row, col);
bool down = dfs(grid, i + 1, j, row, col);
bool left = dfs(grid, i, j - 1, row, col);
bool right = dfs(grid, i, j + 1, row, col);
return up && down && left && right;
}
int closedIslands(int **grid, int grid_size, int *grid_col_size) {
int row = grid_size, col = grid_col_size[0], ans = 0;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
if (!grid[i][j] && dfs(grid, i, j, row, col))
ans++;
return ans;
}
int main() {
int g1[4][8] = {{1, 1, 1, 1, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 1, 1, 0},
{1, 0, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 0}},
gcs1[] = {8, 8, 8, 8}, gs1 = 4;
int g2[2][5] = {{0, 0, 1, 0, 0}, {0, 1, 0, 1, 0}}, gcs2[] = {5, 5}, gs2 = 2;
int g3[7][7] = {{1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}},
gcs3[] = {7, 7, 7, 7, 7, 7, 7}, gs3 = 7;
printf("%d\n", closedIslands(g1, gs1, gcs1)); // expect: 2
printf("%d\n", closedIslands(g2, gs2, gcs2)); // expect: 1
printf("%d\n", closedIslands(g3, gs3, gcs3)); // expect: 2
}
|