Dada una array N x M mat[][] donde inicialmente estamos parados en la celda con índice (i, j) , la tarea es encontrar el número de operaciones requeridas para escapar de la array dada donde en cada operación mat[x] [y] se puede alcanzar desde mat[i][j] tal que x representa el conteo de 0 en la representación binaria de mat[i][j] e y representa el conteo de 1 en la representación binaria de mat[i] [j] .
Ejemplos :
Entrada : mat[][] = {{5, 13, 8, 1}, {7, 9, 2, 15}, {12, 4, 8, 3}}, i = 0, j = 0
Salida : 4
Explicación : Inicialmente, la posición actual es mat[0][0] = 5. Por lo tanto, el índice accesible desde 5 es mat[1][2] ya que el recuento de 0 en 5 es 1 y el recuento de 1 en 5 es 2. Por lo tanto, el primer salto es desde mat[0][0] => mat[1][2]. De manera similar, los saltos están en el siguiente orden: mat[0][0] => mat[1][2] => mat[1][1] => mat[2][2] => mat[3] [1]. Dado que el índice (3, 1) no existe en la array dada, el número de operaciones requeridas es 4.Entrada : mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, i = 1, j = 2
Salida : -1
Explicación : No es posible escapar de la array del índice.
Enfoque : el problema dado se puede resolver con la ayuda del algoritmo de Brian Kernighan y la función de registro incorporada . A continuación se detallan los pasos a seguir:
- Cree una variable Jump , que almacene el número requerido de operaciones de salto para escapar de la array 2D dada . Inicialmente, Salto = 0 .
- Si la celda inicial ya está fuera de los límites de la array dada, devuelva 0 .
- Calcule la cuenta de 0 y 1 en la representación binaria de mat[i][j] .
- Salta al siguiente índice válido y establece mat[i][j] como -1 . Además, incremente el valor de Jump en 1 .
- Compruebe si el valor actual de mat[i][j] = -1 después del salto. Significa que el índice actual ya se ha visitado, por lo que se crea un bucle sin fin. Por lo tanto, devuelve -1 .
- Repita el proceso anterior hasta que el índice actual ya esté visitado o esté fuera de los límites de la array dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define Max 100
using namespace std;
// Function to find total count of
// set bits in any number
int brianKernighan(int N)
{
int Count = 0;
while (N) {
N = N & (N - 1);
Count += 1;
}
return Count;
}
// Function to find left most Set bit
// position in any number
int getMsbIndex(int N)
{
return ((int)log2(N) + 1);
}
// Function to find the number of
// jumps to escape the matrix from
// the given index [i, j]
int countJumps(int Mat[][Max],
int N, int M,
int i, int j)
{
// Initialize the variable Jump
int C0, C1, Jump = 0;
while (i < N && j < M) {
// When the element is already visited
// then a closed loop is formed and
// it is impossible to escape then
// return -1.
if (Mat[i][j] == -1)
return -1;
// Calculate Count of 1 in Mat[i][j]
C1 = brianKernighan(Mat[i][j]);
// Calculate Count of 0 in Mat[i][j]
C0 = getMsbIndex(Mat[i][j]) - C1;
// Set the element Mat[i][j] visited
Mat[i][j] = -1;
// Set i and j to count if 0 and 1
i = C0, j = C1;
// Increment Jump by 1
Jump++;
}
// Return number of Jumps to escape
// the matrix if it is possible to
// escape
return Jump;
}
// Driver Code
int main()
{
int N = 3, M = 4;
int i = 0, j = 0;
int Mat[][Max] = { { 5, 13, 8, 1 },
{ 7, 9, 2, 15 },
{ 12, 4, 8, 3 } };
cout << countJumps(Mat, N, M, i, j);
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find total count of
// set bits in any number
static int brianKernighan(int N)
{
int Count = 0;
while (N != 0) {
N = N & (N - 1);
Count += 1;
}
return Count;
}
// Function to find left most Set bit
// position in any number
static int getMsbIndex(int N)
{
return ((int)(Math.log(N) / Math.log(2)) + 1);
}
// Function to find the number of
// jumps to escape the matrix from
// the given index [i, j]
static int countJumps(int Mat[][],
int N, int M,
int i, int j)
{
// Initialize the variable Jump
int C0, C1, Jump = 0;
while (i < N && j < M) {
// When the element is already visited
// then a closed loop is formed and
// it is impossible to escape then
// return -1.
if (Mat[i][j] == -1)
return -1;
// Calculate Count of 1 in Mat[i][j]
C1 = brianKernighan(Mat[i][j]);
// Calculate Count of 0 in Mat[i][j]
C0 = getMsbIndex(Mat[i][j]) - C1;
// Set the element Mat[i][j] visited
Mat[i][j] = -1;
// Set i and j to count if 0 and 1
i = C0; j = C1;
// Increment Jump by 1
Jump++;
}
// Return number of Jumps to escape
// the matrix if it is possible to
// escape
return Jump;
}
// Driver Code
public static void main (String[] args) {
int N = 3, M = 4;
int i = 0, j = 0;
int Mat[][] = { { 5, 13, 8, 1 },
{ 7, 9, 2, 15 },
{ 12, 4, 8, 3 } };
System.out.println(countJumps(Mat, N, M, i, j));
}
}
// This code is contributed by target_2.
Python3
# Python Program to implement # the above approach import math as Math Max = 100 # Function to find total count of # set bits in any number def brianKernighan(N): Count = 0 while (N): N = N & (N - 1) Count += 1 return Count # Function to find left most Set bit # position in any number def getMsbIndex(N): return Math.floor(Math.log2(N) + 1) # Function to find the number of # jumps to escape the matrix from # the given index [i, j] def countJumps(Mat, N, M, i, j): # Initialize the variable Jump Jump = 0 while (i < N and j < M): # When the element is already visited # then a closed loop is formed and # it is impossible to escape then # return -1. if (Mat[i][j] == -1): return -1 # Calculate Count of 1 in Mat[i][j] C1 = brianKernighan(Mat[i][j]) # Calculate Count of 0 in Mat[i][j] C0 = getMsbIndex(Mat[i][j]) - C1 # Set the element Mat[i][j] visited Mat[i][j] = -1 # Set i and j to count if 0 and 1 i = C0 j = C1 # Increment Jump by 1 Jump += 1 # Return number of Jumps to escape # the matrix if it is possible to # escape return Jump # Driver Code N = 3 M = 4 i = 0 j = 0 Mat = [[5, 13, 8, 1], [7, 9, 2, 15], [12, 4, 8, 3]] print(countJumps(Mat, N, M, i, j)) # This code is contributed by gfgking.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find total count of
// set bits in any number
static int brianKernighan(int N)
{
int Count = 0;
while (N != 0) {
N = N & (N - 1);
Count += 1;
}
return Count;
}
// Function to find left most Set bit
// position in any number
static int getMsbIndex(int N)
{
return ((int)(Math.Log(N) / Math.Log(2)) + 1);
}
// Function to find the number of
// jumps to escape the matrix from
// the given index [i, j]
static int countJumps(int[,] Mat,
int N, int M,
int i, int j)
{
// Initialize the variable Jump
int C0, C1, Jump = 0;
while (i < N && j < M) {
// When the element is already visited
// then a closed loop is formed and
// it is impossible to escape then
// return -1.
if (Mat[i, j] == -1)
return -1;
// Calculate Count of 1 in Mat[i][j]
C1 = brianKernighan(Mat[i, j]);
// Calculate Count of 0 in Mat[i][j]
C0 = getMsbIndex(Mat[i, j]) - C1;
// Set the element Mat[i][j] visited
Mat[i, j] = -1;
// Set i and j to count if 0 and 1
i = C0; j = C1;
// Increment Jump by 1
Jump++;
}
// Return number of Jumps to escape
// the matrix if it is possible to
// escape
return Jump;
}
// Driver Code
public static void Main()
{
int N = 3, M = 4;
int i = 0, j = 0;
int[,] Mat = {{ 5, 13, 8, 1 },
{ 7, 9, 2, 15 },
{ 12, 4, 8, 3 } };
Console.Write(countJumps(Mat, N, M, i, j));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript Program to implement
// the above approach
var Max = 100
// Function to find total count of
// set bits in any number
function brianKernighan(N) {
let Count = 0;
while (N) {
N = N & (N - 1);
Count += 1;
}
return Count;
}
// Function to find left most Set bit
// position in any number
function getMsbIndex(N) {
return Math.floor(Math.log2(N) + 1);
}
// Function to find the number of
// jumps to escape the matrix from
// the given index [i, j]
function countJumps(Mat,
N, M,
i, j) {
// Initialize the variable Jump
let C0, C1, Jump = 0;
while (i < N && j < M) {
// When the element is already visited
// then a closed loop is formed and
// it is impossible to escape then
// return -1.
if (Mat[i][j] == -1)
return -1;
// Calculate Count of 1 in Mat[i][j]
C1 = brianKernighan(Mat[i][j]);
// Calculate Count of 0 in Mat[i][j]
C0 = getMsbIndex(Mat[i][j]) - C1;
// Set the element Mat[i][j] visited
Mat[i][j] = -1;
// Set i and j to count if 0 and 1
i = C0, j = C1;
// Increment Jump by 1
Jump++;
}
// Return number of Jumps to escape
// the matrix if it is possible to
// escape
return Jump;
}
// Driver Code
let N = 3, M = 4;
let i = 0, j = 0;
let Mat = [[5, 13, 8, 1],
[7, 9, 2, 15],
[12, 4, 8, 3]];
document.write(countJumps(Mat, N, M, i, j));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad de tiempo : O(N * M * log(M * N)) Espacio
auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA