假设一个矩阵的大小 N×N 其中包含以 （十） 我 Y 我 ) ，其中x 我 是第i个同心方阵和y的中心行号 我 是第i个同心方阵中心的列号。同心方形矩阵的形式如下：
null
0 0 0 0 0 0 0 0 00 1 1 1 1 1 1 1 00 1 . . . . . 1 0 0 1 . b b b . 1 00 1 . b a b . 1 00 1 . b b b . 1 00 1 . . . . . 1 00 1 1 1 1 1 1 1 00 0 0 0 0 0 0 0 0
其中a为中心，b为a–1，该值将随着行或列的增加而减小。 由于存在多个子矩阵，因此存在多个子矩阵的单元。这些单元格的值将等于相交子矩阵的值之和。考虑到 N、 m，（x） 我 Y 我 A. 我 ) ，其中1<=i<=m和a 我 是第i个同心子矩阵中心的值。任务是在包含子矩阵的矩阵中找到最大值。 那么，之后呢 例如：
Input : N = 10, m = 2 (x1, y1, a1) = (3, 3, 3) (x2, y2, a2) = (7, 7, 4)Output : 4Maxtrix that will be form:
![图片[1]-包含相交同心子矩阵的矩阵中的最大值-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/Example.jpg)
Input : N = 10, m = 1 (x1, y1, a1) = (4, 5, 6)Output : 6
这个想法是制作一个二维矩阵 mat[][] 求每个单元的值，包括多个同心子矩阵相交的单元。现在，每个单元的观察值可以通过max（0，a–max（p–x）找到 我 ，q–y 我 ))其中a是第i个同心子矩阵中心的值，p是单元的行号，q是单元的列号，x 我 Y 我 )是第i个同心子矩阵中心的中心位置。因此，在找到矩阵mat[]]之后，我们将遍历矩阵以找到矩阵中的最大值。 下面是C++实现这种方法：
C++
//C++ Program to find the maximum value in a matrix //which contain intersecting concentric submatrix #include <bits/stdc++.h> using namespace std; #define MAXN 100 // Return the maximum value in intersecting // concentric submatrix. int maxValue( int n, int m, int x[], int y[], int a[]) { int c[MAXN][MAXN] = { 0 }; // For each center of concentric sub-matrix. for ( int i = 0; i < m; ++i) { // for each row for ( int p = 0; p < n; ++p) { // for each column for ( int q = 0; q < n; ++q) { // finding x distance. int dx = abs (p - x[i]); // finding y distance. int dy = abs (q - y[i]); // maximum of x distance and y distance int d = max(dx, dy); // assigning the value. c[p][q] += max(0, a[i] - d); } } } // Finding the maximum value in the formed matrix. int res = 0; for ( int i = 0; i < n; ++i) { for ( int j = 0; j < n; ++j) { res = max(res, c[i][j]); } } return res; } // Driven Program int main() { int n = 10; int m = 2; int x[] = { 3, 7 }; int y[] = { 3, 7 }; int a[] = { 4, 3 }; cout << maxValue(n, m, x, y, a) << endl; return 0; } |
JAVA
// Java Program to find the // maximum value in a matrix // which contain intersecting // concentric submatrix import java.io.*; class GFG { static int MAXN = 100 ; // Return the maximum value // in intersecting // concentric submatrix. static int maxValue( int n, int m, int x[], int y[], int a[]) { int c[][] = new int [MAXN][MAXN]; // For each center of // concentric sub-matrix. for ( int i = 0 ; i < m; ++i) { // for each row for ( int p = 0 ; p < n; ++p) { // for each column for ( int q = 0 ; q < n; ++q) { // finding x distance. int dx = Math.abs(p - x[i]); // finding y distance. int dy = Math.abs(q - y[i]); // maximum of x distance // and y distance int d = Math.max(dx, dy); // assigning the value. c[p][q] += Math.max( 0 , a[i] - d); } } } // Finding the maximum // value in the formed matrix. int res = 0 ; for ( int i = 0 ; i < n; ++i) { for ( int j = 0 ; j < n; ++j) { res = Math.max(res, c[i][j]); } } return res; } // Driven Code public static void main (String[] args) { int n = 10 ; int m = 2 ; int x[] = { 3 , 7 }; int y[] = { 3 , 7 }; int a[] = { 4 , 3 }; System.out.println(maxValue(n, m, x, y, a)); } } // This code is contributed by anuj_67. |
Python 3
# Python 3 Program to find the maximum # value in a matrix which contain # intersecting concentric submatrix MAXN = 100 # Return the maximum value in intersecting # concentric submatrix. def maxValue( n, m, x, y, a): c = [[ 0 for x in range (MAXN)] for y in range (MAXN)] # For each center of concentric sub-matrix. for i in range ( m): # for each row for p in range (n) : # for each column for q in range ( n) : # finding x distance. dx = abs (p - x[i]) # finding y distance. dy = abs (q - y[i]) # maximum of x distance and y distance d = max (dx, dy) # assigning the value. c[p][q] + = max ( 0 , a[i] - d) # Finding the maximum value in # the formed matrix. res = 0 for i in range (n) : for j in range (n) : res = max (res, c[i][j]) return res # Driver Code if __name__ = = "__main__" : n = 10 m = 2 x = [ 3 , 7 ] y = [ 3 , 7 ] a = [ 4 , 3 ] print (maxValue(n, m, x, y, a)) # This code is contributed by ita_c |
C#
// C# Program to find the maximum // value in a matrix which contain // intersecting concentric submatrix using System; class GFG { static int MAXN = 100; // Return the maximum value in intersecting // concentric submatrix. static int maxValue( int n, int m, int [] x, int [] y, int [] a) { int [,] c = new int [MAXN, MAXN]; // For each center of // concentric sub-matrix. for ( int i = 0; i < m; ++i) { // for each row for ( int p = 0; p < n; ++p) { // for each column for ( int q = 0; q < n; ++q) { // finding x distance. int dx = Math.Abs(p - x[i]); // finding y distance. int dy = Math.Abs(q - y[i]); // maximum of x distance // and y distance int d = Math.Max(dx, dy); // assigning the value. c[p,q] += Math.Max(0, a[i] - d); } } } // Finding the maximum // value in the formed matrix. int res = 0; for ( int i = 0; i < n; ++i) { for ( int j = 0; j < n; ++j) { res = Math.Max(res, c[i, j]); } } return res; } // Driver Code public static void Main () { int n = 10; int m = 2; int [] x = { 3, 7 }; int [] y = { 3, 7 }; int [] a = { 4, 3 }; Console.Write(maxValue(n, m, x, y, a)); } } |
Javascript
<script> // Javascript Program to find the // maximum value in a matrix // which contain intersecting // concentric submatrix var maxN = 100; // Return the maximum value in intersecting // concentric submatrix. function maxValue(n, m, x, y, a) { var c = Array.from(Array(maxN), () => Array(maxN).fill(0)); // For each center of concentric sub-matrix. for ( var i = 0; i < m; ++i) { // for each row for ( var p = 0; p < n; ++p) { // for each column for ( var q = 0; q < n; ++q) { // finding x distance. var dx = Math.abs(p - x[i]); // finding y distance. var dy = Math.abs(q - y[i]); // maximum of x distance // and y distance var d = Math.max(dx, dy); // assigning the value. c[p][q] += Math.max(0, a[i] - d); } } } // Finding the Math.maximum value in // the formed matrix. var res = 0; for ( var i = 0; i < n; ++i) { for ( var j = 0; j < n; ++j) { res = Math.max(res, c[i][j]); } } return res; } // Driven Program var n = 10; var m = 2; var x = [ 3, 7 ]; var y = [ 3, 7 ]; var a = [ 4, 3 ]; document.write(maxValue(n, m, x, y, a)); </script> |
输出：
4
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
