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;
}

coding problems solutions