aboutsummaryrefslogtreecommitdiff
path: root/num_enclaves.c
blob: 662d9ab425483048411ae57b612089c42620a8f6 (plain)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 1020. Number of Enclaves
#include <stdbool.h>
#include <stdio.h>

/*
 * given an 'm * n' binary matrix grid, where 0 represents a sea
 * cell and 1 represents a land cell. a move consists of walking
 * from one land cell to another adjacent (4-directionally) land
 * cell o walking off the boundary of the 'grid'. return number
 * of land cells in 'grid' for which we cannot walk off the
 * boundary of the grid in any number of moves.
 */

int u_find(int *u, int val) {
  if (u[val] == val)
    return val;
  return u_find(u, u[val]);
}

bool u_set(int *u, int a, int b) {
  int find_a = u_find(u, a), find_b = u_find(u, b);
  if (find_a == find_b)
    return false;
  u[find_a] = u[find_b];
  return true;
}

void bfs(int **grid, int row, int col, int i, int j) {
  if (i < 0 || i >= row || j < 0 || j >= col)
    return;
  if (!grid[i][j])
    return;
  grid[i][j] = 0;
  bfs(grid, row, col, i - 1, j);
  bfs(grid, row, col, i + 1, j);
  bfs(grid, row, col, i, j - 1);
  bfs(grid, row, col, i, j + 1);
}

int numEnclaves(int **grid, int grid_size, int *grid_col_size) {
  int row = grid_size, col = *grid_col_size;
  for (int i = 0; i < col; i++)
    bfs(grid, row, col, 0, i);
  for (int i = 0; i < col; i++)
    bfs(grid, row, col, row - 1, i);
  for (int i = 0; i < row; i++)
    bfs(grid, row, col, i, 0);
  for (int i = 0; i < row; i++)
    bfs(grid, row, col, i, col - 1);
  int ans = 0;
  for (int i = 0; i < row; i++)
    for (int j = 0; j < col; j++)
      if (grid[i][j])
        ans++;
  return ans;
}

int main() {
  int g1[4][4] = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
  int g2[4][4] = {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
  int grid_size = 4;
  int grid_col_size[] = {4, 4, 4, 4};
  printf("%d\n", numEnclaves(g1, grid_size, grid_col_size)); // expect: 3
  printf("%d\n", numEnclaves(g2, grid_size, grid_col_size)); // expect: 3
}