El camino más corto para que un ladrón llegue a la casa N evitando a los policías

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 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *