Dado un gráfico no ponderado y una array booleana A[ ] , donde si el i -ésimo índice de la array A[ ] denota si ese Node se puede visitar ( 0 ) o no ( 1 ). La tarea es encontrar el camino más corto para alcanzar (N – 1) el Node desde el Node 0 . Si no es posible llegar, imprima -1 .
Ejemplos:
Entrada: N = 5, A[] = {0, 1, 0, 0, 0}, Bordes = {{0, 1}, {0, 2}, {1, 4}, {2, 3}, { 3, 4}}
Salida: 3
Explicación: Hay dos caminos desde la casa 0 hasta la casa 4
- 0 → 1 → 4
- 0 →2 → 3 → 4
Dado que un policía está presente en la 1ª casa, el único camino que se puede elegir es el 2º camino.
Entrada: N = 4, A = {0, 1, 1, 0}, Bordes = {{0, 1}, {0, 2}, {1, 3}, {2, 3}}
Salida: -1
Enfoque: este problema es similar a encontrar el camino más corto en un gráfico no ponderado . Por lo tanto, el problema se puede resolver usando BFS .
Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa_desordenado , diga adj para almacenar los bordes. El borde (a, b) debe excluirse si hay un policía en el Node ao en el Node b .
- Inicialice una variable, pathLength = 0.
- Inicialice un vector del tipo de datos booleano , digamos visitado , para almacenar si un Node es visitado o no.
- Inicialice una array dist[0, 1, …., v-1] tal que dist[i] almacene la distancia del vértice i desde el vértice raíz
- Inicialice una cola y empuje el Node 0 en ella. Además, marque el Node 0 como visitado.
- Iterar mientras la cola no está vacía y el Node N – 1 no se visita, sacar el elemento frontal de la cola y empujar todos los elementos a la cola que tienen un borde desde el elemento frontal de la cola y no se visitan y aumentan la distancia de todos estos Nodes por 1 + dist[q.top()] .
- Si no se visita el Node (N – 1) , imprima -1 .
- De lo contrario, imprima la distancia de (N – 1) Node desde el Node raíz.
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;
// Function to create graph edges
// where node A and B can be visited
void createGraph(unordered_map<int, vector<int> >& adj,
int paths[][2], int A[], int N, int E)
{
// Visit all the connections
for (int i = 0; i < E; i++) {
// If a policeman is at any point of
// connection, leave that connection.
// Insert the connect otherwise.
if (!A[paths[i][0]] && !A[paths[i][1]]) {
adj[paths[i][0]].push_back(paths[i][1]);
}
}
}
// Function to find the shortest path
int minPath(int paths[][2], int A[],
int N, int E)
{
// If police is at either at
// the 1-st house or at N-th house
if (A[0] == 1 || A[N - 1] == 1)
// The thief cannot reach
// the N-th house
return -1;
// Stores Edges of graph
unordered_map<int, vector<int> > adj;
// Function call to store connections
createGraph(adj, paths, A, N, E);
// Stores whether node is
// visited or not
vector<int> visited(N, 0);
// Stores distances
// from the root node
int dist[N];
dist[0] = 0;
queue<int> q;
q.push(0);
visited[0] = 1;
// Visit all nodes that are
// currently in the queue
while (!q.empty()) {
int temp = q.front();
q.pop();
for (auto x : adj[temp]) {
// If current node is
// not visited already
if (!visited[x]) {
q.push(x);
visited[x] = 1;
dist[x] = dist[temp] + 1;
}
}
}
if (!visited[N - 1])
return -1;
else
return dist[N - 1];
}
// Driver Code
int main()
{
// N : Number of houses
// E: Number of edges
int N = 5, E = 5;
// Given positions
int A[] = { 0, 1, 0, 0, 0 };
// Given Paths
int paths[][2] = { { 0, 1 },
{ 0, 2 },
{ 1, 4 },
{ 2, 3 },
{ 3, 4 } };
// Function call
cout << minPath(paths, A, N, E);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to create graph edges
// where node A and B can be visited
static void
createGraph(HashMap<Integer, ArrayList<Integer> > adj,
int paths[][], int A[], int N, int E)
{
// Visit all the connections
for (int i = 0; i < E; i++) {
// If a policeman is at any point of
// connection, leave that connection.
// Insert the connect otherwise.
if (A[paths[i][0]] != 1
&& A[paths[i][1]] != 1) {
ArrayList<Integer> list = adj.getOrDefault(
paths[i][0], new ArrayList<>());
list.add(paths[i][1]);
adj.put(paths[i][0], list);
}
}
}
// Function to find the shortest path
static int minPath(int paths[][], int A[], int N, int E)
{
// If police is at either at
// the 1-st house or at N-th house
if (A[0] == 1 || A[N - 1] == 1)
// The thief cannot reach
// the N-th house
return -1;
// Stores Edges of graph
HashMap<Integer, ArrayList<Integer> > adj
= new HashMap<>();
// Function call to store connections
createGraph(adj, paths, A, N, E);
// Stores whether node is
// visited or not
boolean visited[] = new boolean[N];
// Stores distances
// from the root node
int dist[] = new int[N];
dist[0] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.addLast(0);
visited[0] = true;
// Visit all nodes that are
// currently in the queue
while (!q.isEmpty()) {
int temp = q.removeFirst();
for (int x : adj.getOrDefault(
temp, new ArrayList<>())) {
// If current node is
// not visited already
if (!visited[x]) {
q.addLast(x);
visited[x] = true;
dist[x] = dist[temp] + 1;
}
}
}
if (!visited[N - 1])
return -1;
else
return dist[N - 1];
}
// Driver Code
public static void main(String[] args)
{
// N : Number of houses
// E: Number of edges
int N = 5, E = 5;
// Given positions
int A[] = { 0, 1, 0, 0, 0 };
// Given Paths
int paths[][] = {
{ 0, 1 }, { 0, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 }
};
// Function call
System.out.print(minPath(paths, A, N, E));
}
}
// This code is contributed by Kingash.
Javascript
<script>
// Javascript program for the above approach
// Stores Edges of graph
var adj = new Map();
// Function to create graph edges
// where node A and B can be visited
function createGraph(paths, A, N, E)
{
// Visit all the connections
for (var i = 0; i < E; i++) {
// If a policeman is at any point of
// connection, leave that connection.
// Insert the connect otherwise.
if (!A[paths[i][0]] && !A[paths[i][1]]) {
if(adj.has(paths[i][0]))
{
var tmp = adj.get(paths[i][0]);
tmp.push(paths[i][1]);
adj.set(paths[i][0], tmp);
}
else
{
var tmp = new Array();
tmp.push(paths[i][1]);
adj.set(paths[i][0], tmp);
}
}
}
}
// Function to find the shortest path
function minPath(paths, A, N, E)
{
// If police is at either at
// the 1-st house or at N-th house
if (A[0] == 1 || A[N - 1] == 1)
// The thief cannot reach
// the N-th house
return -1;
// Function call to store connections
createGraph(paths, A, N, E);
// Stores whether node is
// visited or not
var visited = Array(N).fill(0);
// Stores distances
// from the root node
var dist = Array(N).fill(0);
dist[0] = 0;
var q = [];
q.push(0);
visited[0] = 1;
// Visit all nodes that are
// currently in the queue
while (q.length!=0) {
var temp = q[0];
q.pop();
if(adj.has(temp))
{
for (var x of adj.get(temp)) {
// If current node is
// not visited already
if (!visited[x]) {
q.push(x);
visited[x] = 1;
dist[x] = dist[temp] + 1;
}
}
}
}
if (!visited[N - 1])
return -1;
else
return dist[N - 1];
}
// Driver Code
// N : Number of houses
// E: Number of edges
var N = 5, E = 5;
// Given positions
var A = [0, 1, 0, 0, 0 ];
// Given Paths
var paths = [ [ 0, 1 ],
[ 0, 2 ],
[ 1, 4 ],
[ 2, 3 ],
[ 3, 4 ] ];
// Function call
document.write(minPath(paths, A, N, E));
// This code is contributed by itsok.
</script>
Producción:
3
Complejidad temporal: O (N + E)
Espacio auxiliar: O (N + E)
Publicación traducida automáticamente
Artículo escrito por sachinjain74754 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA