aboutsummaryrefslogtreecommitdiff
path: root/shortest_bridge.c
blob: 7c1a86f7bd769f2c3748451a6e55605b150799df (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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// 934. Shortest Bridge
#include <stdio.h>
#include <stdlib.h>

/*
 * given an 'n x n' binary matrix grid where 1 represents land and 0 represents
 * water. an island is a 4 directionally connected group of 1's not connected to
 * any other 1's. there are exactly two islands in a 'grid'. you may change 0's
 * to 1's to connect the two islands to form one island. return the smallest
 * numbe of 0's you must flip to connect the two islands.
 */

typedef struct {
  int x;
  int y;
  int step;
} point_t;

point_t *bfs(int grid_size, int grid[grid_size][grid_size], int grid_col_size,
             point_t p, int *size) {
  point_t *ans = (point_t *)malloc(10000 * sizeof(point_t));
  *size = 1;
  ans[0] = p;
  int head = 0;
  grid[p.x][p.y] = 2;
  int dir[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  while (head < *size) {
    point_t curr = ans[head++];
    for (int i = 0; i < 4; i++) {
      int dx = dir[i][0];
      int dy = dir[i][1];
      point_t new = {curr.x + dx, curr.y + dy, 0};
      if (0 <= new.x &&new.x < grid_size &&
          0 <= new.y &&new.y < grid_col_size && grid[new.x][new.y] == 1) {
        grid[new.x][new.y] = 2;
        ans[*size] = new;
        (*size)++;
      }
    }
  }
  return ans;
}

int shortestBridge(int grid_size, int grid[grid_size][grid_size],
                   int *grid_col_size) {
  if (!grid || grid_size <= 0 || *grid_col_size <= 0)
    return 0;
  point_t *lands;
  int *size = (int *)malloc(sizeof(int));
  *size = -1;
  int flag = 0;
  for (int i = 0; i < grid_size; i++) {
    for (int j = 0; j < *grid_col_size; j++) {
      if (!grid[i][j])
        continue;
      point_t tmp = {i, j, 0};
      lands = bfs(grid_size, grid, *grid_col_size, tmp, size);
      flag = 1;
      break;
    }
    if (flag)
      break;
  }
  int head = 0, dir[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  while (head < *size) {
    point_t curr = lands[head++];
    for (int i = 0; i < 4; i++) {
      int dx = dir[i][0];
      int dy = dir[i][1];
      point_t new = {curr.x + dx, curr.y + dy, curr.step + 1};
      if (0 <= new.x &&new.x < grid_size &&
          0 <= new.y &&new.y < *grid_col_size && grid[new.x][new.y] != 3) {
        if (grid[new.x][new.y] == 1) {
          free(size);
          free(lands);
          lands = NULL;
          return curr.step;
        }
        if (!grid[new.x][new.y]) {
          lands[*size] = new;
          (*size)++;
          grid[new.x][new.y] = 3;
        }
      }
    }
  }
  free(size);
  free(lands);
  lands = NULL;
  return -1;
}

int main() {
  int g1[2][2] = {{0, 1}, {1, 0}}, gs1 = 2, gcs1[] = {2, 2};
  int g2[3][3] = {{0, 1, 0}, {0, 0, 0}, {0, 0, 1}}, gs2 = 3, gcs2[] = {3, 3, 3};
  int g3[5][5] = {{1, 1, 1, 1, 1},
                  {1, 0, 0, 0, 1},
                  {1, 0, 1, 0, 1},
                  {1, 0, 0, 0, 1},
                  {1, 1, 1, 1, 1}},
      gs3 = 5, gcs3[] = {5, 5, 5, 5, 5};
  printf("%d\n", shortestBridge(gs1, g1, gcs1)); // expect: 1
  printf("%d\n", shortestBridge(gs2, g2, gcs2)); // expect: 2
  printf("%d\n", shortestBridge(gs3, g3, gcs3)); // expect: 1
}