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 basado en el algoritmo Floodfill: El enfoque basado en el algoritmo Floodfill se analiza en el Conjunto 1 de este artículo.
Enfoque eficiente: este problema se puede resolver mediante el uso de algoritmos DFS y BFS . La idea es usar DFS para encontrar todos los componentes terrestres de una isla y agregar simultáneamente los componentes terrestres limítrofes a la cola que se usará en BFS para expandirse y encontrar el camino más corto a la segunda isla. Siga los pasos que se mencionan a continuación para resolver el problema:
- Use un bucle anidado para encontrar la primera aparición de ‘L’ en arr[][] .
- Llame a DFS para encontrar todos los elementos de esta isla y si alguna ‘L’ es un elemento de borde (es decir, rodeado por ‘W’ en al menos un lado) también agréguelo en una cola .
- Expanda esta isla usando el algoritmo BFS usando la cola y la array visitada creada durante la llamada DFS .
- En cada nivel aumenta la distancia en 1 .
- Al usar BFS , encuentre el camino más pequeño desde el borde de una isla hasta la segunda isla.
- Si el siguiente componente que se agregará a la cola es ‘L’ , devuelva la distancia hasta ahora.
Nota: Todos los elementos de la primera isla también se pueden encontrar utilizando el algoritmo BFS .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// A class to represent point and dist from first island
class 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
// grid
int dirx[4] = { 0, 1, 0, -1 };
int diry[4] = { 1, 0, -1, 0 };
// Global variables for size of array
int R, C;
// To check if indices are in matrix
bool 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 direction
bool 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 DFS
void 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 BFS
int 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 conversions
int 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 code
int 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 approach
import java.util.*;
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 approach
using 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
Producción
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por karandeep1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA