Given a 2D grid arr[][] of ‘W’ and ‘L’ where ‘W’ denotes water and ‘L’ denotes land, the task is to find the minimum number of water components ‘W’ that must be changed to land component ‘L’ so that two islands becomes connected.
An island is the set of connected ‘L’s
Note: There can be only two disjoint islands.
Examples:
Input: arr[][] = {{‘W’, ‘L’}, {‘L’, ‘W’}};
Output: 1
Explanation: For the given set of islands if we change arr[1][1] to ‘W’
then, set of all island are connected.
Therefore, the minimum number of ‘W’ must be changed to ‘L’ is 1.Input: arr[][] = {{‘W’, ‘L’, ‘W’}, {‘W’, ‘W’, ‘W’}, {‘W’, ‘W’, ‘L’}}
Output: 2
Approach based on Floodfill algorithm: The approach based on Floodfill algorithm is discussed in Set-1 of this article.
Efficient Approach: This problem can be solved by using DFS and BFS algorithms. The idea is to use DFS to find all the land components of one island and simultaneously adding the bordering land components to queue which will be used in BFS to expand and find the shortest path to second island. Follow the steps mentioned below to solve the problem:
- Use a nested loop to find the first occurrence of ‘L’ in arr[][].
- Call DFS to find all the elements of this island and if any ‘L’ is a border element (i.e. surrounded by ‘W’ on at least one side) also add it in a queue.
- Expand this island using BFS algorithm using the queue and visited array created during DFS call.
- At each level increase the distance by 1.
- By using BFS find the smallest path from border of one island to second island.
- If the next component to be added in the queue is ‘L’, return the distance up till now.
Note: All elements of the first island can also be found using the BFS algorithm also.
Below is the implementation of the above approach:
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// A class to represent point and dist from first islandclass qNode {public: int x, y, dist; qNode(int x, int y, int dist) { this->x = x; this->y = y; this->dist = dist; }};// Arrays to get the adjacent indices from one index of the// gridint dirx[4] = { 0, 1, 0, -1 };int diry[4] = { 1, 0, -1, 0 };// Global variables for size of arrayint R, C;// To check if indices are in matrixbool isValid(int x, int y){ if (x < 0 || y < 0 || x >= R || y >= C) return false; return true;}// Return true if surrounded by water in any of 4 directionbool isBorder(int i, int j, vector<vector<char> >& arr){ for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && arr[x][y] == 'W') return true; } return false;}// Function to run DFSvoid dfs(int i, int j, vector<vector<bool> >& visited, queue<qNode>& q, vector<vector<char> >& arr){ visited[i][j] = true; // Checking if it is border component if (isBorder(i, j, arr)) { q.push(qNode(i, j, 0)); } // Calling dfs in all 4 directions for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && arr[x][y] == 'L' && !visited[x][y]) dfs(x, y, visited, q, arr); }}// Function to implement BFSint bfs(queue<qNode>& q, vector<vector<bool> >& visited, vector<vector<char> >& arr){ while (q.size() > 0) { qNode p = q.front(); q.pop(); for (int idx = 0; idx < 4; idx++) { int x = p.x + dirx[idx]; int y = p.y + diry[idx]; // If next unvisited component // is land, return dist // till of p only if (isValid(x, y) && arr[x][y] == 'L' && !visited[x][y]) { return p.dist; } if (isValid(x, y) && arr[x][y] == 'W' && !visited[x][y]) { q.push(qNode(x, y, 1 + p.dist)); visited[x][y] = true; } } } return -1;}// Function to find minimum conversionsint minConversions(vector<vector<char> >& arr){ R = arr.size(); C = arr[0].size(); // Queue to be used in bfs queue<qNode> q; vector<vector<bool> > visited(R, vector<bool>(C, false)); bool flag = false; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i][j] == 'L') { // Visited first island completely and at // same time maintaining visited array and // queue dfs(i, j, visited, q, arr); flag = true; break; } } // Breaking the nested loop once first island found if (flag) break; } return bfs(q, visited, arr);}// Driver codeint main(){ // Creating the Grid vector<vector<char> > arr = { { 'W', 'L', 'W' }, { 'W', 'W', 'W' }, { 'W', 'W', 'L' } }; // Function call cout << minConversions(arr); return 0;}// This code is contributed by abhishekghoshindia. |
Java
// Java program to implement the approachimport java.util.*;public class GFG { static int R; static int C; // A class to represent point and // dist from first island static class qNode { int x; int y; int dist; qNode(int x, int y, int d) { this.x = x; this.y = y; this.dist = d; } } // Function to find minimum conversions static int minConversions(char[][] arr) { R = arr.length; C = arr[0].length; // Queue to be used in bfs Queue<qNode> q = new ArrayDeque<>(); boolean[][] visited = new boolean[R][C]; boolean flag = false; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i][j] == 'L') { // Visited first island // completely and at // same time maintaining // visited array and queue dfs(i, j, visited, q, arr); flag = true; break; } } // Breaking the nested loop // once first island found if (flag) break; } return bfs(q, visited, arr); } // Arrays to get the adjacent indices // from one index of thegrid static int[] dirx = { 0, 1, 0, -1 }; static int[] diry = { 1, 0, -1, 0 }; // Function to run DFS static void dfs(int i, int j, boolean[][] visited, Queue<qNode> q, char[][] arr) { visited[i][j] = true; // Checking if it is border component if (isBorder(i, j, arr)) { q.add(new qNode(i, j, 0)); } // Calling dfs in all 4 directions for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && arr[x][y] == 'L' && !visited[x][y]) { dfs(x, y, visited, q, arr); } } } // Return true if surrounded by water // in any of 4 direction static boolean isBorder(int i, int j, char[][] arr) { for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && arr[x][y] == 'W') return true; } return false; } // Function to implement BFS static int bfs(Queue<qNode> q, boolean[][] visited, char[][] arr) { while (q.size() > 0) { qNode p = q.remove(); for (int idx = 0; idx < 4; idx++) { int x = p.x + dirx[idx]; int y = p.y + diry[idx]; // If next unvisited component // is land, return dist // till of p only if (isValid(x, y) && arr[x][y] == 'L' && !visited[x][y]) { return p.dist; } if (isValid(x, y) && arr[x][y] == 'W' && !visited[x][y]) { q.add(new qNode(x, y, p.dist + 1)); visited[x][y] = true; } } } return -1; } // To check if indices are in matrix static boolean isValid(int x, int y) { if (x < 0 || y < 0 || x >= R || y >= C) return false; return true; } // Driver Code public static void main(String[] args) { char[][] arr = { { 'W', 'L', 'W' }, { 'W', 'W', 'W' }, { 'W', 'W', 'L' } }; // Function call int ans = minConversions(arr); System.out.println(ans); }} |
C#
// C# program to implement the approachusing System;using System.Collections.Generic;public class GFG { static int R; static int C; // A class to represent point and // dist from first island class qNode { public int x; public int y; public int dist; public qNode(int x, int y, int d) { this.x = x; this.y = y; this.dist = d; } } // Function to find minimum conversions static int minConversions(char[,] arr) { R = arr.Length; C = arr.GetLength(0); // Queue to be used in bfs Queue<qNode> q = new Queue<qNode>(); bool[,] visited = new bool[R,C]; bool flag = false; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i,j] == 'L') { // Visited first island // completely and at // same time maintaining // visited array and queue dfs(i, j, visited, q, arr); flag = true; break; } } // Breaking the nested loop // once first island found if (flag) break; } return bfs(q, visited, arr); } // Arrays to get the adjacent indices // from one index of thegrid static int[] dirx = { 0, 1, 0, -1 }; static int[] diry = { 1, 0, -1, 0 }; // Function to run DFS static void dfs(int i, int j, bool[,] visited, Queue<qNode> q, char[,] arr) { visited[i,j] = true; // Checking if it is border component if (isBorder(i, j, arr)) { q.Enqueue(new qNode(i, j, 0)); } // Calling dfs in all 4 directions for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && arr[x,y] == 'L' && !visited[x,y]) { dfs(x, y, visited, q, arr); } } } // Return true if surrounded by water // in any of 4 direction static bool isBorder(int i, int j, char[,] arr) { for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && arr[x,y] == 'W') return true; } return false; } // Function to implement BFS static int bfs(Queue<qNode> q, bool[,] visited, char[,] arr) { while (q.Count > 0) { qNode p = q.Dequeue(); for (int idx = 0; idx < 4; idx++) { int x = p.x + dirx[idx]; int y = p.y + diry[idx]; // If next unvisited component // is land, return dist // till of p only if (isValid(x, y) && arr[x,y] == 'L' && !visited[x,y]) { return p.dist; } if (isValid(x, y) && arr[x,y] == 'W' && !visited[x,y]) { q.Enqueue(new qNode(x, y, p.dist + 1)); visited[x,y] = true; } } } return -1; } // To check if indices are in matrix static bool isValid(int x, int y) { if (x < 0 || y < 0 || x >= R || y >= C) return false; return true; } // Driver Code public static void Main(String[] args) { char[,] arr = { { 'W', 'L', 'W' }, { 'W', 'W', 'W' }, { 'W', 'W', 'L' } }; // Function call int ans = minConversions(arr); Console.WriteLine(ans); }}// This code is contributed by shikhasingrajput |
Python3
from collections import deque#A class to represent point and dist from first islandclass qNode: def __init__(self, x, y, dist): self.x = x self.y = y self.dist = distdirx = [0, 1, 0, -1]diry = [1, 0, -1, 0]R = 0C = 0def isValid(x, y): if x < 0 or y < 0 or x >= R or y >= C: return False return Truedef isBorder(i, j, arr): for idx in range(4): x = i + dirx[idx] y = j + diry[idx] if isValid(x, y) and arr[x][y] == 'W': return True return Falsedef dfs(i, j, visited, q, arr): visited[i][j] = True if isBorder(i, j, arr): q.append(qNode(i, j, 0)) for idx in range(4): x = i + dirx[idx] y = j + diry[idx] if isValid(x, y) and arr[x][y] == 'L' and not visited[x][y]: dfs(x, y, visited, q, arr)def bfs(q, visited, arr): while q: p = q.popleft() for idx in range(4): x = p.x + dirx[idx] y = p.y + diry[idx] #If next unvisited component is land, return dist till of p only if isValid(x, y) and arr[x][y] == 'L' and not visited[x][y]: return p.dist if isValid(x, y) and arr[x][y] == 'W' and not visited[x][y]: q.append(qNode(x, y, 1 + p.dist)) visited[x][y] = True return -1def minConversions(arr): global R, C R = len(arr) C = len(arr[0]) q = deque() visited = [[False for j in range(C)] for i in range(R)] flag = False for i in range(R): for j in range(C): #Visited first island completely and at # same time maintaining visited array and queue if arr[i][j] == 'L': dfs(i, j, visited, q, arr) flag = True break if flag: break return bfs(q, visited, arr)#Creating the Gridarr = [['W', 'L', 'W'], ['W', 'W', 'W'], ['W', 'W', 'L']]print(minConversions(arr)) |
Javascript
class qNode { constructor(x, y, dist) { this.x = x; this.y = y; this.dist = dist; }}const dirx = [0, 1, 0, -1];const diry = [1, 0, -1, 0];let R = 0;let C = 0;function isValid(x, y) { if (x < 0 || y < 0 || x >= R || y >= C) { return false; } return true;}function isBorder(i, j, arr) { for (let idx = 0; idx < 4; idx++) { const x = i + dirx[idx]; const y = j + diry[idx]; if (isValid(x, y) && arr[x][y] === 'W') { return true; } } return false;}function dfs(i, j, visited, q, arr) { visited[i][j] = true; if (isBorder(i, j, arr)) { q.push(new qNode(i, j, 0)); } for (let idx = 0; idx < 4; idx++) { const x = i + dirx[idx]; const y = j + diry[idx]; if (isValid(x, y) && arr[x][y] === 'L' && !visited[x][y]) { dfs(x, y, visited, q, arr); } }}function bfs(q, visited, arr) { while (q.length > 0) { const p = q.shift(); for (let idx = 0; idx < 4; idx++) { const x = p.x + dirx[idx]; const y = p.y + diry[idx]; if (isValid(x, y) && arr[x][y] === 'L' && !visited[x][y]) { return p.dist; } if (isValid(x, y) && arr[x][y] === 'W' && !visited[x][y]) { q.push(new qNode(x, y, p.dist + 1)); visited[x][y] = true; } } } return -1;}function minConversions(arr) { R = arr.length; C = arr[0].length; const q = []; const visited = Array(R).fill().map(() => Array(C).fill(false)); let flag = false; for (let i = 0; i < R; i++) { for (let j = 0; j < C; j++) { if (arr[i][j] === 'L') { dfs(i, j, visited, q, arr); flag = true; break; } } if (flag) { break; } } return bfs(q, visited, arr);}const arr = [['W', 'L', 'W'], ['W', 'W', 'W'], ['W', 'W', 'L']];console.log(minConversions(arr));// This code is contributed by Prince Kumar |
Output
2
Time Complexity: O(N2), since we are using two nested loops to travel every cell thus the complexity of the algorithm is quadratic
Auxiliary Space: O(N2), since we are creating an extra visited array of size R*C
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
