Encuentre movimientos mínimos para traer todos los elementos en una celda de una array

Dada una array mat[][] , par de índices X e Y , la tarea es encontrar el número de movimientos para llevar todos los elementos distintos de cero de la array a la celda dada en (X, Y)
 

Un movimiento consiste en mover un elemento en cualquier celda a sus cuatro celdas direccionales adyacentes, es decir, izquierda, derecha, arriba, abajo. 
 

Ejemplos: 
 

Entrada: mat[][] = {{1, 0}, {1, 0}}, X = 1, Y = 1 Salida: 3 
Explicación
Movimientos 
requeridos => 
Para índice (0, 0) => 2 
Para índice (1, 0) => 1 
Movimientos totales requeridos = 3
Entrada: mat[][] = {{1, 0, 1, 0}, {1, 1, 0, 1}, {0, 0, 1, 0 }}, X = 1, Y = 3 
Salida: 13 
 

Enfoque: la idea es atravesar la array y, para cada elemento distinto de cero de la array, encontrar la distancia de la celda actual (digamos (A, B) ) a la celda de destino (X, Y) de la array como: 
 

moves = abs(x - i) + abs(y - j)

La suma de todas las distancias por la fórmula anterior para todos los elementos distintos de cero es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation to find the
// minimum number of moves to
// bring all non-zero element
// in one cell of the matrix
 
#include <bits/stdc++.h>
using namespace std;
 
const int M = 4;
const int N = 5;
 
// Function to find the minimum
// number of moves to bring all
// elements in one cell of matrix
void no_of_moves(int Matrix[M][N],
                int x, int y)
{
 
    // Moves variable to store
    // the sum of number of moves
    int moves = 0;
 
    // Loop to count the number
    // of the moves
    for (int i = 0; i < M; i++) {
 
        for (int j = 0; j < N; j++) {
 
            // Condition to check that
            // the current cell is a
            // non-zero element
            if (Matrix[i][j] != 0) {
                moves += abs(x - i);
 
                moves += abs(y - j);
            }
        }
    }
 
    cout << moves << "\n";
}
 
// Driver Code
int main()
{
    // Coordinates of given cell
    int x = 3;
    int y = 2;
 
    // Given Matrix
    int Matrix[M][N] = { { 1, 0, 1, 1, 0 },
                        { 0, 1, 1, 0, 1 },
                        { 0, 0, 1, 1, 0 },
                        { 1, 1, 1, 0, 0 } };
 
    // Element to be moved
    int num = 1;
 
    // Function call
    no_of_moves(Matrix, x, y);
    return 0;
}

Java

// Java implementation to find the
// minimum number of moves to
// bring all non-zero element
// in one cell of the matrix
class GFG{
     
static int M = 4;
static int N = 5;
 
// Function to find the minimum
// number of moves to bring all
// elements in one cell of matrix
public static void no_of_moves(int[][] Matrix,
                               int x, int y)
{
     
    // Moves variable to store
    // the sum of number of moves
    int moves = 0;
 
    // Loop to count the number
    // of the moves
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
             
            // Condition to check that
            // the current cell is a
            // non-zero element
            if (Matrix[i][j] != 0)
            {
                moves += Math.abs(x - i);
                moves += Math.abs(y - j);
            }
        }
    }
    System.out.println(moves);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Coordinates of given cell
    int x = 3;
    int y = 2;
 
    // Given Matrix
    int[][] Matrix = { { 1, 0, 1, 1, 0 },
                       { 0, 1, 1, 0, 1 },
                       { 0, 0, 1, 1, 0 },
                       { 1, 1, 1, 0, 0 } };
 
    // Element to be moved
    int num = 1;
 
    // Function call
    no_of_moves(Matrix, x, y);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 implementation to find the
# minimum number of moves to
# bring all non-zero element
# in one cell of the matrix
M = 4
N = 5
 
# Function to find the minimum
# number of moves to bring all
# elements in one cell of matrix
def no_of_moves(Matrix, x, y):
 
    # Moves variable to store
    # the sum of number of moves
    moves = 0
 
    # Loop to count the number
    # of the moves
    for i in range(M):
        for j in range(N):
 
            # Condition to check that
            # the current cell is a
            # non-zero element
            if (Matrix[i][j] != 0):
                moves += abs(x - i)
                moves += abs(y - j)
 
    print(moves)
 
# Driver Code
if __name__ == '__main__':
   
    # Coordinates of given cell
    x = 3
    y = 2
 
    # Given Matrix
    Matrix = [ [ 1, 0, 1, 1, 0 ],
               [ 0, 1, 1, 0, 1 ],
               [ 0, 0, 1, 1, 0 ],
               [ 1, 1, 1, 0, 0 ] ]
 
    # Element to be moved
    num = 1
 
    # Function call
    no_of_moves(Matrix, x, y)
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to find the
// minimum number of moves to
// bring all non-zero element
// in one cell of the matrix
using System;
 
class GFG{
     
static int M = 4;
static int N = 5;
 
// Function to find the minimum
// number of moves to bring all
// elements in one cell of matrix
public static void no_of_moves(int[,] Matrix,
                               int x, int y)
{
     
    // Moves variable to store
    // the sum of number of moves
    int moves = 0;
 
    // Loop to count the number
    // of the moves
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
             
            // Condition to check that
            // the current cell is a
            // non-zero element
            if (Matrix[i, j] != 0)
            {
                moves += Math.Abs(x - i);
                moves += Math.Abs(y - j);
            }
        }
    }
    Console.WriteLine(moves);
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Coordinates of given cell
    int x = 3;
    int y = 2;
 
    // Given matrix
    int[,] Matrix = { { 1, 0, 1, 1, 0 },
                      { 0, 1, 1, 0, 1 },
                      { 0, 0, 1, 1, 0 },
                      { 1, 1, 1, 0, 0 } };
 
    // Function call
    no_of_moves(Matrix, x, y);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation to find the
// minimum number of moves to
// bring all non-zero element
// in one cell of the matrix
         
let M = 4;
let N = 5;
   
// Function to find the minimum
// number of moves to bring all
// elements in one cell of matrix
function no_of_moves(Matrix, x, y)
{
       
    // Moves variable to store
    // the sum of number of moves
    let moves = 0;
   
    // Loop to count the number
    // of the moves
    for(let i = 0; i < M; i++)
    {
        for(let j = 0; j < N; j++)
        {
               
            // Condition to check that
            // the current cell is a
            // non-zero element
            if (Matrix[i][j] != 0)
            {
                moves += Math.abs(x - i);
                moves += Math.abs(y - j);
            }
        }
    }
   document.write(moves);
}
 
// Driver Code
     
    // Coordinates of given cell
    let x = 3;
    let y = 2;
   
    // Given Matrix
    let Matrix = [[ 1, 0, 1, 1, 0 ],
                  [ 0, 1, 1, 0, 1 ],
                  [ 0, 0, 1, 1, 0 ],
                  [ 1, 1, 1, 0, 0 ]];
   
    // Element to be moved
    let num = 1;
   
    // Function call
    no_of_moves(Matrix, x, y);
 
</script>
Producción: 

27

 

Complejidad de Tiempo: O(N 2 )  
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

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