This page explains Java solution to problem Minimum Number of Days to Disconnect Island
using Depth First Search
algorithm.
Given a 2D
grid consisting of 1s
(land) and 0s
(water). An island is a maximal 4-directionally (horizontal or vertical) connected group of 1s
.
The grid is said to be connected if we have exactly one island, otherwise is said disconnected.
In one day, we are allowed to change any single land cell (1)
into a water cell (0)
.
Return the minimum number of days to disconnect the grid.
Example 1:Example 2:Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
Example 3:Input: [[1,1]]
Output: 1
Example 4:Input: [[1,0,1,0]]
Output: 0
Input: [[1,1,0,1,1], [1,1,1,1,1], [1,1,0,1,1],[1,1,1,1,1]]
Output: 2
package com.vc.hard;
class MinimumNumberOfDaysToDisconnectIsland {
public int minDays(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
if(islandCount(grid) != 1) return 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1) {
grid[i][j] = 0;
if(islandCount(grid) != 1) return 1;
grid[i][j] = 1;
}
}
}
/**
At most it will take 2 days to disconnect island,
because you can just disconnect one island on bottom left as below
Let's say we have:
1 1 1
1 1 1
1 1 1
Disconnect bottome left island like so:
1 1 1
0 1 1
1 0 1
*/
return 2;
}
private int islandCount(int[][] grid) {
int count = 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1 && !visited[i][j]) {
dfs(grid, visited, i, j);
count++;
}
}
}
return count;
}
private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void dfs(int[][] grid, boolean[][] visited, int row, int col) {
if(visited[row][col]) return;
visited[row][col] = true;
for(int[] dir: dirs) {
int rowNew = row + dir[0];
int colNew = col + dir[1];
if(rowNew >= 0 && rowNew < grid.length && colNew >= 0 && colNew < grid[0].length &&
grid[rowNew][colNew] == 1) {
dfs(grid, visited, rowNew, colNew);
}
}
}
}
O((N * M)2) Where
N is number of Rows in an input grid
M is number of Columns in an input grid
O(N * M) Where
N is number of Rows in an input grid
M is number of Columns in an input grid