Construya una Array tal que cada celda consista en la suma de los elementos adyacentes de las respectivas celdas en la Array dada

Dada una array arr[][] de dimensiones N * M , la tarea es generar una array tal que cualquier celda (r, c) almacene la suma de los elementos adyacentes presentes horizontal, vertical y diagonalmente en la array dada.

Ejemplos:

Entrada: arr[][] = {{1, 3}, {2, 4}}
Salida: {{9, 7}, {8, 6}}
Explicación: La array se construye mediante las siguientes operaciones: 
Para la celda (0 , 0), arr[1][0] + arr[0][1] + arr[1][1] = 2 + 3 + 4 = 9. 
Para la celda (0, 1), arr[1][0 ] + arr[0][0] + arr[1][1] = 2 + 1 + 4 = 7. 
Para la celda (1, 0), arr[0][0] + arr[0][1] + arr[1][1] = 1 + 3 + 4 = 8. 
Para la celda (1, 1), arr[1][0] + arr[0][1] + arr[0][0] = 2 + 3 + 1 = 6.

Entrada: arr[][] = {{1}}
Salida: {{0}}

Enfoque: La idea es atravesar cada celda de la array dada y para cada celda (r, c) , almacenar la suma de las celdas adyacentes {{r-1, c-1}, {r+1, c+1}, {r-1, c+1}, {r+1, c-1}, {r, c-1}, {r-1, c}, {r+1, c}, {r, c+1 }} si es posible.

  1. Inicialice una array v[][] de dimensión N * M para almacenar los resultados de cada celda.
  2. Ahora, atraviesa cada celda de la array. Para cada celda, verifique las celdas adyacentes válidas y siga actualizando su suma.
  3. Después de atravesar, imprima el valor almacenado en cada celda de la array v[][] .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Initialize rows and columns
int r, c;
 
// Store all 8 directions
vector<vector<int> > dir
    = { { 1, 0 },   { -1, 0 }, { 0, 1 }, { 0, -1 },
        { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };
 
// Function to check if a cell
// (i, j) is valid or not
bool valid(int i, int j)
{
    if (i >= 0 && j >= 0 && i < r && j < c)
        return 1;
 
    return 0;
}
 
// Function to find sum of adjacent cells
// for cell (i, j)
int find(int i, int j, vector<vector<int> >& v)
{
    // Initialize sum
    int s = 0;
 
    // Visit all 8 directions
    for (auto x : dir) {
        int ni = i + x[0], nj = j + x[1];
 
        // Check if cell is valid
        if (valid(ni, nj))
            s += v[ni][nj];
    }
 
    // Return sum
    return s;
}
 
// Function to print sum of adjacent elements
void findsumofneighbors(vector<vector<int> >& M)
{
    // Stores the resultant matrix
    vector<vector<int> > v(r, vector<int>(c, 0));
 
    // Iterate each elements of matrix
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
 
            // Find adjacent sum
            v[i][j] = find(i, j, M);
            cout << v[i][j] << " ";
        }
        cout << "\n";
    }
}
 
// Driver Code
int main()
{
 
    // Given matrix
    vector<vector<int> > M
        = { { 1, 4, 1 }, { 2, 4, 5 }, { 3, 1, 2 } };
 
    // Size of matrix
    r = M.size(), c = M[0].size();
 
    // Function call
    findsumofneighbors(M);
}

Java

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
public class GFG {
 
    // Initialize rows and columns
    private static int r, c;
 
    // Store all 8 directions
    static int[][] dir
        = { { 1, 0 },   { -1, 0 }, { 0, 1 }, { 0, -1 },
            { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };
 
    // Function to check if a cell
    // (i, j) is valid or not
    public static boolean valid(int i, int j)
    {
        if (i >= 0 && j >= 0 && i < r && j < c)
            return true;
 
        return false;
    }
 
    // Function to find sum of adjacent cells
    // for cell (i, j)
    static int find(int i, int j, int[][] v)
    {
        // Initialize sum
        int s = 0;
 
        // Visit all 8 directions
        for (int k = 0; k < 8; k++) {
 
            int ni = i + dir[k][0], nj = j + dir[k][1];
 
            // Check if cell is valid
            if (valid(ni, nj))
                s += v[ni][nj];
        }
 
        // Return sum
        return s;
    }
 
    // Function to print sum of adjacent elements
    static void findsumofneighbors(int[][] M)
    {
        // Stores the resultant matrix
        int[][] v = new int[r];
 
        // Iterate each elements of matrix
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
 
                // Find adjacent sum
                v[i][j] = find(i, j, M);
                System.out.print(v[i][j] + " ");
            }
            System.out.println("");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Given matrix
        int[][] M
            = { { 1, 4, 1 },
               { 2, 4, 5 },
               { 3, 1, 2 } };
 
        // Size of matrix
        r = M.length;
        c = M[0].length;
 
        // Function call
        findsumofneighbors(M);
    }
}
 
// This code is contributed by ajaykr00kj

Python3

# Python program for the above approach
 
# Initialize rows and columns
r, c = 0, 0;
 
# Store all 8 directions
dir = [[1, 0], [-1, 0], [0, 1], [0, -1],
       [-1, -1], [-1, 1], [1, 1], [1, -1]];
 
# Function to check if a cell
# (i, j) is valid or not
def valid(i, j):
    if (i >= 0 and j >= 0 and i < r and j < c):
        return True;
 
    return False;
 
# Function to find sum of adjacent cells
# for cell (i, j)
def find(i, j, v):
   
    # Initialize sum
    s = 0;
 
    # Visit all 8 directions
    for k in range(8):
 
        ni = i + dir[k][0];
        nj = j + dir[k][1];
 
        # Check if cell is valid
        if (valid(ni, nj)):
            s += v[ni][nj];
 
    # Return sum
    return s;
 
# Function to print sum of adjacent elements
def findsumofneighbors(M):
   
    # Stores the resultant matrix
    v = [[0 for i in range(c)] for j in range(r)];
 
    # Iterate each elements of matrix
    for i in range(r):
        for j in range(c):
           
            # Find adjacent sum
            v[i][j] = find(i, j, M);
            print(v[i][j], end=" ");
 
        print("");
 
# Driver code
if __name__ == '__main__':
   
    # Given matrix
    M = [[1, 4, 1], [2, 4, 5], [3, 1, 2]];
 
    # Size of matrix
    r = len(M[0]);
    c = len(M[1]);
 
    # Function call
    findsumofneighbors(M);
 
# This code is contributed by 29AjayKumar

C#

// C# program for the above approach
using System;
public class GFG {
 
    // Initialize rows and columns
    private static int r, c;
 
    // Store all 8 directions
    static int[,] dir
        = { { 1, 0 },   { -1, 0 }, { 0, 1 }, { 0, -1 },
            { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };
 
    // Function to check if a cell
    // (i, j) is valid or not
    public static bool valid(int i, int j)
    {
        if (i >= 0 && j >= 0 && i < r && j < c)
            return true;
 
        return false;
    }
 
    // Function to find sum of adjacent cells
    // for cell (i, j)
    static int find(int i, int j, int[,] v)
    {
        // Initialize sum
        int s = 0;
 
        // Visit all 8 directions
        for (int k = 0; k < 8; k++) {
 
            int ni = i + dir[k, 0], nj = j + dir[k, 1];
 
            // Check if cell is valid
            if (valid(ni, nj))
                s += v[ni, nj];
        }
 
        // Return sum
        return s;
    }
 
    // Function to print sum of adjacent elements
    static void findsumofneighbors(int[,] M)
    {
        // Stores the resultant matrix
        int[,] v = new int[r, c];
 
        // Iterate each elements of matrix
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
 
                // Find adjacent sum
                v[i,j] = find(i, j, M);
                Console.Write(v[i, j] + " ");
            }
            Console.WriteLine("");
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // Given matrix
        int[,] M
            = { { 1, 4, 1 },
               { 2, 4, 5 },
               { 3, 1, 2 } };
 
        // Size of matrix
        r = M.GetLength(0);
        c = M.GetLength(1);
 
        // Function call
        findsumofneighbors(M);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Initialize rows and columns
    let r, c;
  
    // Store all 8 directions
    let dir
        = [[ 1, 0 ],   [ -1, 0 ], [ 0, 1 ], [ 0, -1 ],
            [ -1, -1 ], [ -1, 1 ], [ 1, 1 ], [ 1, -1 ]];
  
    // Function to check if a cell
    // (i, j) is valid or not
   function valid(i, j)
    {
        if (i >= 0 && j >= 0 && i < r && j < c)
            return true;
  
        return false;
    }
  
    // Function to find sum of adjacent cells
    // for cell (i, j)
    function find(i, j, v)
    {
        // Initialize sum
        let s = 0;
  
        // Visit all 8 directions
        for (let k = 0; k < 8; k++) {
  
            let ni = i + dir[k][0], nj = j + dir[k][1];
  
            // Check if cell is valid
            if (valid(ni, nj))
                s += v[ni][nj];
        }
  
        // Return sum
        return s;
    }
  
    // Function to print sum of adjacent elements
    function findsumofneighbors(M)
    {
        // Stores the resultant matrix
        let v = new Array(r);
         
        // Loop to create 2D array using 1D array
    for (var i = 0; i < v.length; i++) {
        v[i] = new Array(2);
    }
  
        // Iterate each elements of matrix
        for (let i = 0; i < r; i++) {
            for (let j = 0; j < c; j++) {
  
                // Find adjacent sum
                v[i][j] = find(i, j, M);
                document.write(v[i][j] + " ");
            }
            document.write("<br/>" );
        }
    }
 
// Driver Code
 
     // Given matrix
      let M
            = [[ 1, 4, 1 ],
               [ 2, 4, 5 ],
               [ 3, 1, 2 ]];
  
        // Size of matrix
        r = M.length;
        c = M[0].length;
  
        // Function call
        findsumofneighbors(M);
 
</script>
Producción

10 13 13 
13 19 12 
7 16 10

Complejidad temporal: O(N*M) donde N * M son las dimensiones de la array.
Espacio auxiliar: O(N*M)

Publicación traducida automáticamente

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