Dada una cuadrícula 2D arr[][] de ‘W’ y ‘L’ donde ‘W’ denota agua y ‘L’ denota tierra, la tarea es encontrar la cantidad mínima de componentes de agua ‘W’ que deben cambiarse a tierra componente ‘L’ para que dos islas queden conectadas.
Una isla es el conjunto de ‘L’ conexas .
Nota: Solo puede haber dos islas separadas.
Ejemplos:
Entrada: arr[][] = {{‘W’, ‘L’}, {‘L’, ‘W’}};
Salida: 1
Explicación:
Para el conjunto dado de islas, si cambiamos arr[1][1] a ‘W’, entonces, el conjunto de todas las islas está conectado.
Por lo tanto, el número mínimo de ‘W’ debe cambiarse a ‘L’ es 1.Entrada: arr[][] = {{‘W’, ‘L’, ‘W’}, {‘W’, ‘W’, ‘W’}, {‘W’, ‘W’, ‘L’} }
Salida: 2
Enfoque: Este problema se puede resolver usando el algoritmo Floodfill . A continuación se muestran los pasos:
- Use el algoritmo Floodfill para el primer conjunto de islas conectadas y haga que todas las islas sean visitadas y almacene las coordenadas en un hash (por ejemplo, hash1 ).
- Use el algoritmo Floodfill para el segundo conjunto de islas conectadas y haga que todas las islas sean visitadas y almacene las coordenadas en un segundo hash (por ejemplo, hash2 ).
- La diferencia mínima entre las coordenadas almacenadas en ambos hash es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Determine the distance between two
// coordinates
int dist(pair<int, int>& p1,
pair<int, int>& p2)
{
return abs(p1.first - p2.first)
+ abs(p2.second - p1.second) - 1;
}
// Function to implement floodfill algorithm
void floodfill(set<pair<int, int> >& hash,
int i, int j,
vector<vector<char> >& A)
{
// Base Case
if (i < 0 || i >= A.size() || j < 0
|| j >= A[0].size() || A[i][j] != 'L') {
return;
}
// Mark the current node visited
A[i][j] = 'V';
// Store the coordinates of in the
// hash set
hash.insert(make_pair(i, j));
// Recursively iterate for the next
// four directions
floodfill(hash, i - 1, j, A);
floodfill(hash, i + 1, j, A);
floodfill(hash, i, j - 1, A);
floodfill(hash, i, j + 1, A);
}
// Function to find the minimum 'W' to flipped
void findMinimumW(vector<vector<char> >& A)
{
// Base Case
if (A.size() == 0)
return;
// Two sets to store the coordinates of
// connected island
set<pair<int, int> > hash1, hash2;
// Traversing the given grid[][]
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < A[0].size(); j++) {
// If an island is found
if (A[i][j] == 'L') {
// Floodfill Algorithm for
// the first island
if (hash1.empty()) {
floodfill(hash1, i, j, A);
}
// Floodfill Algorithm for
// the second island
if (hash2.empty()
&& !hash1.count({ i, j })) {
floodfill(hash2, i, j, A);
}
}
}
}
// To store the minimum count of 'W'
int ans = INT_MAX;
// Traverse both pairs of hashes
for (auto i : hash1) {
for (auto j : hash2) {
ans = min(ans, dist(i, j));
}
}
// Print the final answer
cout << ans << endl;
}
// Driver Code
int main()
{
// Given grid of land and water
vector<vector<char> > arr;
arr = { { 'W', 'L' }, { 'L', 'W' } };
// Function Call
findMinimumW(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Determine the distance between two
// coordinates
static int dist(Pair p1, Pair p2)
{
return Math.abs(p1.first - p2.first)
+ Math.abs(p2.second - p1.second) - 1;
}
// class Pair to represent coordinates
// of elements in grid
static class Pair {
int first;
int second;
Pair(int f, int s)
{
this.first = f;
this.second = s;
}
}
// Function to implement floodfill algorithm
static void floodfill(HashSet<Pair> hash, int i, int j,
char[][] A)
{
// Base Case
if (i < 0 || i >= A.length || j < 0
|| j >= A[0].length || A[i][j] != 'L') {
return;
}
// Mark the current node visited
A[i][j] = 'V';
// Store the coordinates of in the
// hash set
hash.add(new Pair(i, j));
// Recursively iterate for the next
// four directions
floodfill(hash, i - 1, j, A);
floodfill(hash, i + 1, j, A);
floodfill(hash, i, j - 1, A);
floodfill(hash, i, j + 1, A);
}
// Function to find the minimum 'W' to flipped
static void findMinimumW(char[][] A)
{
// Base Case
if (A.length == 0)
return;
// Two sets to store the coordinates of
// connected island
HashSet<Pair> hash1 = new HashSet<>();
HashSet<Pair> hash2 = new HashSet<>();
// Traversing the given grid[][]
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
// If an island is found
if (A[i][j] == 'L') {
// Floodfill Algorithm for
// the first island
if (hash1.isEmpty()) {
floodfill(hash1, i, j, A);
}
// Floodfill Algorithm for
// the second island
if (hash2.isEmpty()
&& !hash1.contains(
new Pair(i, j))) {
floodfill(hash2, i, j, A);
}
}
}
}
// To store the minimum count of 'W'
int ans = Integer.MAX_VALUE;
// Traverse both pairs of hashes
for (Pair i : hash1) {
for (Pair j : hash2) {
ans = Math.min(ans, dist(i, j));
}
}
// Print the final answer
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
// Given grid of land and water
char[][] arr = { { 'W', 'L' }, { 'L', 'W' } };
// Function Call
findMinimumW(arr);
}
}
// This code is contributed by kdeepsingh2002
Python3
# Python3 program for the above approach import sys # Determine the distance between two # coordinates def dist(p1, p2): return (abs(p1[0] - p2[0]) + abs(p2[1] - p1[1]) - 1) # Function to implement floodfill algorithm def floodfill(hash, i, j, A): # Base Case if (i < 0 or i >= len(A) or j < 0 or j >= len(A[0]) or A[i][j] != 'L'): return hash, A # Mark the current node visited A[i][j] = 'V' # Store the coordinates of in the # hash set hash.add((i, j)) # Recursively iterate for the next # four directions hash, A = floodfill(hash, i - 1, j, A) hash, A = floodfill(hash, i + 1, j, A) hash, A = floodfill(hash, i, j - 1, A) hash, A = floodfill(hash, i, j + 1, A) return hash, A # Function to find the minimum 'W' to flipped def findMinimumW(A): # Base Case if (len(A) == 0): return set(), A # Two sets to store the coordinates of # connected island hash1 = set() hash2 = set() # Traversing the given grid[][] for i in range(len(A)): for j in range(len(A[0])): # If an island is found if (A[i][j] == 'L'): # Floodfill Algorithm for # the first island if (len(hash1) == 0): hash1, A = floodfill(hash1, i, j, A) # Floodfill Algorithm for # the second island if (len(hash2) == 0 and (i, j) not in hash1): hash2, A = floodfill(hash2, i, j, A) # To store the minimum count of 'W' ans = sys.maxsize # Traverse both pairs of hashes for i in hash1: for j in hash2: ans = min(ans, dist(i, j)) # Print the final answer print(ans) # Driver Code if __name__=='__main__': # Given grid of land and water arr = [] arr = [ [ 'W', 'L' ], [ 'L', 'W' ] ] # Function Call findMinimumW(arr) # This code is contributed by pratham76
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Determine the distance between two
// coordinates
static int dist(Pair p1, Pair p2)
{
return Math.Abs(p1.first - p2.first)
+ Math.Abs(p2.second - p1.second) - 1;
}
// class Pair to represent coordinates
// of elements in grid
class Pair {
public int first;
public int second;
public Pair(int f, int s)
{
this.first = f;
this.second = s;
}
}
// Function to implement floodfill algorithm
static void floodfill(HashSet<Pair> hash, int i, int j,
char[,] A)
{
// Base Case
if (i < 0 || i >= A.GetLength(0) || j < 0
|| j >= A.GetLength(1) || A[i,j] != 'L') {
return;
}
// Mark the current node visited
A[i,j] = 'V';
// Store the coordinates of in the
// hash set
hash.Add(new Pair(i, j));
// Recursively iterate for the next
// four directions
floodfill(hash, i - 1, j, A);
floodfill(hash, i + 1, j, A);
floodfill(hash, i, j - 1, A);
floodfill(hash, i, j + 1, A);
}
// Function to find the minimum 'W' to flipped
static void findMinimumW(char[,] A)
{
// Base Case
if (A.GetLength(0) == 0)
return;
// Two sets to store the coordinates of
// connected island
HashSet<Pair> hash1 = new HashSet<Pair>();
HashSet<Pair> hash2 = new HashSet<Pair>();
// Traversing the given grid[,]
for (int i = 0; i < A.GetLength(0); i++) {
for (int j = 0; j < A.GetLength(1); j++) {
// If an island is found
if (A[i,j] == 'L') {
// Floodfill Algorithm for
// the first island
if (hash1.Count==0) {
floodfill(hash1, i, j, A);
}
// Floodfill Algorithm for
// the second island
if (hash2.Count==0
&& !hash1.Contains(
new Pair(i, j))) {
floodfill(hash2, i, j, A);
}
}
}
}
// To store the minimum count of 'W'
int ans = int.MaxValue;
// Traverse both pairs of hashes
foreach (Pair i in hash1) {
foreach (Pair j in hash2) {
ans = Math.Min(ans, dist(i, j));
}
}
// Print the readonly answer
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given grid of land and water
char[,] arr = { { 'W', 'L' }, { 'L', 'W' } };
// Function Call
findMinimumW(arr);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Determine the distance between two
// coordinates
function dist(p1,p2)
{
return Math.abs(p1[0] - p2[0])
+ Math.abs(p2[1] - p1[1]) - 1;
}
// Function to implement floodfill algorithm
function floodfill(hash,i,j, A)
{
// Base Case
if (i < 0 || i >= A.length || j < 0
|| j >= A[0].length || A[i][j] != 'L') {
return;
}
// Mark the current node visited
A[i][j] = 'V';
// Store the coordinates of in the
// hash set
hash.add([i, j]);
// Recursively iterate for the next
// four directions
floodfill(hash, i - 1, j, A);
floodfill(hash, i + 1, j, A);
floodfill(hash, i, j - 1, A);
floodfill(hash, i, j + 1, A);
}
// Function to find the minimum 'W' to flipped
function findMinimumW(A)
{
// Base Case
if (A.length == 0)
return;
// Two sets to store the coordinates of
// connected island
let hash1 = new Set(), hash2 = new Set();
// Traversing the given grid[][]
for (let i = 0; i < A.length; i++) {
for (let j = 0; j < A[0].length; j++) {
// If an island is found
if (A[i][j] == 'L') {
// Floodfill Algorithm for
// the first island
if (hash1.size == 0) {
floodfill(hash1, i, j, A);
}
// Floodfill Algorithm for
// the second island
if (hash2.size == 0 && !hash1.has([ i, j ])) {
floodfill(hash2, i, j, A);
}
}
}
}
// To store the minimum count of 'W'
let ans = Number.MAX_VALUE;
// Traverse both pairs of hashes
for (let i of hash1) {
for (let j of hash2) {
ans = Math.min(ans, dist(i, j));
}
}
// Print the final answer
document.write(ans,"</br>");
}
// Driver Code
// Given grid of land and water
let arr = [ [ 'W', 'L' ], [ 'L', 'W' ] ];
// Function Call
findMinimumW(arr);
// This code is contributed by shinjanpatra
</script>
Producción:
1
Complejidad de Tiempo: O(N 4 ) Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por MohitSinha3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA