1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; 
6
7void dfs(int** grid, int n, int x, int y, int** visited, int* queue, int* queueSize) {
8    if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
9    visited[x][y] = 1;
10    queue[(*queueSize)++] = x * n + y;
11    for (int i = 0; i < 4; i++)
12        dfs(grid, n, x + directions[i][0], y + directions[i][1], visited, queue, queueSize);
13}
14
15int shortestBridge(int** grid, int gridSize, int* gridColSize) {
16    int n = gridSize;
17    int** visited = (int**) malloc(n * sizeof(int*));
18    for (int i = 0; i < n; i++) 
19        visited[i] = (int*)calloc(n, sizeof(int));
20    
21    int* queue = (int*) malloc(n * n * sizeof(int));
22    int queueSize = 0, head = 0;
23    bool found = false;
24    
25    for (int i = 0; !found && i < n; i++) {
26        for (int j = 0; !found && j < n; j++) {
27            if (grid[i][j] == 1) {
28                dfs(grid, n, i, j, visited, queue, &queueSize);
29                found = true;
30            }
31        }
32    }
33    int steps = 0;
34    while (head < queueSize) {
35        int size = queueSize - head;
36        while (size--) {
37            int pos = queue[head++], x = pos / n, y = pos % n;
38            for (int i = 0; i < 4; i++) {
39                int newX = x + directions[i][0], newY = y + directions[i][1];
40                if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
41                    if (grid[newX][newY] == 1) return steps;
42                    visited[newX][newY] = 1;
43                    queue[queueSize++] = newX * n + newY;
44                }
45            }
46        }
47        steps++;
48    }
49    return -1;
50}
51
52int main() {
53    int grid1[2][2] = {{0,1},{1,0}};
54    int* gridPtrs1[2];
55    for (int i = 0; i < 2; i++) gridPtrs1[i] = grid1[i];
56    int gridColSize[2] = {2,2};
57    printf("%d\n", shortestBridge(gridPtrs1, 2, gridColSize)); // Expected output: 1
58    
59    int grid2[3][3] = {{0,1,0},{0,0,0},{0,0,1}};
60    int* gridPtrs2[3];
61    for (int i = 0; i < 3; i++) gridPtrs2[i] = grid2[i];
62    int gridColSize2[3] = {3,3,3};
63    printf("%d\n", shortestBridge(gridPtrs2, 3, gridColSize2)); // Expected output: 2
64    
65    int grid3[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}};
66    int* gridPtrs3[5];
67    for (int i = 0; i < 5; i++) gridPtrs3[i] = grid3[i];
68    int gridColSize3[5] = {5,5,5,5,5};
69    printf("%d\n", shortestBridge(gridPtrs3, 5, gridColSize3)); // Expected output: 1
70    return 0;
71}
72