Shortest Bridge

LeetCode Q 934 - Shortest Bridge

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:
Input: [[0,1],[1,0]] ; Output: 1

Example 2:
Input: [[0,1,0],[0,0,0],[0,0,1]] ; Output: 2

Example 3:
Input: [[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]]; Output: 1

Note:

• 1 <= A.length = A[0].length <= 100
• A[i][j] == 0 or A[i][j] == 1

Solution : DFS + BFS

DFS: find the first island, offer all its lands to the que.

BFS: expand the found island layer by layer until it reaches another one.

Code:

private static final int[][] DIRS = new int[][] { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
public int shortestBridge(int[][] A) {
	
	int R = A.length, C = A[0].length;
	boolean[][] visited = new boolean[R][C];

	Queue<int[]> que = new LinkedList<>();
	boolean found = false;

	// 1. DFS to find one island, put its land in the queue
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (found) break;
			if (A[r][c] == 1) {
				dfs(A, visited, r, c, que);
				found = true; break;
			}
		}
	}

	// 2. BFS to expand the current found island to let it reach another one
	int level = 0;
	while (!que.isEmpty()) {
		int size = que.size();
		while (size-- != 0) {
			int[] curr = que.poll();
			for (int[] dir: DIRS) {
				int i = curr[0] + dir[0];
				int j = curr[1] + dir[1];
				if (i >= 0 && j >= 0 && i < R && j < C && !visited[i][j] ) {
					if (A[i][j] == 1) return level;
					que.offer(new int[]{i, j});
					visited[i][j] = true;
				}
			}
		}
		level++;
	}

	return -1;
}
private void dfs(int[][] A, boolean[][] visited, int r, int c, Queue<int[]> que) {

	if (r < 0 || c < 0 || r == A.length || c == A[0].length || visited[r][c] || A[r][c] == 0)
		return;
		
	visited[r][c] = true;
	que.offer(new int[] {r, c});
	for (int[] dir: DIRS) dfs(A, visited, dirs, que, r + dir[0], c + dir[1]);
}