Flip the World

Flip the world is a game. In this game a matrix of size $N\ast M$ is given, which consists of numbers. Each number can be 1 or 0 only. The rows are numbered from 1 to N, and the columns are numbered from 1 to M.

The following steps can be called a single move.

1. Select two integers x,y ($1\le x\le Nand1\le y\le M$) i.e. one square on the matrix.

2. All the integers in the rectangle denoted by $(1,1)$ and $(x,y)$ i.e. rectangle having top-left and bottom-right points as $(1,1)$ and $(x,y)$ are toggled(1 is made 0 and 0 is made 1).

For example, in this matrix ($N=4$ and $M=3$)

101

110

101

000

if we choose $x=3$ and $y=2$, the new state of the matrix would be

011

000

011

000

For a given state of matrix, the aim of the game is to reduce the matrix to a state where all numbers are 1. What is the minimum number of moves required?

Example:

Input:  n = 5, m = 5, v = {"00011", "00011", "00011", "11111", "11111"}
Output: 1

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int flipWorld(int n, int m, vector<string> v)
{
    int count = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = m - 1; j >= 0; j--)
        {
            //if current value of matrix is 0

            if (v[i][j] == '0')
            {
                //increment the count
                count++;

                //now for the rectangle

                for (int p = i; p >= 0; p--)
                {
                    for (int q = j; q >= 0; q--)
                    {
                        //flip the bits
                        v[p][q] = v[p][q] ^ 1;
                    }
                }
            }
        }
    }
    return count;
}
int main()
{

    int n = 5, m = 5;

    vector<string> v = {"00011",
                        "00011",
                        "00011",
                        "11111",
                        "11111"};

    cout << flipWorld(n, m, v) << "\n";

    return 0;
}