Donada una matriu binària de mida n on n > 3 . Un valor vertader (o 1) a la matriu significa actiu i fals (o 0) significa inactiu. Donat un nombre k, la tasca és trobar el recompte de cel·les actives i inactives després de k dies. Després de cada dia, l'estat de la cel·la i s'activa si les cel·les esquerra i dreta no són iguals i inactiva si la cel·la esquerra i dreta són iguals (ambdues 0 o 1).
Com que no hi ha cel·les abans de l'extrem esquerre i després de les cel·les de l'extrem dret, les cel·les de valor abans de l'esquerra i després de les cel·les de l'extrem dret sempre es consideren 0 (o inactives).
Exemples:
Input : cells[] = {1 0 1 1} k = 2 Output : Active cells = 3 Inactive cells = 1 After 1 day cells[] = {0 0 1 1} After 2 days cells[] = {0 1 1 1} Input : cells[] = {0 1 0 1 0 1 0 1} k = 3 Output: Active Cells = 2 Inactive Cells = 6 Explanation : After 1 day cells[] = {1 0 0 0 0 0 0 0} After 2 days cells[] = {0 1 0 0 0 0 0 0} After 3 days cells[] = {1 0 1 0 0 0 0 0} Input : cells[] = {0 1 1 1 0 1 1 0} k = 4 Output: Active Cells = 3 Inactive Cells = 5 L'únic important és assegurar-nos que mantenim una còpia de la matriu donada perquè necessitem els valors anteriors per actualitzar-los per al dia següent. A continuació es detallen els passos.
- Primer copiem la matriu cel·les[] a la matriu temp[] i fem canvis a la matriu temp[] segons la condició donada.
- En la condició es dóna que si la cel·la esquerra i dreta immediata de la cel·la i és inactiva o activa l'endemà, i esdevé inactiva, és a dir; (cel·les[i-1] == 0 i cel·les[i+1] == 0) o (cel·les[i-1] == 1 i cel·les[i+1] == 1), llavors les cel·les[i] = 0, aquestes condicions es poden aplicar mitjançant XOR de cel·les[i-1] i cel·les[i+1].
- Per a la temperatura de la cel·la d'índex 0'th[0] = 0^cel·les[1] i per a la temperatura de la cel·la d'índex (n-1)'th[n-1] = 0^cel·les[n-2].
- Ara, per a l'índex 1 a n-2, feu la següent operació temp[i] = cel·les[i-1] ^ cel·les[i+1]
- Repetiu el procés fins que s'hagin completat k dies.
A continuació es mostra la implementació dels passos anteriors.
C++
// C++ program to count active and inactive cells after k // days #include
// Java program to count active and // inactive cells after k days class GFG { // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days static void activeAndInactive(boolean cells[] int n int k) { // copy cells[] array into temp [] array boolean temp[] = new boolean[n]; for (int i = 0; i < n; i++) temp[i] = cells[i]; // Iterate for k days while (k-- > 0) { // Finding next values for corner cells temp[0] = false ^ cells[1]; temp[n - 1] = false ^ cells[n - 2]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for (int i = 1; i <= n - 2; i++) temp[i] = cells[i - 1] ^ cells[i + 1]; // Copy temp[] to cells[] for next iteration for (int i = 0; i < n; i++) cells[i] = temp[i]; } // count active and inactive cells int active = 0 inactive = 0; for (int i = 0; i < n; i++) if (cells[i] == true) active++; else inactive++; System.out.print('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive); } // Driver code public static void main(String[] args) { boolean cells[] = {false true false true false true false true}; int k = 3; int n = cells.length; activeAndInactive(cells n k); } } // This code is contributed by Anant Agarwal.
# Python program to count # active and inactive cells after k # days # cells[] - store current # status of cells # n - Number of cells # temp[] - to perform # intermediate operations # k - number of days # active - count of active # cells after k days # inactive - count of active # cells after k days def activeAndInactive(cellsnk): # copy cells[] array into temp [] array temp=[] for i in range(n+1): temp.append(False) for i in range(n): temp[i] = cells[i] # Iterate for k days while (k >0): # Finding next values for corner cells temp[0] = False^cells[1] temp[n-1] = False^cells[n-2] # Compute values of intermediate cells # If both cells active or # inactive then temp[i]=0 # else temp[i] = 1. for i in range(1n-2+1): temp[i] = cells[i-1] ^ cells[i+1] # Copy temp[] to cells[] # for next iteration for i in range(n): cells[i] = temp[i] k-=1 # count active and inactive cells active = 0 inactive = 0; for i in range(n): if(cells[i] == True): active+=1 else: inactive+=1 print('Active Cells ='active' ' 'Inactive Cells =' inactive) # Driver code cells = [False True False True False True False True] k = 3 n =len(cells) activeAndInactive(cells n k) # This code is contributed # by Anant Agarwal.
// C# program to count active and // inactive cells after k days using System; class GFG { // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate // operations k - number of days // active - count of active cells // after k days inactive - count // of active cells after k days static void activeAndInactive(bool []cells int n int k) { // copy cells[] array into // temp [] array bool []temp = new bool[n]; for (int i = 0; i < n; i++) temp[i] = cells[i]; // Iterate for k days while (k-- > 0) { // Finding next values // for corner cells temp[0] = false ^ cells[1]; temp[n - 1] = false ^ cells[n - 2]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for (int i = 1; i <= n - 2; i++) temp[i] = cells[i - 1] ^ cells[i + 1]; // Copy temp[] to cells[] // for next iteration for (int i = 0; i < n; i++) cells[i] = temp[i]; } // count active and inactive cells int active = 0 inactive = 0; for (int i = 0; i < n; i++) if (cells[i] == true) active++; else inactive++; Console.Write('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive); } // Driver code public static void Main() { bool []cells = {false true false true false true false true}; int k = 3; int n = cells.Length; activeAndInactive(cells n k); } } // This code is contributed by Nitin Mittal.
// PHP program to count active // and inactive cells after k // days // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate // operations k - number of days // active - count of active cells // after k days inactive - count of // active cells after k days function activeAndInactive($cells $n $k) { // copy cells[] array into // temp [] array $temp = array(); for ($i = 0; $i < $n ; $i++) $temp[$i] = $cells[$i]; // Iterate for k days while ($k--) { // Finding next values // for corner cells $temp[0] = 0 ^ $cells[1]; $temp[$n - 1] = 0 ^ $cells[$n - 2]; // Compute values of // intermediate cells // If both cells active // or inactive then temp[i]=0 // else temp[i] = 1. for ($i = 1; $i <= $n - 2; $i++) $temp[$i] = $cells[$i - 1] ^ $cells[$i + 1]; // Copy temp[] to cells[] // for next iteration for ($i = 0; $i < $n; $i++) $cells[$i] = $temp[$i]; } // count active and // inactive cells $active = 0;$inactive = 0; for ($i = 0; $i < $n; $i++) ($cells[$i] == 1)? $active++ : $inactive++; echo 'Active Cells = ' $active ' Inactive Cells = ' $inactive; } // Driver Code $cells= array(0 1 0 1 0 1 0 1); $k = 3; $n = count($cells); activeAndInactive($cells $n $k); // This code is contributed by anuj_67. ?> <script> // javascript program to count active and // inactive cells after k days // cells - store current status // of cells n - Number of cells // temp - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days function activeAndInactive(cells n k) { // copy cells array into temp array var temp = Array(n).fill(false); for (i = 0; i < n; i++) temp[i] = cells[i]; // Iterate for k days while (k-- > 0) { // Finding next values for corner cells temp[0] = false ^ cells[1]; temp[n - 1] = false ^ cells[n - 2]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for (i = 1; i <= n - 2; i++) temp[i] = cells[i - 1] ^ cells[i + 1]; // Copy temp to cells for next iteration for (i = 0; i < n; i++) cells[i] = temp[i]; } // count active and inactive cells var active = 0 inactive = 0; for (i = 0; i < n; i++) if (cells[i] == true) active++; else inactive++; document.write('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive); } // Driver code var cells = [ false true false true false true false true ]; var k = 3; var n = cells.length; activeAndInactive(cells n k); // This code is contributed by Rajput-Ji </script>
Sortida
Active Cells = 2 Inactive Cells = 6
Complexitat temporal: O(N*K) on N és la mida d'una matriu i K és el nombre de dies.
Espai auxiliar: O(N)
Aquest article és revisat per l'equip de geeksforgeeks. Si teniu un millor enfocament per a aquest problema, si us plau, compartiu.