Pasos mínimos necesarios para visitar todos los rincones de una cuadrícula N * M

Dados dos números enteros N y M que representan las dimensiones de una cuadrícula 2D , y dos números enteros R y C , que representan la posición de un bloque en esa cuadrícula, la tarea es encontrar el número mínimo de pasos necesarios para visitar todas las esquinas de la cuadrícula. , a partir de (R, C) . En cada paso, se permite mover el bloque adyacente al lado en la cuadrícula.

Ejemplos:

Entrada: N = 2, M = 2, R = 1, C = 2 
Salida: 3

Explicación: 
(1, 2) -> (1, 1) -> (2, 1) -> (2, 2) 
Por lo tanto, la salida requerida es 3.

Entrada: N = 2, M = 3, R = 2, C = 2 
Salida:
Explicación: 
(2, 2) -> (2, 3) -> (1, 3) -> (1, 2) -> (1, 1) -> (2, 1) 
Por lo tanto, la salida requerida es 5.

Enfoque: El problema se puede resolver con base en las siguientes observaciones.

El número mínimo de pasos necesarios para visitar el bloque (i 2 , j 2 ) a partir de (i 1 , j 1 ) es igual a abs(i 2 – i 1 ) + abs(j 2 – j 1 )

Siga los pasos que se indican a continuación para resolver el problema:

  • Primero visite la esquina que requiere un mínimo de pasos utilizando las observaciones anteriores.
  • Visite las otras esquinas de la cuadrícula atravesando el límite de la cuadrícula, ya sea en el sentido de las agujas del reloj o en el sentido contrario, dependiendo de cuál tomará la cantidad mínima de pasos para visitar las esquinas.
  • Finalmente, imprima el conteo mínimo de pasos obtenidos.

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum count of steps
// required to visit all the corners of the grid
int min_steps_required(int n, int m, int r, int c)
{
 
    // Stores corner of the grid
    int i, j;
 
    // Stores minimum count of steps required
    // to visit the first corner of the grid
    int corner_steps_req = INT_MAX;
 
    // Checking for leftmost upper corner
    i = 1;
    j = 1;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    // Checking for leftmost down corner
    i = n;
    j = 1;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    // Checking for rightmost upper corner
    i = 1;
    j = m;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    // Checking for rightmost down corner
    i = n;
    j = m;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    // Stores minimum count of steps required
    // to visit remaining three corners of the grid
    int minimum_steps = min(2 * (n - 1) + m - 1,
                            2 * (m - 1) + n - 1);
 
    return minimum_steps + corner_steps_req;
}
 
// Driver Code
int main()
{
 
    int n = 3;
    int m = 2;
    int r = 1;
    int c = 1;
 
    cout << min_steps_required(n, m, r, c);
 
    return 0;
}

Java

// Java Program to implement the
// above approach
import java.util.*;
class GFG
{
  
// Function to find the minimum count of steps
// required to visit all the corners of the grid
static int min_steps_required(int n, int m, int r, int c)
{
 
    // Stores corner of the grid
    int i, j;
 
    // Stores minimum count of steps required
    // to visit the first corner of the grid
    int corner_steps_req = Integer.MAX_VALUE;
 
    // Checking for leftmost upper corner
    i = 1;
    j = 1;
    corner_steps_req = Math.min(corner_steps_req,
                           Math.abs(r - i) + Math.abs(j - c));
 
    // Checking for leftmost down corner
    i = n;
    j = 1;
    corner_steps_req = Math.min(corner_steps_req,
                           Math.abs(r - i) + Math.abs(j - c));
 
    // Checking for rightmost upper corner
    i = 1;
    j = m;
    corner_steps_req = Math.min(corner_steps_req,
                           Math.abs(r - i) + Math.abs(j - c));
 
    // Checking for rightmost down corner
    i = n;
    j = m;
    corner_steps_req = Math.min(corner_steps_req,
                           Math.abs(r - i) + Math.abs(j - c));
 
    // Stores minimum count of steps required
    // to visit remaining three corners of the grid
    int minimum_steps = Math.min(2 * (n - 1) + m - 1,
                            2 * (m - 1) + n - 1);
 
    return minimum_steps + corner_steps_req;
}
  
// Driver Code
public static void main(String[] args)
{
    int n = 3;
    int m = 2;
    int r = 1;
    int c = 1;
 
    System.out.print(min_steps_required(n, m, r, c));
}
}
 
// This code is contributed by code_hunt.

Python3

# Python3 program to implement
# the above approach
import sys
INT_MAX = sys.maxsize;
 
# Function to find the minimum count of steps
# required to visit all the corners of the grid
def min_steps_required(n, m, r, c) :
 
    # Stores corner of the grid
    i = 0; j = 0;
 
    # Stores minimum count of steps required
    # to visit the first corner of the grid
    corner_steps_req = INT_MAX;
 
    # Checking for leftmost upper corner
    i = 1;
    j = 1;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    # Checking for leftmost down corner
    i = n;
    j = 1;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    # Checking for rightmost upper corner
    i = 1;
    j = m;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    # Checking for rightmost down corner
    i = n;
    j = m;
    corner_steps_req = min(corner_steps_req,
                           abs(r - i) + abs(j - c));
 
    # Stores minimum count of steps required
    # to visit remaining three corners of the grid
    minimum_steps = min(2 * (n - 1) + m - 1,
                            2 * (m - 1) + n - 1);
 
    return minimum_steps + corner_steps_req;
 
# Driver Code
if __name__ == "__main__" :
    n = 3;
    m = 2;
    r = 1;
    c = 1;
    print(min_steps_required(n, m, r, c));
 
    # This code is contributed by AnkThon

C#

// C# program to implement the
// above approach
using System;
 
class GFG{
  
// Function to find the minimum count
// of steps required to visit all the
// corners of the grid
static int min_steps_required(int n, int m,
                              int r, int c)
{
     
    // Stores corner of the grid
    int i, j;
 
    // Stores minimum count of steps required
    // to visit the first corner of the grid
    int corner_steps_req = int.MaxValue;
 
    // Checking for leftmost upper corner
    i = 1;
    j = 1;
    corner_steps_req = Math.Min(corner_steps_req,
                                Math.Abs(r - i) +
                                Math.Abs(j - c));
 
    // Checking for leftmost down corner
    i = n;
    j = 1;
    corner_steps_req = Math.Min(corner_steps_req,
                                Math.Abs(r - i) +
                                Math.Abs(j - c));
 
    // Checking for rightmost upper corner
    i = 1;
    j = m;
    corner_steps_req = Math.Min(corner_steps_req,
                                Math.Abs(r - i) +
                                Math.Abs(j - c));
 
    // Checking for rightmost down corner
    i = n;
    j = m;
    corner_steps_req = Math.Min(corner_steps_req,
                                Math.Abs(r - i) +
                                Math.Abs(j - c));
 
    // Stores minimum count of steps required
    // to visit remaining three corners of the grid
    int minimum_steps = Math.Min(2 * (n - 1) + m - 1,
                                 2 * (m - 1) + n - 1);
 
    return minimum_steps + corner_steps_req;
}
  
// Driver Code
public static void Main(String[] args)
{
    int n = 3;
    int m = 2;
    int r = 1;
    int c = 1;
 
    Console.Write(min_steps_required(n, m, r, c));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript program to implement the
// above approach
  
// Function to find the minimum count
// of steps required to visit all the
// corners of the grid
 
function  min_steps_required( n,  m,  r,  c)
{
      
    // Stores corner of the grid
    var i, j;
  
    // Stores minimum count of steps required
    // to visit the first corner of the grid
     
    var corner_steps_req = Number.MAX_VALUE;
  
    // Checking for leftmost upper corner
     
    i = 1;
    j = 1;
    corner_steps_req = Math.min(corner_steps_req,
                                Math.abs(r - i) +
                                Math.abs(j - c));
  
    // Checking for leftmost down corner
    i = n;
    j = 1;
    corner_steps_req = Math.min(corner_steps_req,
                                Math.abs(r - i) +
                                Math.abs(j - c));
  
    // Checking for rightmost upper corner
    i = 1;
    j = m;
    corner_steps_req = Math.min(corner_steps_req,
                                Math.abs(r - i) +
                                Math.abs(j - c));
  
    // Checking for rightmost down corner
    i = n;
    j = m;
    corner_steps_req = Math.min(corner_steps_req,
                                Math.abs(r - i) +
                                Math.abs(j - c));
  
    // Stores minimum count of steps required
    // to visit remaining three corners of the grid
    var minimum_steps = Math.min(2 * (n - 1) + m - 1,
                                 2 * (m - 1) + n - 1);
  
    return minimum_steps + corner_steps_req;
}
   
// Driver Code
 
    var n = 3;
    var m = 2;
    var r = 1;
    var c = 1;
  
    document.write(min_steps_required(n, m, r, c));
     
</script>
Producción: 

4

 

Complejidad temporal: O(1)  
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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