Dados dois matrizes a e b de tamanho n*m . A tarefa é encontrar o necessário número de etapas de transformação para que ambas as matrizes se tornem iguais. Imprimir -1 se isso não for possível.
O transformação passo é o seguinte:
- Selecione qualquer matriz entre duas matrizes.
- Escolha qualquer um linha/coluna da matriz selecionada.
- Incrementar cada elemento do select linha/coluna por 1.
Exemplos:
Entrada:
uma[][] = [[1 1]
[11]]b[][] = [[1 2]
[3 4]]Saída : 3
Explicação :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Entrada :
uma[][] = [[1 1]
[10]]b[][] = [[1 2]
[3 4]]Saída : -1
Explicação : Nenhuma transformação tornará aeb iguais.
Abordagem:
A ideia é que incrementando qualquer linha/coluna em matriz uma é equivalente a diminuindo a mesma linha/coluna em matriz b .
Isto significa que em vez de rastrear ambas as matrizes podemos trabalhar com a sua diferença (a[i][j] - b[i][j]). Quando incrementamos uma linha em ' um' todos os elementos naquela linha aumentam em 1, o que é o mesmo que todos os elementos naquela linha da matriz de diferença aumentando em 1. Da mesma forma, quando incrementamos uma coluna em ' um' é equivalente a aumentar todos os elementos dessa coluna da matriz de diferenças em 1.
Isso nos permite transformar o problema em trabalhar com apenas uma matriz.
Determine se existe alguma solução ou não:
Depois de criar o matriz de diferença para cada célula uma[i][j] (excluindo a primeira linha e a primeira coluna) verificamos se
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Se esta equação não for válida para nenhuma célula, podemos concluir imediatamente que não existe solução.
Por que isso funciona?
Pense em como linha e coluna operações afetam cada célula: quando realizamos x operações na linha eu e e operações na coluna j uma[i][j] muda por (x + y) uma[i][0] muda por x (somente operações de linha) a[0][j] muda por y (somente operações de coluna) e a[0][0] é afetado por nem linha i nem coluna j operações. Portanto (x + y) - x - y + 0 = 0 deve valer para qualquer solução válida. Se esta equação não for válida para nenhuma célula, significa que nenhuma sequência de operações em linhas e colunas pode transformar uma matriz em outra.
Calcule o número de transformações necessárias:
C++Para calcular o número de transformações necessárias, precisamos apenas olhar para o primeira linha e primeira coluna porque:
- Primeiro resumimos |a[i][0]| para todos i (cada primeiro elemento da coluna) porque isso representa quantas operações de linha precisamos. Para cada linha i precisamos |a[i][0]| operações para tornar esse elemento de linha zero.
- Então resumimos |a[0][j] - a[0][0]| para todo j (cada elemento da primeira linha menos o primeiro elemento) porque isso representa operações adicionais de coluna necessárias. Subtraímos a[0][0] para evitar contá-lo duas vezes, pois as operações de linha já afetaram este elemento.
- A soma desses dois nos dá o número mínimo de operações necessário, pois as operações de linha tratam das diferenças da primeira coluna e as operações de coluna tratam das diferenças restantes na primeira linha.
// 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));
Saída
3
Complexidade de tempo: O(n*m)
Espaço Auxiliar: O(1)