Número mínimo de pistas requeridas para obtener la celda oculta en la cuadrícula 2D

Dada una array 2D de tamaño M * N . La tarea es encontrar el número mínimo de pistas requeridas para elegir la posición correcta de una celda oculta en la cuadrícula, donde en cada pista se informará la distancia de Manhattan de la celda oculta a cualquier celda de su elección.

Nota: La distancia de Manhattan entre dos celdas es la suma de las diferencias absolutas entre filas y columnas de las celdas.

Ejemplos:

Entrada: M = 1, N = 3
Salida: 1
Explicación: Para cualquier celda oculta, si se conoce la distancia del camino X desde (1,1), entonces la celda oculta es (1, 1+X).

Entrada: M = 1, N = 1
Salida: 0
Explicación: Solo una celda posible.

Enfoque: Hay tres casos posibles para encontrar la posición de la celda en la cuadrícula:

Caso-1: cuando la cuadrícula tiene forma de fila, es decir   , dimensión = (1 x N) 

Para la tabla anterior, se requiere un mínimo de una pista. En la sugerencia, se puede obtener la distancia desde las celdas (1, 1) y si X es la distancia de la celda oculta desde (1, 1), entonces (1, 1+X) será la celda oculta.

Caso-2: cuando la cuadrícula tiene forma de columna, es decir   , dimensión = (N x 1)

Para la tabla anterior, se requiere un mínimo de una pista. En la pista, se puede obtener la distancia desde (1, 1) y si X es la distancia de la celda oculta desde (1, 1), entonces (1+X, 1) será la celda oculta.

Caso-3: Cuando la cuadrícula tiene forma de rectángulo, es decir   , dimensión = (M x N)
Para este tipo de tablas, se requiere un mínimo de dos pistas. Las pistas requeridas se muestran a continuación:

1. Uno para obtener la distancia de la ruta desde la celda (1, 1) y si X es la distancia de la ruta de la celda oculta desde (1, 1), entonces cualquier celda de la forma (1+X ₁ , 1+X ₂ ) será la oculta celda donde X ₁ + X ₂ = X .
2. Otro para obtener la distancia de la ruta desde la celda (1, N) y si Y es la distancia de la ruta de la celda oculta desde (1, N), entonces cualquier celda de la forma (1+Y ₁ , NY ₂ ) será la celda oculta donde Y ₁ + Y ₂ = Y .

Para cualquier combinación de X e Y, solo hay una celda que satisface ambas distancias. Usando las dos ecuaciones anteriores, la celda oculta se puede encontrar fácilmente. Entonces, en este caso, se necesitarán un mínimo de dos ayudas.

Siga la imagen a continuación para comprender mejor las condiciones y la intersección de las celdas con cualquier valor X e Y. Cualquier valor de X e Y tendrá solo una celda como punto de intersección.

celdas equidistantes de 1,1

Celda equidistante de (1,N) es decir, 1,4

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum help required
// for finding the hidden cell
int minHints(int M, int N)
{
    int res;
 
    // Grid having one cell
    if (M == 1 && N == 1)
        res = 0;
 
    // Row form or column form grid
    else if (M == 1 || N == 1)
        res = 1;
 
    // Rectangle form grid
    else
        res = 2;
 
    return res;
}
 
int main()
{
    // Declaring the dimension of the grid
    int M = 1, N = 3;
 
    cout << minHints(M, N);
    return 0;
}

// Java code to implement above approach
import java.util.*;
public class GFG
{
 
  // Function to find minimum help required
  // for finding the hidden cell
  static int minHints(int M, int N)
  {
    int res;
 
    // Grid having one cell
    if (M == 1 && N == 1)
      res = 0;
 
    // Row form or column form grid
    else if (M == 1 || N == 1)
      res = 1;
 
    // Rectangle form grid
    else
      res = 2;
 
    return res;
  }
 
  public static void main(String args[])
  {
     
    // Declaring the dimension of the grid
    int M = 1, N = 3;
 
    System.out.print(minHints(M, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 code to implement above approach
 
# Function to find minimum help required
# for finding the hidden cell
def minHints(M, N):
    res = 0
 
    # Grid having one cell
    if (M == 1 and N == 1):
        res = 0
 
    # Row form or column form grid
    elif (M == 1 or N == 1):
        res = 1
 
    # Rectangle form grid
    else:
        res = 2
 
    return res
 
 
if __name__ == "__main__":
 
    # Declaring the dimension of the grid
    M = 1
    N = 3
 
    print(minHints(M, N))
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG
{
 
  // Function to find minimum help required
  // for finding the hidden cell
  static int minHints(int M, int N)
  {
    int res;
 
    // Grid having one cell
    if (M == 1 && N == 1)
      res = 0;
 
    // Row form or column form grid
    else if (M == 1 || N == 1)
      res = 1;
 
    // Rectangle form grid
    else
      res = 2;
 
    return res;
  }
 
  public static void Main()
  {
 
    // Declaring the dimension of the grid
    int M = 1, N = 3;
 
    Console.Write(minHints(M, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find minimum help required
      // for finding the hidden cell
      function minHints(M, N)
      {
          let res;
 
          // Grid having one cell
          if (M == 1 && N == 1)
              res = 0;
 
          // Row form or column form grid
          else if (M == 1 || N == 1)
              res = 1;
 
          // Rectangle form grid
          else
              res = 2;
 
          return res;
      }
 
 
      // Declaring the dimension of the grid
      let M = 1, N = 3;
 
      document.write(minHints(M, N));
 
// This code is contributed by Potta Lokesh
  </script>

1

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)