Encuentre la subarray que contiene la coordenada dada

Dada una array mat de N*N (N es un cuadrado perfecto|) y dos puntos xey , la tarea es devolver todos los elementos de la subarray en la que se encuentra el elemento A[x][y] .

Nota: La array se divide en N subarray igual cada una de tamaño K*K (donde K es la raíz cuadrada de N)

Ejemplos:

Entrada: N = 9, x = 4, y = 4
mat = {{1, 2, 3, 9, 8, 7, 1, 2, 1}, {4, 5, 6, 1, 2, 3, 7 , 9, 8}, {7, 8, 9, 2, 2, 0, 1, 5, 7},  
{0, 2, 9, 1, 2, 3, 4, 5, 3}, {9, 8 , 7, 4, 5, 6, 7, 4, 1}, {1, 4, 7, 7, 8, 9, 9, 8, 7},  
{5, 6, 1, 9, 8, 7, 5 , 2, 3}, {4, 5, 1, 6, 5, 4, 9, 7, 4}, {8, 7, 9, 3, 2, 1, 9, 4, 9}}, 
Salida: { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Explicación:  Dado x = 4, y = 4, ese elemento se encuentra en la cuadrícula del medio.

Array de entrada

Entrada: N = 9, x = 6, y= 4
mat = {{1, 2, 3, 9, 8, 7, 1, 2, 1}, {4, 5, 6, 1, 2, 3, 7 , 9, 8}, {7, 8, 9, 2, 2, 0, 1, 5, 7},  
{0, 2, 9, 1, 2, 3, 4, 5, 3}, {9, 8 , 7, 4, 5, 6, 7, 4, 1}, {1, 4, 7, 7, 8, 9, 9, 8, 7}, 
{5, 6, 1, 9, 8, 7, 5 , 2, 3}, {4, 5, 1, 6, 5, 4, 9, 7, 4}, {8, 7, 9, 3, 2, 1, 9, 4, 9}}
Salida: {{ 9, 8, 7}, {6, 5, 4}, {3, 2, 1}}
Explicación:  dado x = 6, y = 4, ese elemento se encuentra en la cuadrícula que se muestra a continuación.

Array de entrada

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

Un elemento en el índice (x, y) en una array cuadrada de longitud cuadrada perfecta, se encuentra en subarray[n*(x/n), (n*(y/n)] , donde cada valor muestra el posicionamiento con respecto a otro subarrays Entonces, la idea es simplemente imprimir esa subarray. 

Siga los pasos mencionados a continuación para implementar la idea:

• Encuentra la raíz cuadrada en N .
• Almacene la subarray donde se encuentra la coordenada (x, y) en una nueva array.
• Devuelve la nueva array.

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

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print submatrix
vector<vector<int> >
getSubGrid(int N, vector<vector<int> >& matrix, int x,
           int y)
{
    int n = sqrt(N);
    vector<vector<int> > subGrid(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            subGrid[i][j]
                = matrix[n * (x / n) + (j / n) + i]
                        [n * (y / n) + j % n];
        }
    }
 
    // Return the submatrix
    return subGrid;
}
 
// Driver Code
int main()
{
    int N = 9;
    vector<vector<int> > matrix
        = { { 1, 2, 3, 9, 8, 7, 1, 2, 1 },
            { 4, 5, 6, 1, 2, 3, 7, 9, 8 },
            { 7, 8, 9, 2, 2, 0, 1, 5, 7 },
            { 0, 2, 9, 1, 2, 3, 4, 5, 3 },
            { 9, 8, 7, 4, 5, 6, 7, 4, 1 },
            { 1, 4, 7, 7, 8, 9, 9, 8, 7 },
            { 5, 6, 1, 9, 8, 7, 5, 2, 3 },
            { 4, 5, 1, 6, 5, 4, 9, 7, 4 },
            { 8, 7, 9, 3, 2, 1, 9, 4, 9 } };
    int x = 4;
    int y = 4;
 
    // Function call
    vector<vector<int> > subGrid
        = getSubGrid(N, matrix, x, y);
    for (int i = 0; i < subGrid.size(); i++) {
        cout << "[";
        int j = 0;
        for (; j < subGrid.size() - 1; j++) {
            cout << subGrid[i][j] << ", ";
        }
        cout << subGrid[i][j] << "] ";
    }
 
    return 0;
}
 
// This code is contributed by Rohit Pradhan

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to print submatrix
    static int[][] getSubGrid(int N, int[][] matrix,
                              int x, int y)
    {
        int n = (int)Math.sqrt(N);
        int subGrid[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                subGrid[i][j]
                    = matrix[n * (x / n) + (j / n) + i]
                            [n * (y / n) + j % n];
            }
        }
 
        // Return the submatrix
        return subGrid;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 9;
        int matrix[][] = { { 1, 2, 3, 9, 8, 7, 1, 2, 1 },
                           { 4, 5, 6, 1, 2, 3, 7, 9, 8 },
                           { 7, 8, 9, 2, 2, 0, 1, 5, 7 },
                           { 0, 2, 9, 1, 2, 3, 4, 5, 3 },
                           { 9, 8, 7, 4, 5, 6, 7, 4, 1 },
                           { 1, 4, 7, 7, 8, 9, 9, 8, 7 },
                           { 5, 6, 1, 9, 8, 7, 5, 2, 3 },
                           { 4, 5, 1, 6, 5, 4, 9, 7, 4 },
                           { 8, 7, 9, 3, 2, 1, 9, 4, 9 } };
        int x = 4;
        int y = 4;
 
        // Function call
        int subGrid[][] = getSubGrid(N, matrix, x, y);
 
        System.out.println(Arrays.deepToString(subGrid));
    }
}

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

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