Dada una cuadrícula[][] que contiene 0 y 1 , donde ‘0’ representa agua y ‘1’ representa tierra. Dado que una isla es un grupo de tierra (1s) rodeada de agua (0s) por todos lados.
La tarea es encontrar la distancia entre las dos islas más cercanas tal que:
- La distancia entre dos islas es el número mínimo de ‘0’ entre dos islas.
- Solo se permite el movimiento en 4 direcciones.
- Hay al menos 2 islas presentes en la cuadrícula.
Ejemplos:
Entrada: cuadrícula = {{1, 1, 0 , 1, 1},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 1, 1}}
Salida: 1
Explicación: Hay tres islas presentes en la cuadrícula.
El par de islas más cercano tiene solo 1 cero (en negrita en la cuadrícula de entrada) entre ellas.Entrada: cuadrícula = {{1, 0, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 0 , 0, 0, 0},
{0, 0 , 1, 1, 1}}
Salida: 2
Explicación: Hay tres islas presentes en la cuadrícula.
El par de islas más cercano tiene 2 ceros entre ellos (representado por un 0 en negrita en la cuadrícula de entrada).
En este caso, hay varios pares de islas que tienen una distancia de 2 entre ellas.
Enfoque ingenuo:
La intuición es encontrar la distancia mínima entre cada posible par de islas y devolver el mínimo de todas las distancias, usando DFS .
Para encontrar la distancia mínima entre 2 islas, siga los pasos a continuación:
- Guarde las coordenadas de cada isla por separado en Lista / vector.
- Cree una array booleana visitada para marcar si un elemento ha sido visitado.
- Recorra la cuadrícula y si un elemento es ‘1’ y no está visitado, llame a dfs para obtener todos los elementos correspondientes a la isla
- Guarda las coordenadas de esta isla en la lista.
- Encuentra la distancia mínima entre cada par de islas en la lista.
- Para cada par de islas de la lista, encuentre la distancia mínima entre ellas.
- la distancia entre 2 islas será la distancia mínima entre cada par de puntos en ambas islas.
- Para cada par de islas de la lista, encuentre la distancia mínima entre ellas.
- Devuelve el mínimo de todas las distancias entre islas.
A continuación se muestra el código para la implementación del enfoque:
C++
// CPP code to implement the approach
#include <bits/stdc++.h>
using namespace std;
int row;
int col;
// Function to check if
// a point is inside grid
bool isValid(int x, int y)
{
if (x < 0 || x >= row
|| y < 0 || y >= col)
return false;
return true;
}
int dirx[] = { 0, 1, 0, -1 };
int diry[] = { 1, 0, -1, 0 };
void dfs(vector <vector<bool>> &visited,
vector <vector<int>> &grid,
int i, int j,
vector <pair <int,int> > &island)
{
visited[i][j] = true;
island.push_back({i,j});
for (int idx = 0; idx < 4; idx++) {
int x = i + dirx[idx];
int y = j + diry[idx];
if (isValid(x, y)
&& grid[x][y] == 1
&& !visited[x][y]) {
dfs(visited, grid, x, y, island);
}
}
}
// Function to find and
// store all islands in list
vector <vector <pair <int,int> > >
findIslands(vector <vector<int>> &grid)
{
vector <vector <bool>> visited(row,vector <bool> (col,false));
vector <vector <pair <int,int> > > list;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1
&& !visited[i][j]) {
vector <pair <int,int> > island;
dfs(visited, grid, i,
j, island);
list.push_back(island);
}
}
}
return list;
}
// Function to find min distance
// between 2 islands
int findDistance(vector <pair <int,int> > &island1,
vector <pair <int,int> > &island2)
{
int dist = INT_MAX;
for (int i = 0; i < island1.size();
i++) {
pair <int,int> point1 = island1[i];
for (int j = 0; j < island2.size();
j++) {
pair <int,int> point2 = island2[j];
int distp1p2
= abs(point1.first - point2.first)
+ abs(point1.second - point2.second)
- 1;
dist = min(dist, distp1p2);
}
}
return dist;
}
// Function to find closest distance
void closestDistance(vector <vector<int>> &grid)
{
row = grid.size();
col = grid[0].size();
// List of coordinates
// of all the islands
vector <vector<pair <int,int>> > list
= findIslands(grid);
// Number of islands
int n = list.size();
// Variable to store
// minimum of all distances
int ans = INT_MAX;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
vector <pair <int,int> > island1
= list[i];
vector <pair <int,int> > island2
= list[j];
int dist = findDistance(island1,
island2);
ans = min(dist, ans);
}
}
cout<<ans<<endl;
}
int main(){
vector <vector <int>> grid = { { 1, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1 } };
closestDistance(grid);
return 0;
}
// This code is contributed by Sachin Sahara (sachin801)
Java
// Java code to implement the approach
import java.util.*;
class GFG {
static int row;
static int col;
// A class to represent coordinates of
// element in matrix
static class Pair {
int x;
int y;
Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Function to find closest distance
static void closestDistance(int[][] grid)
{
row = grid.length;
col = grid[0].length;
// List of coordinates
// of all the islands
ArrayList<ArrayList<Pair> > list
= findIslands(grid);
// Number of islands
int n = list.size();
// Variable to store
// minimum of all distances
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
ArrayList<Pair> island1
= list.get(i);
ArrayList<Pair> island2
= list.get(j);
int dist = findDistance(island1,
island2);
ans = Math.min(dist, ans);
}
}
System.out.println(ans);
}
// Function to find and
// store all islands in list
static ArrayList<ArrayList<Pair> >
findIslands(int[][] grid)
{
boolean[][] visited
= new boolean[row][col];
ArrayList<ArrayList<Pair> > list
= new ArrayList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1
&& !visited[i][j]) {
ArrayList<Pair> island
= new ArrayList<>();
dfs(visited, grid, i,
j, island);
list.add(island);
}
}
}
return list;
}
// Function to find min distance
// between 2 islands
static int findDistance(ArrayList<Pair> island1,
ArrayList<Pair> island2)
{
int dist = Integer.MAX_VALUE;
for (int i = 0; i < island1.size();
i++) {
Pair point1 = island1.get(i);
for (int j = 0; j < island2.size();
j++) {
Pair point2 = island2.get(j);
int distp1p2
= Math.abs(point1.x - point2.x)
+ Math.abs(point1.y - point2.y)
- 1;
dist = Math.min(dist, distp1p2);
}
}
return dist;
}
static int[] dirx = { 0, 1, 0, -1 };
static int[] diry = { 1, 0, -1, 0 };
static void dfs(boolean[][] visited,
int[][] grid,
int i, int j,
ArrayList<Pair> island)
{
visited[i][j] = true;
island.add(new Pair(i, j));
for (int idx = 0; idx < 4; idx++) {
int x = i + dirx[idx];
int y = j + diry[idx];
if (isValid(x, y)
&& grid[x][y] == 1
&& !visited[x][y]) {
dfs(visited, grid, x, y, island);
}
}
}
// Function to check if
// a point is inside grid
static boolean isValid(int x, int y)
{
if (x < 0 || x >= row
|| y < 0 || y >= col)
return false;
return true;
}
// Driver code
public static void main(String[] args)
{
int[][] grid = { { 1, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1 } };
closestDistance(grid);
}
}
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG {
static int row;
static int col;
// A class to represent coordinates of
// element in matrix
class Pair {
public int x;
public int y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Function to find closest distance
static void closestDistance(int[,] grid)
{
row = grid.GetLength(0);
col = grid.GetLength(1);
// List of coordinates
// of all the islands
List<List<Pair> > list
= findIslands(grid);
// Number of islands
int n = list.Count;
// Variable to store
// minimum of all distances
int ans = int.MaxValue;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
List<Pair> island1
= list[i];
List<Pair> island2
= list[j];
int dist = findDistance(island1,
island2);
ans = Math.Min(dist, ans);
}
}
Console.WriteLine(ans);
}
// Function to find and
// store all islands in list
static List<List<Pair> >
findIslands(int[,] grid)
{
bool[,] visited
= new bool[row,col];
List<List<Pair> > list
= new List<List<Pair>>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i,j] == 1
&& !visited[i,j]) {
List<Pair> island
= new List<Pair>();
dfs(visited, grid, i,
j, island);
list.Add(island);
}
}
}
return list;
}
// Function to find min distance
// between 2 islands
static int findDistance(List<Pair> island1,
List<Pair> island2)
{
int dist = int.MaxValue;
for (int i = 0; i < island1.Count;
i++) {
Pair point1 = island1[i];
for (int j = 0; j < island2.Count;
j++) {
Pair point2 = island2[j];
int distp1p2
= Math.Abs(point1.x - point2.x)
+ Math.Abs(point1.y - point2.y)
- 1;
dist = Math.Min(dist, distp1p2);
}
}
return dist;
}
static int[] dirx = { 0, 1, 0, -1 };
static int[] diry = { 1, 0, -1, 0 };
static void dfs(bool[,] visited,
int[,] grid,
int i, int j,
List<Pair> island)
{
visited[i,j] = true;
island.Add(new Pair(i, j));
for (int idx = 0; idx < 4; idx++) {
int x = i + dirx[idx];
int y = j + diry[idx];
if (isValid(x, y)
&& grid[x,y] == 1
&& !visited[x,y]) {
dfs(visited, grid, x, y, island);
}
}
}
// Function to check if
// a point is inside grid
static bool isValid(int x, int y)
{
if (x < 0 || x >= row
|| y < 0 || y >= col)
return false;
return true;
}
// Driver code
public static void Main(String[] args)
{
int[,] grid = { { 1, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1 } };
closestDistance(grid);
}
}
// This code is contributed by 29AjayKumar
Javascript
// Javascript code to implement the approach
var row, col;
// A class to represent coordinates of
// element in matrix
class Pair{
constructor(x, y)
{
this.x = x;
this.y = y;
}
}
// Function to find closest distance
function closestDistance(grid)
{
row = grid.length;
col = grid[0].length;
// List of coordinates
// of all the islands
var list = findIslands(grid);
// Number of islands
n = list.length;
// Variable to store
// minimum of all distances
ans = Number.MAX_SAFE_INTEGER;
for (let i = 0 ; i < n - 1 ; i++) {
for (let j = i + 1 ; j < n ; j++) {
island1 = list[i];
island2 = list[j];
dist = findDistance(island1, island2);
ans = Math.min(dist, ans);
}
}
console.log(ans);
}
// Function to find and
// store all islands in list
function findIslands(grid)
{
var visited = new Array(row);
for(let i = 0 ; i < row ; i++){
visited[i] = new Array(col)
for(let j = 0 ; j < col ; j++){
visited[i][j] = false
}
}
var list = new Array();
for (let i = 0 ; i < row ; i++) {
for (let j = 0 ; j < col ; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
var island = new Array()
dfs(visited, grid, i, j, island)
list.push(island)
}
}
}
return list
}
// Function to find min distance
// between 2 islands
function findDistance(island1, island2)
{
var dist = Number.MAX_SAFE_INTEGER;
for (let i = 0 ; i < island1.length ; i++) {
var point1 = island1[i];
for (let j = 0 ; j < island2.length ; j++) {
var point2 = island2[j];
var distp1p2 = Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y) - 1;
dist = Math.min(dist, distp1p2);
}
}
return dist;
}
var dirx = [ 0, 1, 0, -1 ];
var diry = [ 1, 0, -1, 0 ];
function dfs(visited, grid, i, j, island)
{
visited[i][j] = true;
island.push(new Pair(i, j));
for (let idx = 0; idx < 4; idx++) {
var x = i + dirx[idx];
var y = j + diry[idx];
if (isValid(x, y) && grid[x][y] == 1 && !visited[x][y]) {
dfs(visited, grid, x, y, island);
}
}
}
// Function to check if
// a point is inside grid
function isValid(x, y)
{
if (x < 0 || x >= row || y < 0 || y >= col){
return false;
}
return true;
}
// Driver code
var grid = [ [ 1, 0, 0, 0, 1 ],
[ 1, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 1, 1 ] ];
closestDistance(grid);
// This code is contributed by subhamgoyal2014.
Producción
2
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente:
La idea es que, en lugar de encontrar la distancia entre cada par de islas desde el enfoque ingenuo, optimice la tarea utilizando técnicas transversales de búsqueda primero en profundidad y búsqueda primero en amplitud para operaciones individuales, como se menciona a continuación:
- Primero encuentre todas las islas en la Cuadrícula usando DFS
- Luego encuentre el par de islas de distancia mínima entre estos, usando BFS.
Siga los pasos para resolver el problema utilizando el enfoque eficiente anterior:
- Cree dos arrays 2d ‘visitado’ y ‘distancia’ inicializadas por 0. La array de distancia será para almacenar la distancia a la isla más cercana.
- Atraviese la cuadrícula y si un elemento es ‘1’ , llame a dfs para marcar el elemento correspondiente en la array visitada con cualquier número que no sea 0.
- Marque cada isla en la array visitada con números diferentes.
- Mientras realiza el recorrido de dfs , agregue simultáneamente el Node que representa este elemento en la cola que se usará en bfs .
- Use la cola creada en los pasos anteriores para el cruce de bfs y expanda cada isla nivel por nivel.
- si el elemento vecino en la cuadrícula no está marcado como visitado, márquelo como visitado con el mismo número que el del Node actual en la array visitada.
- Almacene la distancia de {Node actual + 1} en la array de distancia para el elemento vecino no visitado.
- de lo contrario, si el elemento vecino en la cuadrícula ya está marcado como visitado con algún número que no sea el del Node actual en la array visitada.
- distancia de retorno del elemento actual + distancia del elemento vecino.
- si el elemento vecino en la cuadrícula no está marcado como visitado, márquelo como visitado con el mismo número que el del Node actual en la array visitada.
A continuación se muestra el código para la implementación del enfoque:
C++
// CPP code to implement the approach
#include <bits/stdc++.h>
using namespace std;
int row;
int col;
struct Pair {
int x;
int y;
int identity;
Pair(int x, int y, int identity)
{
this->x = x;
this->y = y;
this->identity = identity;
}
};
// Function to check if
// a point is inside grid
bool isValid(int x, int y)
{
if (x < 0 || x >= row
|| y < 0 || y >= col)
return false;
return true;
}
int dirx[] = { 0, 1, 0, -1 };
int diry[] = { 1, 0, -1, 0 };
// Dfs function to add all island elements
// In queue and marking them visited with id
void dfs(vector <vector<int>> &grid, vector <vector<int>> &visited,
queue <Pair> &q, int i,
int j, int id)
{
visited[i][j] = id;
Pair p1(i, j, id);
q.push(p1);
for (int idx = 0; idx < 4; idx++) {
int x = i + dirx[idx];
int y = j + diry[idx];
if (isValid(x, y) && grid[x][y] == 1
&& visited[x][y] == 0) {
dfs(grid, visited, q, x, y, id);
}
}
}
// Bfs function to expand every island and
// Maintaining distance array
int bfs(vector <vector<int>> &grid, vector <vector<int>> & visited,
vector <vector<int>> & distance, queue<Pair> &q)
{
while ( !q.empty() ) {
Pair p = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = p.x + dirx[i];
int y = p.y + diry[i];
if (isValid(x, y)
&& visited[x][y] == 0) {
q.push(Pair(x, y,
p.identity));
distance[x][y]
= distance[p.x][p.y] + 1;
visited[x][y]
= p.identity;
}
else if (isValid(x, y)
&& visited[x][y] != 0
&& visited[x][y]
!= visited[p.x][p.y]) {
return distance[x][y]
+ distance[p.x][p.y];
}
}
}
return -1;
}
// Function to find closest distance
void closestDistance(vector <vector <int>> &grid)
{
row = grid.size();
col = grid[0].size();
int id = 1;
queue <Pair> q;
vector <vector <int>> visited(row,vector <int>(col,0));
// Distance array to store distance
// From nearest island
vector <vector <int>> distance(row,vector <int>(col,0));
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1
&& visited[i][j] == 0) {
dfs(grid, visited, q, i, j, id);
id++;
}
}
}
// To store minimal distance
// b/w closest islands
int ans = bfs(grid, visited, distance, q);
cout << ans << endl;
}
int main(){
vector <vector <int>> grid = { { 1, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1 } };
closestDistance(grid);
return 0;
}
// This code is contributed by Sachin Sahara (sachin801)
Java
// Java code to implement the approach
import java.util.*;
class GFG {
static int row;
static int col;
// A class to represent coordinates of
// element in matrix
static class Pair {
int x;
int y;
int identity;
Pair(int x, int y, int identity)
{
this.x = x;
this.y = y;
this.identity = identity;
}
}
// Function to find closest distance
static void closestDistance(int[][] grid)
{
row = grid.length;
col = grid[0].length;
int id = 1;
Queue<Pair> q = new ArrayDeque<Pair>();
int[][] visited = new int[row][col];
// Distance array to store distance
// From nearest island
int[][] distance = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1
&& visited[i][j] == 0) {
dfs(grid, visited, q, i, j, id);
id++;
}
}
}
// To store minimal distance
// b/w closest islands
int ans = bfs(grid, visited, distance, q);
System.out.println(ans);
}
static int[] dirx = { 0, 1, 0, -1 };
static int[] diry = { 1, 0, -1, 0 };
// Dfs function to add all island elements
// In queue and marking them visited with id
static void dfs(int[][] grid, int[][] visited,
Queue<Pair> q, int i,
int j, int id)
{
visited[i][j] = id;
q.add(new Pair(i, j, id));
for (int idx = 0; idx < 4; idx++) {
int x = i + dirx[idx];
int y = j + diry[idx];
if (isValid(x, y) && grid[x][y] == 1
&& visited[x][y] == 0) {
dfs(grid, visited, q, x, y, id);
}
}
}
// Bfs function to expand every island and
// Maintaining distance array
static int bfs(int[][] grid, int[][] visited,
int[][] distance, Queue<Pair> q)
{
while (q.size() != 0) {
Pair p = q.remove();
for (int i = 0; i < 4; i++) {
int x = p.x + dirx[i];
int y = p.y + diry[i];
if (isValid(x, y)
&& visited[x][y] == 0) {
q.add(new Pair(x, y,
p.identity));
distance[x][y]
= distance[p.x][p.y] + 1;
visited[x][y]
= p.identity;
}
else if (isValid(x, y)
&& visited[x][y] != 0
&& visited[x][y]
!= visited[p.x][p.y]) {
return distance[x][y]
+ distance[p.x][p.y];
}
}
}
return -1;
}
// Function to check if point
// Is inside grid
static boolean isValid(int x, int y)
{
if (x < 0 || x >= row
|| y < 0 || y >= col)
return false;
return true;
}
// Driver Code
public static void main(String[] args)
{
int[][] grid = { { 1, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1 } };
closestDistance(grid);
}
}
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