La celda más alejada de una celda determinada en una array

Dados los números enteros N , M , R y C donde N y M denotan el número de filas y columnas en una array y (R, C) denota una celda en esa array, la tarea es encontrar la distancia de la celda más alejada de la array. celda (R, C) . 
Nota: La array solo se puede atravesar horizontal o verticalmente a la vez.

Ejemplos:

Entrada: N = 15, M = 12, R = 1, C = 6
Salida: 20
Explicación: La distancia máxima calculada desde las cuatro esquinas es 20, 5, 19, 6. Por lo tanto, 20 es la respuesta requerida.

Entrada: N = 15, M = 12, R = 2, C = 4
Salida: 21

Enfoque ingenuo: el enfoque más simple es atravesar la array y calcular la distancia de cada celda de la array desde la celda dada (R, C) y mantener el máximo de todas las distancias. 

Complejidad de tiempo : O (N * M), ya que estamos usando bucles anidados para atravesar N * M veces.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
 

Enfoque eficiente: para optimizar el enfoque anterior, la observación es que la celda más alejada de cualquier celda en una array será una de las cuatro celdas de la mayoría de las esquinas, es decir (1, 1), (1, M), (N, 1), (N, M) .

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

• Inicialice d1 , d2 , d3 y d4 sean iguales a N + M – R – C , R + C – 2 , N – R + C – 1 y M – C+ R – 1 respectivamente.
• Imprime el máximo entre d1 , d2 , d3 y d4 .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the farthest
// cell distance from the given cell
void farthestCellDistance(int N, int M,
                          int R, int C)
{
    // Distance from all the
    // cornermost cells
 
    // From cell(N, M)
    int d1 = N + M - R - C;
 
    // From Cell(1, 1)
    int d2 = R + C - 2;
 
    // From cell(N, 1)
    int d3 = N - R + C - 1;
 
    // From cell(1, M)
    int d4 = M - C + R - 1;
 
    // Finding out maximum
    int maxDistance = max(d1,
                          max(d2,
                              max(d3, d4)));
 
    // Print the answer
    cout << maxDistance;
}
 
// Driver Code
int main()
{
    int N = 15, M = 12, R = 1, C = 6;
    farthestCellDistance(N, M, R, C);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to find the farthest
// cell distance from the given cell
static void farthestCellDistance(int N, int M,
                                 int R, int C)
{
     
    // Distance from all the
    // cornermost cells
 
    // From cell(N, M)
    int d1 = N + M - R - C;
 
    // From Cell(1, 1)
    int d2 = R + C - 2;
 
    // From cell(N, 1)
    int d3 = N - R + C - 1;
 
    // From cell(1, M)
    int d4 = M - C + R - 1;
 
    // Finding out maximum
    int maxDistance = Math.max(d1, Math.max(
                  d2, Math.max(d3, d4)));
 
    // Print the answer
    System.out.println(maxDistance);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 15, M = 12, R = 1, C = 6;
     
    farthestCellDistance(N, M, R, C);
}
}
 
// This code is contributed by Dharanendra L V

# Python program for the above approach
 
# Function to find the farthest
# cell distance from the given cell
def farthestCellDistance(N, M, R, C):
   
    # Distance from all the
    # cornermost cells
 
    # From cell(N, M)
    d1 = N + M - R - C;
 
    # From Cell(1, 1)
    d2 = R + C - 2;
 
    # From cell(N, 1)
    d3 = N - R + C - 1;
 
    # From cell(1, M)
    d4 = M - C + R - 1;
 
    # Finding out maximum
    maxDistance = max(d1, max(d2, max(d3, d4)));
 
    # Print the answer
    print(maxDistance);
 
# Driver Code
if __name__ == '__main__':
    N = 15;
    M = 12;
    R = 1;
    C = 6;
 
    farthestCellDistance(N, M, R, C);
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the farthest
// cell distance from the given cell
static void farthestCellDistance(int N, int M,
                                 int R, int C)
{
     
    // Distance from all the
    // cornermost cells
 
    // From cell(N, M)
    int d1 = N + M - R - C;
 
    // From Cell(1, 1)
    int d2 = R + C - 2;
 
    // From cell(N, 1)
    int d3 = N - R + C - 1;
 
    // From cell(1, M)
    int d4 = M - C + R - 1;
 
    // Finding out maximum
    int maxDistance = Math.Max(d1, Math.Max(
                  d2, Math.Max(d3, d4)));
 
    // Print the answer
    Console.WriteLine(maxDistance);
}
 
// Driver Code
static public void Main()
{
    int N = 15, M = 12, R = 1, C = 6;
     
    farthestCellDistance(N, M, R, C);
}
}
 
// This code is contributed by Dharanendra L V

<script>
// Java script program for the above approach
 
// Function to find the farthest
// cell distance from the given cell
function farthestCellDistance( N,  M,
                                 R,  C)
{
     
    // Distance from all the
    // cornermost cells
 
    // From cell(N, M)
    let d1 = N + M - R - C;
 
    // From Cell(1, 1)
    let d2 = R + C - 2;
 
    // From cell(N, 1)
    let d3 = N - R + C - 1;
 
    // From cell(1, M)
    let d4 = M - C + R - 1;
 
    // Finding out maximum
    let maxDistance = Math.max(d1, Math.max(
                d2, Math.max(d3, d4)));
 
    // Print the answer
    document.write(maxDistance);
}
 
// Driver Code
 
    let N = 15, M = 12, R = 1, C = 6;
     
    farthestCellDistance(N, M, R, C);
 
 
// This code is contributed by Bobby
</script>

20

Complejidad de tiempo: O (1), ya que no estamos usando ningún bucle o recursividad para atravesar.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.