2 つ与えられる 行列 そして b サイズの ん*ん 。タスクは必要なものを見つけることです 変換ステップ数 両方の行列が等しくなるようにします。印刷する -1 それが不可能な場合。
の 変換 ステップは次のとおりです。
パワーシェルとバッシュの比較
- 2 つの行列からいずれか 1 つの行列を選択します。
- どちらかを選択してください 行/列 選択したマトリックスの値。
- 選択のすべての要素をインクリメントします 行/列 1までに。
例:
入力：
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]出力 ：3
説明 :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
入力 :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]出力 : -1
説明 : a と b が等しくなる変換はありません。
アプローチ：
その考えは、 増加する の任意の行/列 行列a と同等です 減少する 同じ行/列 行列 b 。
これは、両方の行列を追跡する代わりに、それらの差を処理できることを意味します。 (a[i][j] - b[i][j])。 ' で行をインクリメントすると、 ああ その行のすべての要素が 1 ずつ増加します。これは、差分行列のその行のすべての要素が 1 ずつ増加するのと同じです。同様に、' の列をインクリメントするときも同様です。 ああ これは、差分行列のその列のすべての要素を 1 増やすことと同じです。
これにより、問題を 1 つの行列だけを扱うように変換することができます。
ハッキング処理
解決策が存在するかどうかを判断します。
を作成した後、 差分行列 細胞ごとに a[i][j] (最初の行と最初の列を除く)
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0。
この方程式がどのセルにも当てはまらない場合は、すぐに解が存在しないと結論付けることができます。
なぜこれが機能するのでしょうか?
方法を考えてください 行と列 操作は各セルに影響します: 実行時 × 行に対する操作 私 そして そして 列に対する操作 j a[i][j] (x + y) によって変化します a[i][0] x によって変更されます (行操作のみ)、a[0][j] は y によって変更されます (列操作のみ)、a[0][0] は次の影響を受けます。 行 i も列 j もありません 操作。したがって (x + y) - x - y + 0 = 0 有効な解には必ず当てはまります。この方程式がどのセルにも当てはまらない場合は、一連の行および列の演算で 1 つの行列を別の行列に変換できないことを意味します。
必要な変換の数を計算します。
C++必要な変換の数を計算するには、 最初の行 そして 最初の列 なぜなら：
- まず要約します |a[i][0]| すべての i (各最初の列要素) について、これは必要な行操作の数を表すためです。各行 i には |a[i][0]| が必要です。その行要素をゼロにする操作。
- それでは要約します |a[0][j] - a[0][0]| これは、必要な追加の列操作を表すため、すべての j (各最初の行要素から最初の要素を差し引いたもの) に対して行われます。行操作がすでにこの要素に影響を与えているため、2 回カウントされるのを避けるために a[0][0] を減算します。
- これら 2 つの合計により、 最小操作数 行操作は最初の列の差異を処理し、列操作は最初の行の残りの差異を処理するため、必要になります。
// C++ program to find number of transformation // to make two Matrix Equal #include
// Java program to find number of transformation // to make two Matrix Equal import java.util.*; class GfG { static int countOperations(int[][] a int[][] b) { int n = a.length; int m = a[0].length; // Create difference matrix (a = a - b) for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] -= b[i][j]; } } // Check if transformation is possible using the // property a[i][j] - a[i][0] - a[0][j] + a[0][0] // should be 0 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (a[i][j] - a[i][0] - a[0][j] + a[0][0] != 0) { return -1; } } } int result = 0; // Add operations needed for first column for (int i = 0; i < n; i++) { result += Math.abs(a[i][0]); } // Add operations needed for // first row (excluding a[0][0]) for (int j = 0; j < m; j++) { result += Math.abs(a[0][j] - a[0][0]); } return result; } public static void main(String[] args) { int[][] a = { { 1 1 } { 1 1 } }; int[][] b = { { 1 2 } { 3 4 } }; System.out.println(countOperations(a b)); } }
# Python program to find number of transformation # to make two Matrix Equal def countOperations(a b): n = len(a) m = len(a[0]) # Create difference matrix (a = a - b) for i in range(n): for j in range(m): a[i][j] -= b[i][j] # Check if transformation is possible using the property # a[i][j] - a[i][0] - a[0][j] + a[0][0] should be 0 for i in range(1 n): for j in range(1 m): if a[i][j] - a[i][0] - a[0][j] + a[0][0] != 0: return -1 result = 0 # Add operations needed for first column for i in range(n): result += abs(a[i][0]) # Add operations needed for # first row (excluding a[0][0]) for j in range(m): result += abs(a[0][j] - a[0][0]) return result if __name__ == '__main__': a = [ [1 1] [1 1] ] b = [ [1 2] [3 4] ] print(countOperations(a b))
// C# program to find number of transformation // to make two Matrix Equal using System; class GfG { static int countOperations(int[ ] a int[ ] b) { int n = a.GetLength(0); int m = a.GetLength(1); // Create difference matrix (a = a - b) for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i j] -= b[i j]; } } // Check if transformation is possible using the // property a[i j] - a[i 0] - a[0 j] + a[0 0] // should be 0 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (a[i j] - a[i 0] - a[0 j] + a[0 0] != 0) { return -1; } } } int result = 0; // Add operations needed for first column for (int i = 0; i < n; i++) { result += Math.Abs(a[i 0]); } // Add operations needed for // first row (excluding a[0 0]) for (int j = 0; j < m; j++) { result += Math.Abs(a[0 j] - a[0 0]); } return result; } static void Main(string[] args) { int[ ] a = { { 1 1 } { 1 1 } }; int[ ] b = { { 1 2 } { 3 4 } }; Console.WriteLine(countOperations(a b)); } }
// JavaScript program to find number of transformation // to make two Matrix Equal function countOperations(a b) { let n = a.length; let m = a[0].length; // Create difference matrix (a = a - b) for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { a[i][j] -= b[i][j]; } } // Check if transformation is possible using the // property a[i][j] - a[i][0] - a[0][j] + a[0][0] should // be 0 for (let i = 1; i < n; i++) { for (let j = 1; j < m; j++) { if (a[i][j] - a[i][0] - a[0][j] + a[0][0] !== 0) { return -1; } } } let result = 0; // Add operations needed for first column for (let i = 0; i < n; i++) { result += Math.abs(a[i][0]); } // Add operations needed for // first row (excluding a[0][0]) for (let j = 0; j < m; j++) { result += Math.abs(a[0][j] - a[0][0]); } return result; } //Driver code let a = [ [ 1 1 ] [ 1 1 ] ]; let b = [ [ 1 2 ] [ 3 4 ] ]; console.log(countOperations(a b));
出力
3
時間計算量: O(n*m)
補助スペース: ○(1)