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)