934. Shortest Bridge
Last updated
Last updated
idea: use DFS mark first island to 2 (1 to 2),
then for second island (value is 1), do BFS, until find 2 .=> it's done!
DFS or BFS are all O(mn), so O(mn)
time : O(m*n)
space: O(m*n)
class Solution {
private static final int[][] DIRECTIONS = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestBridge(int[][] grid) {
// dfs to mark first island to 2
// then bfs to find second island (value is 1)
int m = grid.length;
int n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean markFirstIslandOver = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !markFirstIslandOver) {
dfs(grid, i, j);
markFirstIslandOver = true;
}
if (markFirstIslandOver && grid[i][j] == 1) {
queue.offer(new int[]{i, j});
}
}
}
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int q = 0; q < size; q++) {
int cell[] = queue.poll();
int i = cell[0];
int j = cell[1];
for (int dir[] : DIRECTIONS) {
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n) continue;
if (grid[x][y] == 1) {
continue;
} else if (grid[x][y] == 2) {
return level;
} else if (grid[x][y] == 0) {
grid[x][y] = 1;
queue.offer(new int[]{x, y});
}
}
}
level++;
}
return -1;
}
private void dfs(int[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;
// dfs only mark with value is 1
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1) return;
grid[i][j] = 2;
for (int dir[] : DIRECTIONS) {
dfs(grid, i + dir[0], j + dir[1]);
}
}
}
class Solution {
private static final int[][] DIRECTIONS = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestBridge(int[][] grid) {
// dfs to mark first island to 2
// then bfs to find second island (value is 1)
int m = grid.length;
int n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean visited[][] = new boolean[m][n];
boolean markFirstIslandOver = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !markFirstIslandOver) {
dfs(grid, i, j, visited);
markFirstIslandOver = true;
}
if (markFirstIslandOver && grid[i][j] == 1) {
queue.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int q = 0; q < size; q++) {
int cell[] = queue.poll();
int i = cell[0];
int j = cell[1];
for (int dir[] : DIRECTIONS) {
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n) continue; // cant put visited[][] here, grid[x][y] == 2 visited
if (grid[x][y] == 2) { // it must be visited
return level;
}
if (!visited[x][y]) { // zero case
queue.offer(new int[]{x, y});
visited[x][y] = true;
}
}
}
level++;
}
return -1;
}
private void dfs(int[][] grid, int i, int j, boolean visited[][]) {
int m = grid.length;
int n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1) return; // only mark with value is 1
grid[i][j] = 2;
visited[i][j] = true;
for (int dir[] : DIRECTIONS) {
dfs(grid, i + dir[0], j + dir[1], visited);
}
}
}