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: 5
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 ₂ , j ₂ ) a partir de (i ₁ , j ₁ ) es igual a abs(i ₂ – i ₁ ) + abs(j ₂ – j ₁ )

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:

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta