Dada una array A[][] de dimensión N*M , la tarea es encontrar el número mínimo de movimientos necesarios para atravesar toda la array a partir de (0, 0) al atravesar celdas conectadas con valores iguales en cada paso.
Desde una celda (i, j), se pueden conectar celdas (i + 1, j), (i – 1, j), (i, j – 1) y (i, j + 1).
Ejemplos:
Entrada: arr[][] = {{1, 1, 2, 2, 1}, {1, 1, 2, 2, 1}, {1, 1, 1, 3, 2}}
Salida: 5
Explicación:
Se requieren un mínimo de 5 movimientos para atravesar la array.
Primer movimiento: a partir de [0, 0], atraviesa las celdas [0, 1], [1, 1], [1, 0], [2, 0], [2, 1], [2, 2] como todas estas celdas tienen el mismo valor, 1.
Segundo movimiento: Atraviesa las celdas [0, 2], [0, 3], [1, 3], [1, 2] ya que todas estas celdas tienen el valor 2.
Tercer movimiento: Atraviesa las celdas [0, 4], [1, 4] que contiene 1.
Cuarto movimiento: Poligonal [2, 3] que contiene 3.
Quinto movimiento: Poligonal [2, 4] que contiene 4.Entrada: arr[][] = {{2, 1, 3}, {1, 1, 2}}
Salida: 4
Explicación:
Se requiere un mínimo de 4 movimientos para cubrir esta array 2-D
Primer movimiento: atravesar solo [0, 0] ya que ninguna otra celda conectada tiene el valor 2.
Segundo movimiento: recorrer las celdas [0, 1], [1, 1], [1, 0] ya que estas celdas contienen el valor 1.
Tercer movimiento: atravesar la celda [0, 2] que contiene 3.
Cuarto movimiento: celda poligonal [1, 2] que contiene 2.
Enfoque:
siga los pasos a continuación para resolver el problema:
- Cree otra array para llenar cada celda con valores distintos.
- Array poligonal A[][] a partir de (0, 0) . Para cada celda (i, j) , verifique si sus celdas adyacentes tienen el mismo valor que A[i][j] o no.
- Si alguna celda adyacente tiene el mismo valor, reemplace esa celda en B[][] con el valor de B[i][j] .
- El conteo de elementos distintos restantes en la array B[][] después de completar el recorrido de A[][] , da la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// minimum number of moves
// to traverse a given matrix
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// number of moves to traverse
// the given matrix
int solve(int A[][10], int N, int M)
{
int B[N][M];
int c = 1;
set<int> s;
// Constructing another matrix
// consisting of distinct values
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
B[i][j] = c++;
}
// Updating the array B by checking
// the values of A that if there are
// same values connected
// through an edge or not
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// Check for boundary
// condition of the matrix
if (i != 0) {
// If adjacent cells have
// same value
if (A[i - 1][j] == A[i][j])
B[i - 1][j] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (i != N - 1) {
// If adjacent cells have
// same value
if (A[i + 1][j] == A[i][j])
B[i + 1][j] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (j != 0) {
// If adjacent cells have
// same value
if (A[i][j - 1] == A[i][j])
B[i][j - 1] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (j != M - 1) {
// If adjacent cells have
// same value
if (A[i][j + 1] == A[i][j])
B[i][j + 1] = B[i][j];
}
}
}
// Store all distinct elements
// in a set
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
s.insert(B[i][j]);
}
// Return answer
return s.size();
}
// Driver Code
int main()
{
int N = 2, M = 3;
int A[][10] = { { 2, 1, 3 },
{ 1, 1, 2 } };
// Function Call
cout << solve(A, N, M);
}
Java
// Java program to find the
// minimum number of moves
// to traverse a given matrix
import java.util.*;
class GFG{
// Function to find the minimum
// number of moves to traverse
// the given matrix
static int solve(int A[][], int N,
int M)
{
int [][]B = new int[N][M];
int c = 1;
HashSet<Integer> s = new HashSet<Integer>();
// Constructing another matrix
// consisting of distinct values
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
B[i][j] = c++;
}
// Updating the array B by checking
// the values of A that if there are
// same values connected
// through an edge or not
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
// Check for boundary
// condition of the matrix
if (i != 0)
{
// If adjacent cells have
// same value
if (A[i - 1][j] == A[i][j])
B[i - 1][j] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (i != N - 1)
{
// If adjacent cells have
// same value
if (A[i + 1][j] == A[i][j])
B[i + 1][j] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (j != 0)
{
// If adjacent cells have
// same value
if (A[i][j - 1] == A[i][j])
B[i][j - 1] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (j != M - 1)
{
// If adjacent cells have
// same value
if (A[i][j + 1] == A[i][j])
B[i][j + 1] = B[i][j];
}
}
}
// Store all distinct elements
// in a set
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
s.add(B[i][j]);
}
// Return answer
return s.size();
}
// Driver Code
public static void main(String[] args)
{
int N = 2, M = 3;
int A[][] = { { 2, 1, 3 },
{ 1, 1, 2 } };
// Function Call
System.out.print(solve(A, N, M));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the # minimum number of moves # to traverse a given matrix # Function to find the minimum # number of moves to traverse # the given matrix def solve(A, N, M): B = [] c = 1 s = set() # Constructing another matrix # consisting of distinct values for i in range(N): new = [] for j in range(M): new.append(c) c = c + 1 B.append(new) # Updating the array B by checking # the values of A that if there are # same values connected # through an edge or not for i in range(N): for j in range(M): # Check for boundary # condition of the matrix if i != 0: # If adjacent cells have # same value if A[i - 1][j] == A[i][j]: B[i - 1][j] = B[i][j] # Check for boundary # condition of the matrix if (i != N - 1): # If adjacent cells have # same value if A[i + 1][j] == A[i][j]: B[i + 1][j] = B[i][j] # Check for boundary # condition of the matrix if (j != 0): # If adjacent cells have # same value if A[i][j - 1] == A[i][j]: B[i][j - 1] = B[i][j] # Check for boundary # condition of the matrix if (j != M - 1): # If adjacent cells have # same value if (A[i][j + 1] == A[i][j]): B[i][j + 1] = B[i][j] # Store all distinct elements # in a set for i in range(N): for j in range(M): s.add(B[i][j]) # Return answer return len(s) # Driver code N = 2 M = 3 A = [ [ 2, 1, 3 ], [ 1, 1, 2 ] ] # Function call print(solve(A, N, M)) # This code is contributed by divyeshrabadiya07
C#
// C# program to find the
// minimum number of moves
// to traverse a given matrix
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum
// number of moves to traverse
// the given matrix
static int solve(int [,]A, int N,
int M)
{
int [,]B = new int[N, M];
int c = 1;
HashSet<int> s = new HashSet<int>();
// Constructing another matrix
// consisting of distinct values
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
B[i, j] = c++;
}
// Updating the array B by checking
// the values of A that if there are
// same values connected
// through an edge or not
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
// Check for boundary
// condition of the matrix
if (i != 0)
{
// If adjacent cells have
// same value
if (A[i - 1, j] == A[i, j])
B[i - 1, j] = B[i, j];
}
// Check for boundary
// condition of the matrix
if (i != N - 1)
{
// If adjacent cells have
// same value
if (A[i + 1, j] == A[i, j])
B[i + 1, j] = B[i, j];
}
// Check for boundary
// condition of the matrix
if (j != 0)
{
// If adjacent cells have
// same value
if (A[i, j - 1] == A[i, j])
B[i, j - 1] = B[i, j];
}
// Check for boundary
// condition of the matrix
if (j != M - 1)
{
// If adjacent cells have
// same value
if (A[i, j + 1] == A[i, j])
B[i, j + 1] = B[i, j];
}
}
}
// Store all distinct elements
// in a set
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
s.Add(B[i, j]);
}
// Return answer
return s.Count;
}
// Driver Code
public static void Main(String[] args)
{
int N = 2, M = 3;
int [,]A = { { 2, 1, 3 },
{ 1, 1, 2 } };
// Function Call
Console.Write(solve(A, N, M));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the
// minimum number of moves
// to traverse a given matrix
// Function to find the minimum
// number of moves to traverse
// the given matrix
function solve(A, N, M)
{
var B = Array.from(Array(N), ()=> Array(M));
var c = 1;
var s = new Set();
// Constructing another matrix
// consisting of distinct values
for (var i = 0; i < N; i++) {
for (var j = 0; j < M; j++)
B[i][j] = c++;
}
// Updating the array B by checking
// the values of A that if there are
// same values connected
// through an edge or not
for (var i = 0; i < N; i++) {
for (var j = 0; j < M; j++) {
// Check for boundary
// condition of the matrix
if (i != 0) {
// If adjacent cells have
// same value
if (A[i - 1][j] == A[i][j])
B[i - 1][j] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (i != N - 1) {
// If adjacent cells have
// same value
if (A[i + 1][j] == A[i][j])
B[i + 1][j] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (j != 0) {
// If adjacent cells have
// same value
if (A[i][j - 1] == A[i][j])
B[i][j - 1] = B[i][j];
}
// Check for boundary
// condition of the matrix
if (j != M - 1) {
// If adjacent cells have
// same value
if (A[i][j + 1] == A[i][j])
B[i][j + 1] = B[i][j];
}
}
}
// Store all distinct elements
// in a set
for (var i = 0; i < N; i++) {
for (var j = 0; j < M; j++)
s.add(B[i][j]);
}
// Return answer
return s.size;
}
// Driver Code
var N = 2, M = 3;
var A = [ [ 2, 1, 3 ],
[ 1, 1, 2 ]];
// Function Call
document.write( solve(A, N, M));
</script>
Producción:
4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )