Problem Statement
In the context of this problem, you are dealing with an n x n binary matrix visualization known as grid where the digit 1 symbolizes land and the digit 0 symbolizes water. The construct of an "island" in this matrix is defined as a cluster of adjacent 1's (connected from any of the four possible directions: up, down, left, or right), which stands isolated from any other clusters of 1's. It's established that there are precisely two such islands in the grid provided.
The primary objective is to ascertain the minimum number of 0 values (water) that must be converted into 1 values (land) to merge the two separate islands into one singular connected mass. The result should express this minimum quantity of conversions necessary to achieve the desired outcome.
Examples
Example 1
Input:
grid = [[0,1],[1,0]]
Output:
1
Example 2
Input:
grid = [[0,1,0],[0,0,0],[0,0,1]]
Output:
2
Example 3
Input:
grid = [[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
Constraints
n == grid.length == grid[i].length2 <= n <= 100grid[i][j]is either0or1.- There are exactly two islands in
grid.
Approach and Intuition
To solve this problem effectively, let's consider each step based on the provided examples and constraints:
Breadth-First Search (BFS) Initialization:
- First, identify the coordinates of the cells that make up each of the two islands. This can be done using a BFS approach starting from any
1found, marking and storing all connected1's until the entire island is traced.
- First, identify the coordinates of the cells that make up each of the two islands. This can be done using a BFS approach starting from any
Layer Expansion:
- Once the two islands are identified and their coordinates known, initiate an expansion from the entire first island, treating each position as a level in BFS. This expansion involves moving to adjacent
0cells and incrementing a count of steps taken.
- Once the two islands are identified and their coordinates known, initiate an expansion from the entire first island, treating each position as a level in BFS. This expansion involves moving to adjacent
Intersection Check:
- The expansion continues until the cells being expanded from one island meet the cells of the other island. The point at which these expansions intersect gives the minimum number of
0s – the distance that needs to be flipped to connect the two islands.
- The expansion continues until the cells being expanded from one island meet the cells of the other island. The point at which these expansions intersect gives the minimum number of
The intuition behind using BFS rather than DFS (Depth-First Search) is in managing the expansion level by level, which aligns well with finding the shortest path or minimum number of steps to connect two regions on the grid. Each layer or level in BFS represents a ring of expansions from the originally identified borders of the islands. This method ensures that the first intersection point of these growing rings denotes the shortest path connecting the two islands.
The constraints specify that we're dealing with a reasonably sized grid (2 <= n <= 100), making a BFS approach feasible within given limits. The guarantee of exactly two islands simplifies the initial problem identification phase.
Solutions
- C++
class Solution {
public:
int findShortestBridge(vector<vector<int>>& matrix) {
int size = matrix.size();
int startY = -1, startX = -1;
// Locate first land
for (int r = 0; r < size; r++) {
for (int c = 0; c < size; c++) {
if (matrix[r][c] == 1) {
startY = r;
startX = c;
break;
}
}
if (startY != -1) break;
}
// Queue for BFS
vector<pair<int, int>> bfsQueue, waterQueue;
bfsQueue.push_back({startY, startX});
waterQueue.push_back({startY, startX});
matrix[startY][startX] = 2;
// Process first island
while (!bfsQueue.empty()) {
vector<pair<int, int>> tempQueue;
for (auto& coord : bfsQueue) {
int row = coord.first, col = coord.second;
vector<pair<int, int>> directions = {{row + 1, col}, {row - 1, col}, {row, col + 1}, {row, col - 1}};
for (auto& d : directions) {
int nextRow = d.first, nextCol = d.second;
if (nextRow >= 0 && nextRow < size && nextCol >= 0 && nextCol < size && matrix[nextRow][nextCol] == 1) {
tempQueue.push_back({nextRow, nextCol});
waterQueue.push_back({nextRow, nextCol});
matrix[nextRow][nextCol] = 2;
}
}
}
bfsQueue = tempQueue;
}
// Expand from the coded island
int separation = 0;
while (!waterQueue.empty()) {
vector<pair<int, int>> currentQueue;
for (auto& coord : waterQueue) {
int row = coord.first, col = coord.second;
vector<pair<int, int>> directions = {{row + 1, col}, {row - 1, col}, {row, col + 1}, {row, col - 1}};
for (auto& d : directions) {
int nextRow = d.first, nextCol = d.second;
if (nextRow >= 0 && nextRow < size && nextCol >= 0 && nextCol < size) {
if (matrix[nextRow][nextCol] == 1) {
return separation;
}
if (matrix[nextRow][nextCol] == 0) {
currentQueue.push_back({nextRow, nextCol});
matrix[nextRow][nextCol] = -1;
}
}
}
}
waterQueue = currentQueue;
separation++;
}
return separation;
}
};
The task involves finding the shortest bridge between two islands on a grid, using Breadth-First-Search (BFS) and marking processes in C++.
- Start by locating the first cell of an island on the grid. This initiates at an uninitialized state and begins scanning until it finds the first land parcel (denoted by 1).
- Initiate two queues: one for processing the BFS (
bfsQueue) and another (waterQueue) that will both start from the located starting land cell. Mark this initial cell differently (with 2) to avoid reprocessing. - Conduct the BFS to process the entire first island. For each cell processed as part of the first island, add adjacent land cells to the queue and mark them to prevent future reprocessing.
- After processing the whole island, begin expanding the search into water cells around this island, aiming to find the shortest route to the second island. Continue marking the cells to avoid revisiting.
- For each layer of expansion from the island (moving outwards in the grid by one cell layer per iteration), check if the new cells touch the second island. If they do, the current count of steps taken represents the shortest bridge length.
- Continue the expansion until a pathway to the second island is confirmed, returning the number of steps expanded as the bridge length.
This solution utilizes two main phases: marking the first island and expanding outwards to find the shortest path to the second island. Efficient use of queues helps systematically process each layer, ensuring an optimized search for the shortest bridge.
- Java
class Solution {
public int findShortestBridge(int[][] area) {
int size = area.length;
int initialX = -1, initialY = -1;
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
if (area[x][y] == 1) {
initialX = x;
initialY = y;
break;
}
}
if (initialX != -1) break;
}
List<int[]> landSearchQueue = new ArrayList<>();
List<int[]> waterSearchQueue = new ArrayList<>();
landSearchQueue.add(new int[] { initialX, initialY });
waterSearchQueue.add(new int[] { initialX, initialY });
area[initialX][initialY] = 2;
while (!landSearchQueue.isEmpty()) {
List<int[]> currentLandBatch = new ArrayList<>();
for (int[] point : landSearchQueue) {
int x = point[0];
int y = point[1];
for (int[] direction : new int[][] {
{ x + 1, y }, { x - 1, y }, { x, y + 1 }, { x, y - 1 }
}) {
int newX = direction[0];
int newY = direction[1];
if (newX >= 0 && newX < size && newY >= 0 && newY < size && area[newX][newY] == 1) {
currentLandBatch.add(new int[] { newX, newY });
waterSearchQueue.add(new int[] { newX, newY });
area[newX][newY] = 2;
}
}
}
landSearchQueue = currentLandBatch;
}
int bridgeLength = 0;
while (!waterSearchQueue.isEmpty()) {
List<int[]> currentWaterBatch = new ArrayList<>();
for (int[] point : waterSearchQueue) {
int x = point[0];
int y = point[1];
for (int[] direction : new int[][] {
{ x + 1, y }, { x - 1, y }, { x, y + 1 }, { x, y - 1 }
}) {
int newX = direction[0];
int newY = direction[1];
if (newX >= 0 && newX < size && newY >= 0 && newY < size) {
if (area[newX][newY] == 1) {
return bridgeLength;
} else if (area[newX][newY] == 0) {
currentWaterBatch.add(new int[] { newX, newY });
area[newX][newY] = -1;
}
}
}
}
waterSearchQueue = currentWaterBatch;
bridgeLength++;
}
return bridgeLength;
}
}
The Java solution to the "Shortest Bridge" problem involves identifying and connecting two islands in a grid using the minimum number of bridge tiles. This solution uses a breadth-first search (BFS) technique which is executed in two phases:
Initial Island Discovery and Water Expansion:
- Start by finding the first 1 (representing land) in the grid to determine the starting point for the land discovery.
- Use BFS to traverse all connected land tiles of the first island, marking them distinctively and adding them to a queue for subsequent processing.
- Simultaneously, add all neighboring water tiles of each discovered land tile to a separate queue for potential expansion.
Bridge Building through Water:
- Process the water tiles queue accumulated from the first phase.
- For each water tile, check all four possible directions for expansion.
- If another land tile is encountered during expansion, it indicates the discovery of the second island, and the minimum bridge length is achieved.
- If a water tile is encountered, mark and add it to the queue for further expansion in the next steps of BFS.
- Continue expanding layer by layer until the second island is reached.
This algorithm effectively marks the first island and uses it as a base for building the shortest bridge to the second island, tracking and returning the number of steps taken to connect the two islands. The solution ensures optimal performance by terminating immediately when the second island is reached and accurately counts the steps required to build the bridge.
- Python
class Solution:
def findMinBridge(self, islandMap: List[List[int]]) -> int:
mapSize = len(islandMap)
initX, initY = -1, -1
# Discover starting point of the first island.
for row in range(mapSize):
for col in range(mapSize):
if islandMap[row][col] == 1:
initX, initY = row, col
break
# Preparing queues: one for initial island discovery, one for the water expansion.
exploreQueue = [(initX, initY)]
waterQueue = [(initX, initY)]
islandMap[initX][initY] = 2
# Explore the entire first island marking its area as visited.
while exploreQueue:
tempQueue = []
for xPos, yPos in exploreQueue:
for newX, newY in [(xPos + 1, yPos), (xPos - 1, yPos), (xPos, yPos + 1), (xPos, yPos - 1)]:
if 0 <= newX < mapSize and 0 <= newY < mapSize and islandMap[newX][newY] == 1:
tempQueue.append((newX, newY))
waterQueue.append((newX, newY))
islandMap[newX][newY] = 2
exploreQueue = tempQueue
# Minimum distance calculation through BFS over the water.
minDist = 0
while waterQueue:
tempQueue = []
for xPos, yPos in waterQueue:
for newX, newY in [(xPos + 1, yPos), (xPos - 1, yPos), (xPos, yPos + 1), (xPos, yPos - 1)]:
if 0 <= newX < mapSize and 0 <= newY < mapSize:
if islandMap[newX][newY] == 1:
return minDist
elif islandMap[newX][newY] == 0:
tempQueue.append((newX, newY))
islandMap[newX][newY] = -1
waterQueue = tempQueue
minDist += 1
return minDist
The provided Python code is designed to solve the "Shortest Bridge" problem where the main task is to find the shortest bridge connecting two islands in a given grid. The grid is represented as a 2D list, where '1' indicates land and '0' indicates water.
Here is a breakdown of how the solution operates:
Firstly, the code identifies the starting point of one of the islands. This is achieved by iterating over the grid until it finds a cell with value '1', which marks the beginning of an island.
Two queues are initiated: one
exploreQueuefor the land portion of the island for marking all connected parts of the first island, and anotherwaterQueuefor managing the water expansion in search of the second island.The solution uses a breadth-first search (BFS) approach. It first marks all the cells of the first island using the
exploreQueueand changes their values to '2' to indicate they are visited. These cells are also added towaterQueue.After marking the entire first island, the code iterates through the
waterQueuefor water expansion. For each cell in the queue, it explores its neighbors. If a neighboring cell belongs to the second island (i.e., has a value of '1'), it returns the distance accumulated so far as the shortest bridge distance.If a neighboring cell is water (i.e., has a value of '0'), it adds this cell to the next layer of the BFS queue and marks it as visited by setting the value to '-1'.
The process increments the distance with each layer of water explored until the second island is reached. The function finally returns the minimum distance as the shortest bridge length needed to connect the two islands. This approach ensures efficient exploration and accurate calculation of the bridge length using BFS in a grid-based map.
No comments yet.