構造一個矩陣,使該矩陣每個元素由給定矩陣中各個元素的相鄰元素之和組成
瀏覽人數:596最近更新:
給定尺寸為N * M的矩陣 arr [] [],任務是生成一個矩陣,以使任何元素(r,c)存儲在給定矩陣中水平,垂直和對角線方向上存在的相鄰元素的總和。
例子:
輸入: arr [] [] = {{1,3},{2,4}}
輸出: {{9,7},{8,6}}
說明:矩陣是通過以下操作構造的:
對於單元格(0 ,0),arr [1] [0] + arr [0] [1] + arr [1] [1] = 2 + 3 + 4 =9。
對於單元格(0,1),arr [1] [0 ] + arr [0] [0] + arr [1] [1] = 2 +1 + 4 =7。
對於單元格(1,0),arr [0] [0] + arr [0] [1] + arr [1] [1] = 1 + 3 + 4 =8。
對於單元格(1,1),arr [1] [0] + arr [0] [1] + arr [0] [0] = 2 + 3 +1 = 6。
輸入: arr [] [] = {{1}}
輸出: {{0}}
方法:想法是遍歷給定矩陣的每個元素,對於每個像元(r,c),存儲相鄰像元{{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 }}。
- 初始化尺寸為N * M的矩陣v [] []以存儲每個單元格的結果。
- 現在,遍歷矩陣的每個單元格。對於每個單元格,檢查有效的相鄰單元格,並繼續更新其總和。
- 遍歷後,打印存儲在矩陣v [] []的每個單元格中的值。
#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);
}
輸出:
10 13 13
13 19 12
7 16 10
時間複雜度: O(N * M),其中N * M是矩陣的維數。
輔助空間: O(N * M)
本作品係原創或者翻譯,採用《署名-非商業性使用-禁止演繹4.0國際》許可協議