Pasos mínimos para mover todos los 1 a una sola celda de Matrix cuadrada dada

Dado un número entero positivo impar N , que denota el tamaño de una array cuadrada N*N llena de 1, la tarea es encontrar el número mínimo de pasos para mover todos los 1 a una sola celda de la array donde, en un paso, cualquier 1 se puede mover a cualquier celda que esté adyacente horizontal, vertical o diagonalmente. 

Ejemplos:

Entrada: N = 3
Salida: 8
Explicación: Todos los 8 1 presentes en el límite pueden llevarse al centro de la array en un solo paso.
Así que el total de pasos requeridos = 8

Entrada: N = 367
Salida: 16476832
Explicación: El número mínimo de pasos necesarios para poner todas las galletas en exactamente un bloque de la bandeja es 16476832. 

Planteamiento: El problema se puede resolver con base en la siguiente observación.

Para minimizar el número de pasos, todos los 1 deben moverse al centro de la array. 
Cualquier celda de la array es parte de la i-ésima zona si su distancia al centro es i (horizontal, vertical o diagonal). 
Todos los elementos del i-ésimo bloque se pueden mover al centro en i pasos.

Vea la imagen de abajo para una mejor idea acerca de las zonas. (Aquí se muestran zonas de una array 7*7)

Siga los pasos mencionados a continuación para resolver el problema utilizando la observación anterior:

• Número total de zonas posibles X = N/2 .
• El número total de celdas en la i-ésima zona es 2 * i * 4 = 8*i .
• Entonces, el número total de pasos requeridos para mover todos los 1 de la i-ésima zona al centro es 8*i*i .
• Ejecute un bucle de i = 1 a X y:
  • Calcule el número total de pasos para la i-ésima zona utilizando la fórmula anterior.
  • Súmalo con la suma .
• Devuelve la suma final como la respuesta.

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 minimum number
// of steps required to put
// all the cookies in exactly one cell
int minSteps(int N)
{
    // Stores the minimum number of steps
    int res = 0;
 
    // Loop to iterate over
    // all the zones present in the matrix
    for (int i = 1; i <= N / 2; ++i) {
 
        // Steps to move all 1s of ith zone
        // to the centre of the matrix
        res += 8 * i * i;
    }
 
    // Return the minimum steps
    return res;
}
 
// Driver Code
int main()
{
    // Given input
    int N = 7;
 
    // Function Call
    cout << minSteps(N);
    return 0;
}

// JAVA program for the above approach
import java.util.*;
class GFG
{
 
  // Function to find the minimum number
  // of steps required to put
  // all the cookies in exactly one cell
  public static int minSteps(int N)
  {
 
    // Stores the minimum number of steps
    int res = 0;
 
    // Loop to iterate over
    // all the zones present in the matrix
    for (int i = 1; i <= N / 2; ++i) {
 
      // Steps to move all 1s of ith zone
      // to the centre of the matrix
      res += 8 * i * i;
    }
 
    // Return the minimum steps
    return res;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Given input
    int N = 7;
 
    // Function Call
    System.out.print(minSteps(N));
  }
}
 
// This code is contributed by Taranpreet

# Python program for the above approach
 
# Function to find the minimum number
# of steps required to put
# all the cookies in exactly one cell
def minSteps(N):
 
    # Stores the minimum number of steps
    res = 0
 
    # Loop to iterate over
    # all the zones present in the matrix
    i = 1
    while(i <= N//2):
 
        # Steps to move all 1s of ith zone
        # to the centre of the matrix
        res += 8 * i * i
        i += 1
 
    # Return the minimum steps
    return res
 
# Driver Code
 
# Given input
N = 7
 
# Function Call
print(minSteps(N))
 
# This code is contributed by Samim Hossain Mondal.

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the minimum number
    // of steps required to put
    // all the cookies in exactly one cell
    static int minSteps(int N)
    {
 
        // Stores the minimum number of steps
        int res = 0;
 
        // Loop to iterate over
        // all the zones present in the matrix
        for (int i = 1; i <= N / 2; ++i) {
 
            // Steps to move all 1s of ith zone
            // to the centre of the matrix
            res += 8 * i * i;
        }
 
        // Return the minimum steps
        return res;
    }
 
    // Driver Code
    public static void Main()
    {
 
        // Given input
        int N = 7;
 
        // Function Call
        Console.Write(minSteps(N));
    }
}
 
// This code is contributed by Samim Hossain Mondal

<script>
    // JavaScript program for the above approach
 
 
    // Function to find the minimum number
    // of steps required to put
    // all the cookies in exactly one cell
    const minSteps = (N) => {
        // Stores the minimum number of steps
        let res = 0;
 
        // Loop to iterate over
        // all the zones present in the matrix
        for (let i = 1; i <= parseInt(N / 2); ++i) {
 
            // Steps to move all 1s of ith zone
            // to the centre of the matrix
            res += 8 * i * i;
        }
 
        // Return the minimum steps
        return res;
    }
 
    // Driver Code
 
    // Given input
    let N = 7;
 
    // Function Call
    document.write(minSteps(N));
 
// This code is contributed by rakeshsahni
 
</script>

112

Complejidad Temporal: O(X), donde X es el número de zonas presentes en la array
Espacio Auxiliar: O(1)