Matrix Game : Flip The World

Composition and Dimension of Matrix

There is an binary matrix of dimension M x N.
Binary Matrix : Matrix with entries from the Boolean domain B = {0, 1}

Make a move

1. Select any two integer , say x and y such that 1<=x<=M and 1<=y<=N .
2. All the elements in the rectangle or square formed by (1,1) and (x,y) are to be toggled ,i.e. 0 is made 1 and
    1 is made 0.
                                 (1,1) . . . . . . . . . . . . . .
                                    .                .
                                    .                .
                                    .                .
                                    .............(x,y)

 Note : (1,1) is always taken as one of the two co-ordinates.

For Example : Given a  matrix 4 x 4 (M=4, N=4)

                          1 0 1 0
                          1 1 0 0
                          1 0 0 1
                          1 1 1 0

If we choose x=2 and y=3, then new matrix after toggle will be :

                          0 1 0 0
                          0 0 1 0
                          1 0 0 1
                          1 1 1 0


Aim of the Game

Sole aim of the game is to change all elements of the matrix to 1.
This requires some number of moves to be made in order to get the all-ones matrix out of binary matrix.

Calculating number of steps required

Algorithm:-

1.  Input : row , column and array element .
2.  for i from row-1 to 0 do
3.  for j from column-1 to 0 do
4.  if  array[row][column]==0 then
5.  Toggle the matrix
6.  increment the counter
7. Output : all-ones matrix  and number of moves


Complexity : O(n2)


Java Implementation of the algorithm



import java.util.Scanner;

public class FlipTheWorld {


    public static void main(String[] args) {
       
        System.out.println("Enter row (M): ");  //Input rows
        Scanner scan = new Scanner(System.in);
        int row = Integer.parseInt(scan.nextLine());
       
        System.out.println("Enter column (N): ");  //Input columns
        Scanner scan1 = new Scanner(System.in);
        int column = Integer.parseInt(scan1.nextLine());
       
        int array[][] = new int[row][column];
        int count = 0;
        for(int r=0;r<row;r++){                       // Input binary matrix
            System.out.println("Enter row "+(r+1));
            for(int c=0;c<column;c++){
                Scanner scan2 = new Scanner(System.in);
                array[r][c]=Integer.parseInt(scan2.nextLine());
            }
        }
        System.out.println("Original : ");
        display(array,row,column);
        for(int r=row-1;r>=0;r--){                                
            for(int c=column-1;c>=0;c--){
                if(array[r][c]==0){
                    toggle(array,r,c);
                    count = count+1;
                    System.out.println();
                    System.out.println("Matrix after toggle "+count);
                    display(array,row,column);
                }
                   
            }
        }
        int sum = 0;                                        
        for(int i=0;i<row;i++){                            //Checking if resultant matrix is all-ones or not
            for(int j=0;j<column;j++){                     //for this to check , compare the sum of elements
                                                           // of resultant matrix with the product of row and column.
        sum = sum + array[i][j];
            }
        }
        if(sum==row*column){
        System.out.println();
        System.out.println();
        System.out.println("Final : ");
        display(array,row,column);
        System.out.println();
        System.out.println("Number of steps : "+count);
            }
        else{
            System.out.println("Failure of algo");
        }

    }
   
    static void display(int[][] array,int row,int column) {         //function to display matrix
        for(int r=0;r<row;r++){
            System.out.println();
            for(int c=0;c<column;c++){
                System.out.print(array[r][c]);
            }
        }
       
    }

    static void toggle(int array[][],int row,int column){          //function to toggle the matrix
        for(int r=0;r<=row;r++){
            for(int c=0;c<=column;c++){
                if(array[r][c]==1)
                    array[r][c]=0;
                else
                    array[r][c]=1;
            }
        }
    }

}









Output :

Original :

1010
1100
1001
1110
Matrix after toggle 1

0101
0011
0110
0001

Matrix after toggle 2

1011
1101
1000
1111

Matrix after toggle 3

0100
0010
0111
1111

Matrix after toggle 4

1100
1010
1111
1111

Matrix after toggle 5

0011
0101
1111
1111

Matrix after toggle 6

1101
1011
1111
1111

Matrix after toggle 7

0001
0111
1111
1111

Matrix after toggle 8

1001
1111
1111
1111

Matrix after toggle 9

0111
1111
1111
1111

Matrix after toggle 10

1111
1111
1111
1111

Final :

1111
1111
1111
1111

Number of steps : 10
Time Taken= 0.011 sec