# HackerEarth Mosaics and holes problem solution

In this HackerEarth Coprimes problem solution, John wants to cover his yard floor with mosaics. The yard floor is a n x m matrix and each cell is either a mosaic or a hole. John has invented the flipper machine. This machine has a size of k and can select a k x k square of the yard and flip the cells in it. By this action, every hole in the square becomes a mosaic and every mosaic in the square becomes a hole. It is illustrated by the following example:

The 2 x 2 square on the left has been flipped to the right one by the flipper with the size 2 and blacks are holes and whites are mosaics.

Help John to cover the floor of the yard completely by mosaics by using this machine. In each step, John selects a k x k square of the yard floor and sets the machine on it. He wants to compute the minimum steps needed to repair the yard floor.

## HackerEarth Mosaics and holes problem solution.

`#include<bits/stdc++.h>using namespace std;const int M=1e3+10;int ans,a[M][M],b[M][M],n,m,k;void prt()//used for debug{  cout<<"a: "<<endl;  for(int i=1;i<=n;i++)    {      for(int j=1;j<=m;j++)    cout<<a[i][j]<<" ";      cout<<endl;    }  cout<<"b: "<<endl;  for(int i=1;i<=n;i++)    {      for(int j=1;j<=m;j++)    cout<<b[i][j]<<" ";      cout<<endl;    }  cout<<endl;}int32_t main(){  cin>>n>>m>>k;  for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)      scanf("%d",&a[i][j]);  for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)      {    a[i][j]^=b[i][j];    b[i+1][j]^=b[i][j];    b[i][j+1]^=b[i][j];    b[i+1][j+1]^=b[i][j];    if(a[i][j]==0 && i+k-1<=n && j+k-1<=m)      {        ans++;        a[i][j]^=1;        b[i+1][j]^=1;        b[i][j+1]^=1;        b[i+1][j+1]^=1;        b[i+k][j]^=1;        b[i][j+k]^=1;        b[i+k][j+k]^=1;      }    else if(a[i][j]==0)      return cout<<-1<<endl,0;    //prt();      }  cout<<ans<<endl;  return 0;}`

### Second solution

`#include<bits/stdc++.h>using namespace std;const int maxn = 1000 + 10;bool b[maxn][maxn];bool ps[maxn][maxn];bool ar[maxn][maxn];int main(){    int n, m, k;    cin >> n >> m >> k;    for(int i = 1; i <= n; i++)    for(int j = 1; j <= m; j++)        cin >> b[i][j];    int ans = 0;    for(int i = 1; i <= n; i++)    for(int j = 1; j <= m; j++){        ps[i][j] = ps[i - 1][j - 1] ^ ps[i][j] ^ ps[i - 1][j] ^ ps[i][j - 1];        if(ps[i][j] == b[i][j]){        if(i + k > n + 1 || j + k > m + 1)            return cout << -1 << endl , 0;        ps[i][j] ^= 1;        ps[i + k][j] ^= 1;        ps[i][j + k] ^= 1;        ps[i + k][j + k] ^= 1;        ans++;        }    }    cout << ans << endl;}`