Recuento mínimo de filas entre filas que contienen X e Y respectivamente

Posted on by Rudeus Greyrat

Dada una Grid de tamaño NxM y dos enteros X e Y , la tarea es contar el número mínimo de filas entre la fila que contiene X y la fila que contiene Y de tal manera que las filas adyacentes entre ellas tengan al menos un elemento en común. Se permiten varias apariciones de un número en la cuadrícula. En otras palabras, se dice que dos filas son adyacentes si tienen al menos un elemento en común.

Ejemplos:

Entrada: arr[][] = {{1, 2, 3}, {2, 5, 6}, {7, 8, 13}}, X = 1, Y = 6
Salida: 0
Explicación: X = 1 es presente en la fila 0 (considerando 0 – indexación) y Y = 6 está en la fila 2.
Ambas filas tienen ‘2’ en común, ambas son adyacentes y hay 0 filas en el medio.

Entrada: arr[][] = {{1, 2, 3}, {2, 5, 6}, {3, 7, 13}}, X = 2, Y = 6
Salida: 0
Explicación: Ambos números son en la misma fila.

Entrada: arr[][] = {{1, 2, 3}, {2, 5, 6}, {3, 7, 13}}, X = 2, Y = 8
Salida: -1
Explicación: No hay posible combinación de filas adyacentes entre la fila que contiene X y la fila que contiene Y.

Entrada: arr[][] = {{1, 2, 3, 21}, {1, 11, 12, 25}, {12, 13, 14, 7}, {3, 5, 6, 7}, { 6, 8, 9, 10}}, X = 1, Y = 9
Salida: 1
Explicación: Una posible combinación de filas adyacentes es 0 -> 1 -> 2 -> 3 -> 4 que tiene 3 filas adyacentes entre ellas. 
Otra forma posible 1 -> 2 -> 3 -> 4 que tiene 2 filas adyacentes entre ellas. 
La ruta que tiene filas mínimas sería 0 -> 4 -> 5 que tiene solo 1 fila en el medio.

 

Enfoque:   el problema dado se puede resolver usando la ruta más corta en un gráfico no ponderado que usa el algoritmo BFS .

  • Cree un gráfico no ponderado donde cada Node represente una fila.
  • Dos Nodes de este gráfico están conectados si comparten al menos 1 número común entre ellos.
    • Ejecute el bucle for externo desde i = 0 hasta N , donde N es el número de filas.
      • Ejecute un ciclo interno de j = i + 1 a N .
      • Conecte la fila ‘i’ y la fila ‘j’ si hay algo común en ambas filas.
  • Ahora el problema se reduce a encontrar el camino más corto desde el Node que tiene X hasta el Node que tiene Y.
  • Vuelva a ejecutar otro bucle anidado y almacene las filas que tienen X en una cola para usarlas para BFS. 
  • Además, al almacenar todas las filas que tienen Y, se usará para detectar si se alcanza o no el Node que tiene el número objetivo.
  • Si el Node actual en el recorrido BFS del gráfico tiene una Y, devuelva el número de aristas recorridas: 1.
  • Si BFS está en exceso, devuelve -1, no hay combinación posible de filas adyacentes entre ambas filas.

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;
 
// class to represent node in queue
class Node {
  public:
  int rowNo;
  int edgesTravelled;
  Node(int r, int e)
  {
    this->rowNo = r;
    this->edgesTravelled = e;
  }
};
 
// function to check connection b/w two rows
bool shareCommon(vector<int>& i, vector<int>& j)
{
  // adding all elements of larger array to hashset then
  // iterating other array
  set<int> row1;
  if (i.size() > j.size()) {
    for (int idx = 0; idx < i.size(); idx++) {
      row1.insert(i[idx]);
    }
    for (int idx = 0; idx < j.size(); idx++) {
      if (row1.count(j[idx]))
        return true;
    }
  }
  else {
    for (int idx = 0; idx < j.size(); idx++) {
      row1.insert(j[idx]);
    }
    for (int idx = 0; idx < i.size(); idx++) {
      if (row1.count(i[idx]))
        return true;
    }
  }
  return false;
}
 
void minRowsBetweenXY(vector<vector<int> >& arr, int X,
                      int Y)
{
  // No. of rows
  int N = arr.size();
  if (X == Y) {
    cout << 0;
    return;
  }
  // constructing graph:
  vector<vector<int> > graph(N);
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      // if row i and j share something in common then
      // connect row i and j
      if (shareCommon(arr[i], arr[j])) {
        graph[i].push_back(j);
        graph[j].push_back(i);
      }
    }
  }
 
  // queue for BFS
  queue<Node> q;
  // visited array for bfs
  vector<bool> visited(N, false);
 
  // Set to store rows having Y
  set<int> targetRows;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < arr[i].size(); j++) {
      if (arr[i][j] == Y) {
        targetRows.insert(i);
      }
      if (arr[i][j] == X && !visited[i]) {
        q.push(Node(i, 0));
        // q.add(new Node(i, 0));
        visited[i] = true;
      }
    }
  }
 
  // using bfs algorithm:
  while (q.size() > 0) {
    Node rm = q.front();
    q.pop();
 
    // if the removed node is in the target row then
    // return
    if (targetRows.count(rm.rowNo)) {
      if (rm.edgesTravelled == 0) {
        cout << 0;
        return;
      }
      cout << rm.edgesTravelled - 1;
      return;
    }
 
    // adding neighbouring nodes
    for (int nbr : graph[rm.rowNo]) {
      if (!visited[nbr]) {
        int edgesTravelledBeforeNbr
          = rm.edgesTravelled;
        q.push(
          Node(nbr, 1 + edgesTravelledBeforeNbr));
        visited[nbr] = true;
      }
    }
  }
  // if bfs over => path not possible
  cout << -1;
}
 
// Driver code
int main()
{
  vector<vector<int> > arr = { { 1, 2, 3, 21 },
                              { 1, 11, 12, 25 },
                              { 12, 13, 14, 7 },
                              { 3, 5, 6, 7 },
                              { 6, 8, 9, 10 } };
  int X = 1;
  int Y = 9;
  minRowsBetweenXY(arr, X, Y);
  return 0;
}
 
// This code is contributed by abhishekghoshindia.

Java

// Java program to find minimum adjacent
// rows between rows containing X and Y
import java.util.*;
 
class GFG {
    static void minRowsBetweenXY(int[][] arr,
                                 int X, int Y)
    {
        // No. of rows
        int N = arr.length;
 
        if (X == Y) {
            System.out.println(0);
            return;
        }
 
        // constructing graph:
        ArrayList<ArrayList<Integer> > graph
            = new ArrayList<ArrayList<Integer> >();
        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                // if row i and j share
                // something in common
                // then connect row i and j
                if (shareCommon(arr[i], arr[j])) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }
 
        // queue fo BFS
        Queue<Node> q = new ArrayDeque<>();
        // visited array for bfs
        boolean[] visited = new boolean[N];
 
        // hashset to store rows
        // having Y
        HashSet<Integer> targetRows = new HashSet<>();
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == Y) {
                    targetRows.add(i);
                }
                if (arr[i][j] == X && !visited[i]) {
                    q.add(new Node(i, 0));
                    visited[i] = true;
                }
            }
        }
 
        // using bfs algorithm:
        while (q.size() > 0) {
            Node rm = q.remove();
 
            // if the removed node is in
            // the target row then return:
            if (targetRows.contains(rm.rowNo)) {
                if (rm.edgesTravelled == 0) {
                    System.out.println(0);
                    return;
                }
                System.out.println(
                    rm.edgesTravelled - 1);
                return;
            }
 
            // adding neighbouring nodes
            for (Integer nbr : graph.get(rm.rowNo)) {
                if (!visited[nbr]) {
                    int edgesTravelledBeforeNbr
                        = rm.edgesTravelled;
                    q.add(new Node(
                        nbr,
                        edgesTravelledBeforeNbr + 1));
                    visited[nbr] = true;
                }
            }
        }
        // if bfs over
        // => path not possible
        System.out.println(-1);
    }
 
    // function to check connection b/w
    // two rows
    static boolean shareCommon(int[] i, int[] j)
    {
        // adding all elements
        // of larger array to hashset
        // then iterating other array
        HashSet<Integer> row1 = new HashSet<>();
        if (i.length > j.length) {
            for (int idx = 0; idx < i.length; idx++) {
                row1.add(i[idx]);
            }
            for (int idx = 0; idx < j.length; idx++) {
                if (row1.contains(j[idx]))
                    return true;
            }
        }
        else {
            for (int idx = 0; idx < j.length; idx++) {
                row1.add(j[idx]);
            }
            for (int idx = 0; idx < i.length; idx++) {
                if (row1.contains(i[idx]))
                    return true;
            }
        }
        return false;
    }
 
    // class to represent node in queue
    static class Node {
        int rowNo;
        int edgesTravelled;
        Node(int r, int e)
        {
            this.rowNo = r;
            this.edgesTravelled = e;
        }
    }
 
    // driver code
    public static void main(String[] args)
    {
        int[][] arr = { { 1, 2, 3, 21 },
                        { 1, 11, 12, 25 },
                        { 12, 13, 14, 7 },
                        { 3, 5, 6, 7 },
                        { 6, 8, 9, 10 } };
        int X = 1;
        int Y = 9;
        minRowsBetweenXY(arr, X, Y);
    }
}

C#

// C# program to find minimum adjacent
// rows between rows containing X and Y
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // class to represent node in queue
  public class Node {
    public  int rowNo;
    public  int edgesTravelled;
    public  Node(int r, int e)
    {
      this.rowNo = r;
      this.edgesTravelled = e;
    }
  }
  public static int[] GetRow(int[,] matrix, int row)
  {
    var rowLength = matrix.GetLength(1);
    var rowVector = new int[rowLength];
 
    for (var i = 0; i < rowLength; i++)
      rowVector[i] = matrix[row, i];
 
    return rowVector;
  }
  static void minRowsBetweenXY(int[,] arr,
                               int X, int Y)
  {
    // No. of rows
    int N = arr.GetLength(0);
 
    if (X == Y) {
      Console.WriteLine(0);
      return;
    }
 
    // constructing graph:
    List<List<int> > graph
      = new List<List<int> >();
    for (int i = 0; i < N; i++) {
      graph.Add(new List<int>());
    }
 
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        // if row i and j share
        // something in common
        // then connect row i and j
        int[] t1 = GetRow(arr,i);
        int[] t2 = GetRow(arr,j);
        if (shareCommon(t1,t2)) {
          graph[i].Add(j);
          graph[j].Add(i);
        }
      }
    }
 
    // queue fo BFS
    List<Node> q = new List<Node>();
    // visited array for bfs
    bool[] visited = new bool[N];
 
    // hashset to store rows
    // having Y
    HashSet<int> targetRows = new HashSet<int>();
 
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < arr.GetLength(1); j++) {
        if (arr[i,j] == Y) {
          targetRows.Add(i);
        }
        if (arr[i,j] == X && !visited[i]) {
          q.Add(new Node(i, 0));
          visited[i] = true;
        }
      }
    }
 
    // using bfs algorithm:
    while (q.Count > 0) {
      Node rm = q[0];
      q.RemoveAt(0);
 
      // if the removed node is in
      // the target row then return:
      if (targetRows.Contains(rm.rowNo)) {
        if (rm.edgesTravelled == 0) {
          Console.WriteLine(0);
          return;
        }
        Console.WriteLine(
          rm.edgesTravelled - 1);
        return;
      }
 
      // adding neighbouring nodes
      foreach (int nbr in graph[rm.rowNo]) {
        if (!visited[nbr]) {
          int edgesTravelledBeforeNbr
            = rm.edgesTravelled;
          q.Add(new Node(
            nbr,
            edgesTravelledBeforeNbr + 1));
          visited[nbr] = true;
        }
      }
    }
    // if bfs over
    // => path not possible
    Console.WriteLine(-1);
  }
 
  // function to check connection b/w
  // two rows
  static bool shareCommon(int[] i, int[] j)
  {
    // adding all elements
    // of larger array to hashset
    // then iterating other array
    HashSet<int> row1 = new HashSet<int>();
    if (i.Length > j.Length) {
      for (int idx = 0; idx < i.Length; idx++) {
        row1.Add(i[idx]);
      }
      for (int idx = 0; idx < j.Length; idx++) {
        if (row1.Contains(j[idx]))
          return true;
      }
    }
    else {
      for (int idx = 0; idx < j.Length; idx++) {
        row1.Add(j[idx]);
      }
      for (int idx = 0; idx < i.Length; idx++) {
        if (row1.Contains(i[idx]))
          return true;
      }
    }
    return false;
  }
 
 
  // driver code
  public static void Main(String[] args)
  {
    int[,] arr = { { 1, 2, 3, 21 },
                  { 1, 11, 12, 25 },
                  { 12, 13, 14, 7 },
                  { 3, 5, 6, 7 },
                  { 6, 8, 9, 10 } };
    int X = 1;
    int Y = 9;
    minRowsBetweenXY(arr, X, Y);
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
    // Javascript code to implement the approach
 
    // class to represent node in queue
    class Node {
        constructor(r, e)
        {
            this.rowNo = r;
            this.edgesTravelled = e;
        }
    }
 
    // function to check connection b/w two rows
    function shareCommon(i, j)
    {
        // adding all elements of larger array to hashset then
        // iterating other array
        var row1 = new Set()
        if (i.length > j.length) {
            for (let idx = 0; idx < i.length; idx++) {
                row1.add(i[idx])
            }
            for (let idx = 0 ; idx < j.length ; idx++) {
                if (row1.has(j[idx])){
                    return true
                }
            }
        }
        else {
            for (let idx = 0; idx < j.length; idx++) {
                row1.add(j[idx]);
            }
            for (let idx = 0; idx < i.length; idx++) {
                if (row1.has(i[idx])){
                    return true
                }
            }
        }
        return false;
    }
 
    function minRowsBetweenXY(arr, X, Y)
    {
        // No. of rows
        let N = arr.length;
        if (X == Y) {
            console.log(0)
            return;
        }
        // constructing graph:
        var graph = Array(N)
        for(let i = 0 ; i < N ; i++){
            graph[i] = Array()
        }
 
        for (let i = 0; i < N; i++) {
            for (let j = i + 1; j < N; j++) {
                // if row i and j share something in common then
                // connect row i and j
                if (shareCommon(arr[i], arr[j])) {
                    graph[i].push(j);
                    graph[j].push(i);
                }
            }
        }
 
        // queue for BFS
        var q = Array()
        // visited array for bfs
        var visited = Array(N);
        for(let i = 0 ; i < N ; i++){
            visited[i] = false
        }
 
        // Set to store rows having Y
        var targetRows = new Set()
 
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == Y) {
                    targetRows.add(i)
                }
                if (arr[i][j] == X && !visited[i]) {
                    q.push(new Node(i, 0))
                    // q.add(new Node(i, 0));
                    visited[i] = true
                }
            }
        }
 
        // using bfs algorithm:
        while (q.length > 0) {
            var rm = q[0]
            q.shift()
 
            // if the removed node is in the target row then
            // return
            if (targetRows.has(rm.rowNo)) {
                if (rm.edgesTravelled == 0) {
                    console.log(0)
                    return;
                }
                console.log(rm.edgesTravelled - 1)
                return;
            }
 
            // adding neighbouring nodes
            for(let i = 0 ; i < graph[rm.rowNo].length ; i++){
                var nbr = graph[rm.rowNo][i]
                if (!visited[nbr]) {
                    let edgesTravelledBeforeNbr = rm.edgesTravelled;
                    q.push(new Node(nbr, 1 + edgesTravelledBeforeNbr));
                    visited[nbr] = true;
                }
            }
        }
        // if bfs over => path not possible
        console.log(-1)
    }
 
    // Driver code
    var arr = [ [ 1, 2, 3, 21 ],
                [ 1, 11, 12, 25 ],
                [ 12, 13, 14, 7 ],
                [ 3, 5, 6, 7 ],
                [ 6, 8, 9, 10 ]
            ];
 
    var X = 1;
    var Y = 9;
    minRowsBetweenXY(arr, X, Y);
     
    // This code is contributed by subhamgoyal2014.
 
</script>
Producción: 

1

 

Complejidad de Tiempo: O(N 2 + N * M)
Espacio Auxiliar: O(N 2 + M) 

Publicación traducida automáticamente

Artículo escrito por karandeep1234 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 *