给定一个由N×M个正整数组成的矩阵，任务是找出是否可能使该矩阵增加。打印矩阵，否则打印-1。矩阵元素应大于零。 如果满足以下条件，则称矩阵为递增矩阵：-
null
- 对于每一行，元素的顺序是递增的。
- 对于每一列，元素的顺序都是递增的。
例如：
输入：N=4，M=4 1 2 2 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 输出： 1 2 2 3 1 2 7 7 6 6 7 7 6 6 7 7 正如我们所见，这是递增矩阵。 输入：N=2，M=3 1 4 -1 1 -1 3 输出：-1 这里，在第一排，我们必须放一些更大的东西 4以上，使其顺序递增。但是，在这之后， 第三列永远不会按递增顺序排列。 所以，不可能使其增加矩阵。
注：一个矩阵可以有多个解。
方法： 设dp[i][j]表示矩阵dp的第i行和第j列的元素。由于矩阵是非递减的，因此应保持以下两个条件：
- dp[i][j]>=dp[i][j-1]，在第一行中，元素是非递减的。
- dp[i][j]>=dp[i-1][j]，第j列中的元素是非递减的。
这意味着dp[i][j]>=dp[r]对于每1<=r<=i，1<=c<=j（一个元素大于左侧的所有元素）。 假设我是dp中包含-1的第一行，在这一行中，j是最左边的-1的列。将dp[i][j]替换为最小可能值总是很方便的，否则，可能无法为右边的另一个-1找到有效值。因此，一个可能的解决方案（也是字典中最小的）是设置dp[i][j]=max{dp[i][j-1]，dp[i-1][j]}。 在填充dp中的一些未知位置后，可能会发现其中一个dp值小于左侧的一些元素。在这种情况下，没有解决方案。
C++
// CPP program to Check if we can make // the given matrix increasing matrix or not #include <bits/stdc++.h> using namespace std; #define n 4 #define m 4 // Function to find increasing matrix void findIncreasingMatrix( int dp[n + 1][m + 1]) { bool flag = false ; for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { // Putting max into b as per the above approach int b = max(dp[i - 1][j], dp[i][j - 1]); // If b is -1 than putting 1 to it b = max(1, b); // If dp[i][j] has to be filled with max if (dp[i][j] == -1) dp[i][j] = b; // If dp[i][j] is less than from it's left // element or from it's upper element else if (dp[i][j] < b) flag = true ; } } // If it is not possible if (flag) cout << -1 << '' ; else { // Printing the increasing matrix for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { cout << dp[i][j] << ' ' ; } cout << endl; } } } // Drivers code int main() { /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ int dp[n + 1][m + 1] = { { 0, 0, 0, 0, 0 }, { 0, 1, 2, 2, 3 }, { 0, 1, -1, 7, -1 }, { 0, 6, -1, -1, -1 }, { 0, -1, -1, -1, -1 } }; findIncreasingMatrix(dp); } |
JAVA
// Java program to Check if we // can make the given matrix // increasing matrix or not import java.util.*; import java.lang.*; import java.io.*; class GFG { static final int n = 4 ; static final int m = 4 ; // Function to find increasing matrix static void findIncreasingMatrix( int dp[][]) { boolean flag = false ; for ( int i = 1 ; i <= n; ++i) { for ( int j = 1 ; j <= m; ++j) { // Putting max into b as per // the above approach int b = Math.max(dp[i - 1 ][j], dp[i][j - 1 ]); // If b is -1 than putting 1 to it b = Math.max( 1 , b); // If dp[i][j] has to be // filled with max if (dp[i][j] == - 1 ) dp[i][j] = b; // If dp[i][j] is less than from // it's left element or from // it's upper element else if (dp[i][j] < b) flag = true ; } } // If it is not possible if (flag == true ) System.out.println( "-1" ); else { // Printing the increasing matrix for ( int i = 1 ; i <= n; ++i) { for ( int j = 1 ; j <= m; ++j) { System.out.print(dp[i][j] + " " ); } System.out.println(); } } } // Driver code public static void main(String args[]) { /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ int dp[][] = {{ 0 , 0 , 0 , 0 , 0 }, { 0 , 1 , 2 , 2 , 3 }, { 0 , 1 , - 1 , 7 , - 1 }, { 0 , 6 , - 1 , - 1 , - 1 }, { 0 , - 1 , - 1 , - 1 , - 1 }}; findIncreasingMatrix(dp); } } // This code is contributed // by Subhadeep |
Python3
# Python3 program to Check if we can make # the given matrix increasing matrix or not # Function to find increasing matrix def findIncreasingMatrix(dp): flag = False for i in range ( 1 , n + 1 ): for j in range ( 1 , m + 1 ): # Putting max into b as per # the above approach b = max (dp[i - 1 ][j], dp[i][j - 1 ]) # If b is -1 than putting 1 to it b = max ( 1 , b) # If dp[i][j] has to be filled with max if dp[i][j] = = - 1 : dp[i][j] = b # If dp[i][j] is less than from it's left # element or from it's upper element elif dp[i][j] < b: flag = True # If it is not possible if flag: print ( - 1 ) else : # Printing the increasing matrix for i in range ( 1 , n + 1 ): for j in range ( 1 , m + 1 ): print (dp[i][j], end = ' ' ) print () # Driver code if __name__ = = "__main__" : dp = [[ 0 , 0 , 0 , 0 , 0 ], [ 0 , 1 , 2 , 2 , 3 ], [ 0 , 1 , - 1 , 7 , - 1 ], [ 0 , 6 , - 1 , - 1 , - 1 ], [ 0 , - 1 , - 1 , - 1 , - 1 ]] n = m = 4 findIncreasingMatrix(dp) # This code is contributed # by Rituraj Jain |
C#
// C# program to Check if we // can make the given matrix // increasing matrix or not using System; class GFG { static readonly int n = 4; static readonly int m = 4; // Function to find increasing matrix static void findIncreasingMatrix( int [,]dp) { bool flag = false ; for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { // Putting max into b as per // the above approach int b = Math.Max(dp[i - 1, j], dp[i, j - 1]); // If b is -1 than putting 1 to it b = Math.Max(1, b); // If dp[i,j] has to be // filled with max if (dp[i, j] == -1) dp[i, j] = b; // If dp[i,j] is less than from // it's left element or from // it's upper element else if (dp[i, j] < b) flag = true ; } } // If it is not possible if (flag == true ) Console.WriteLine( "-1" ); else { // Printing the increasing matrix for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { Console.Write(dp[i, j] + " " ); } Console.WriteLine(); } } } // Driver code public static void Main() { /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ int [,]dp = {{ 0, 0, 0, 0, 0 }, { 0, 1, 2, 2, 3 }, { 0, 1, -1, 7, -1 }, { 0, 6, -1, -1, -1 }, { 0, -1, -1, -1, -1 }}; findIncreasingMatrix(dp); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP program to Check if we can make // the given matrix increasing matrix or not $n = 4; $m = 4; // Function to find increasing matrix function findIncreasingMatrix( $dp ) { global $n ; global $m ; $flag = false; for ( $i = 1; $i <= $n ; ++ $i ) { for ( $j = 1; $j <= $m ; ++ $j ) { // Putting max into b as per the above approach $b = max( $dp [ $i - 1][ $j ], $dp [ $i ][ $j - 1]); // If b is -1 than putting 1 to it $b = max(1, $b ); // If dp[i][j] has to be filled with max if ( $dp [ $i ][ $j ] == -1) $dp [ $i ][ $j ] = $b ; // If dp[i][j] is less than from it's left // element or from it's upper element else if ( $dp [ $i ][ $j ] < $b ) $flag = true; } } // If it is not possible if ( $flag ) echo -1, '' ; else { // Printing the increasing matrix for ( $i = 1; $i <= $n ; ++ $i ) { for ( $j = 1; $j <= $m ; ++ $j ) { echo $dp [ $i ][ $j ], ' ' ; } echo "" ; } } } // Driver Code /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ $dp = array ( array (0, 0, 0, 0, 0), array (0, 1, 2, 2, 3), array (0, 1, -1, 7, -1), array (0, 6, -1, -1, -1), array (0, -1, -1, -1, -1)); findIncreasingMatrix( $dp ); // This code is contributed by akt_mit ?> |
Javascript
<script> // Javascript program to Check if we can make // the given matrix increasing matrix or not let n = 4; let m = 4; // Function to find increasing matrix function findIncreasingMatrix(dp) { let flag = false ; for (let i = 1; i <= n; ++i) { for (let j = 1; j <= m; ++j) { // Putting max into b as per the above approach let b = Math.max(dp[i - 1][j], dp[i][j - 1]); // If b is -1 than putting 1 to it b = Math.max(1, b); // If dp[i][j] has to be filled with max if (dp[i][j] == -1) dp[i][j] = b; // If dp[i][j] is less than from it's left // element or from it's upper element else if (dp[i][j] < b) flag = true ; } } // If it is not possible if (flag) document.write(-1 + "</br>" ); else { // Printing the increasing matrix for (let i = 1; i <= n; ++i) { for (let j = 1; j <= m; ++j) { document.write(dp[i][j] + " " ); } document.write( "</br>" ); } } } /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ let dp = [ [ 0, 0, 0, 0, 0 ], [ 0, 1, 2, 2, 3 ], [ 0, 1, -1, 7, -1 ], [ 0, 6, -1, -1, -1 ], [ 0, -1, -1, -1, -1 ] ]; findIncreasingMatrix(dp); // This code is contributed by divyesh072019. </script> |
输出：
1 2 2 3 1 2 7 7 6 6 7 7 6 6 7 7
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
