#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

const numVertices = 21;
const maxColumns = 2000;
int grid[numVertices][numVertices];
int smallGrid[numVertices][maxColumns];

bool nextB()
{
        int i;
        for (i=0; i < numVertices; i++)
        {
                grid[i][0] = 1-grid[i][0];
                if (grid[i][0] == 1)
                        return true;
        }
        return false;
}

void buildC()
{
        int i,j,sum;
        for(j=1;j< numVertices; j++)
        {
                for(i=0;i < numVertices-j;i++)
                {
                   sum = grid[i][j-1]+grid[i+1][j-1];
                   if (i > 0)
                        sum += grid[i-1][j-1];
                   if (j > 1)
                        sum += grid[i][j-2];
                   if (sum % 2 == 0)
                        grid[i][j] = 1;
                   else
                        grid[i][j] = 0;
                }
        }
}

void printC()
{
     for (int i=0; i < numVertices; i++)
    {
       for (int j=0; j < numVertices-i; j++)
       printf("%d",grid[i][j]);
       printf("\n");
    }
}

bool checkC()
{
    static int bfsQueue[numVertices*numVertices][2];
    static int mark[numVertices+1][numVertices+1];
    int head, tail;
    int i,j;

    for(i=0;i<=numVertices;i++)
        for(j=0;j <= numVertices;j++)
            mark[i][j]=0;

    for(i=0;i<=numVertices;i++)
    {
        bfsQueue[i][0]=i;
        bfsQueue[i][1]=numVertices-i;
        mark[i][numVertices-i]=1;
    }
    head=0;
    tail=numVertices;

    while (head <= tail)
    {
      i=bfsQueue[head][0];
      j=bfsQueue[head][1];
      head++;
      if ((i > 0) && (grid[i-1][j] == 1) &&
              (mark[i-1][j] == 0))
     {
       mark[i-1][j]=1;
       bfsQueue[tail+1][0]=i-1;
       bfsQueue[tail+1][1]=j;
       tail++;
      }
      if ((j > 0) && (grid[i][j-1] == 1) &&
                (mark[i][j-1] == 0))
      {
        mark[i][j-1]=1;
        bfsQueue[tail+1][0]=i;
        bfsQueue[tail+1][1]=j-1;
        tail++;
      }
      if ((i+j < numVertices) && (grid[i+1][j] == 1) &&
                 (mark[i+1][j] == 0))
      {
        mark[i+1][j]=1;
        bfsQueue[tail+1][0]=i+1;
        bfsQueue[tail+1][1]=j;
        tail++;
      }
      if ((i+j < numVertices) && (grid[i][j+1] == 1) &&
                  (mark[i][j+1] == 0))
      {
        mark[i][j+1]=1;
        bfsQueue[tail+1][0]=i;
        bfsQueue[tail+1][1]=j+1;
        tail++;
      }
    }
    for (i=0; i < numVertices;i++)
      for(j=0;j < numVertices-i; j++)
       if ((grid[i][j]== 1) && (mark[i][j] == 0))
        return false;
    return true;
}

bool nextSmallB(int m)
{
        int i;
        for (i=0; i < m; i++)
        {
                smallGrid[i][0] = 1-smallGrid[i][0];
                if (smallGrid[i][0] == 1)
                        return true;
        }
        return false;
}

bool nextColumn(int m, int c)
{
        int i,sum;
        for (i=0; i < m; i++)
        {
                sum = smallGrid[i][c-1];
                if (i > 0)
                        sum += smallGrid[i-1][c-1];
                if (i < m-1)
                        sum += smallGrid[i+1][c-1];
                if (c > 1)
                        sum += smallGrid[i][c-2];
                if (sum % 2 == 0)
                        smallGrid[i][c] = 1;
                else
                        smallGrid[i][c] = 0;
        }
        for (i = 0; i < m; i++)
                if (smallGrid[i][c] == 1)
                        return true;
        return false;
}

void printSmallC(int m, int c)
{
        int i,j;

        if (m <= c)
        {
                for(i=0; i < m; i++)
                {
                        for(j=0; j < c ; j++)
                                printf("%d",smallGrid[i][j]);
                        printf("\n");
                }
                printf("\n");
        }
        for (i=0; i < m; i++)
                if (smallGrid[i][c-1] == 0)
                        return;
        if (m <= c+1)
        {
                for(i=0; i < m; i++)
                {
                        for(j=0; j < c ; j++)
                                printf("%d",smallGrid[i][j]);
                        printf("0\n");
                }
                printf("\n");
        }
}

bool checkSmallC(int m, int c)
{
   static int bfsQueue[numVertices*maxColumns][2];
   static int mark[numVertices][maxColumns];
   int head, tail;
   int i,j;

   for(i=0;i< m ;i++)
     for(j=0;j < c;j++)
       mark[i][j]=0;

   for(i=0; i < m; i++)
    if (smallGrid[i][c-1] == 1)
    {
      bfsQueue[0][0]=i;
      bfsQueue[0][1] = c-1;
      mark[i][c-1] = 1;
      break;
    }
    head=0;
    tail=0;

    while (head <= tail)
    {
      i=bfsQueue[head][0];
      j=bfsQueue[head][1];
      head++;
      if ((i > 0) && (smallGrid[i-1][j] == 1) &&
          (mark[i-1][j] == 0))
     {
       mark[i-1][j]=1;
       bfsQueue[tail+1][0]=i-1;
       bfsQueue[tail+1][1]=j;
       tail++;
      }
      if ((i < m-1) && (smallGrid[i+1][j] == 1) &&
             (mark[i+1][j] == 0))
      {
        mark[i+1][j]=1;
        bfsQueue[tail+1][0]=i+1;
        bfsQueue[tail+1][1]=j;
        tail++;
      }
      if ((j > 0) && (smallGrid[i][j-1] == 1) &&
             (mark[i][j-1] == 0))
      {
        mark[i][j-1]=1;
        bfsQueue[tail+1][0]=i;
        bfsQueue[tail+1][1]=j-1;
        tail++;
      }
      if ((j < c-1) && (smallGrid[i][j+1] == 1) &&
             (mark[i][j+1] == 0))
      {
        mark[i][j+1]=1;
        bfsQueue[tail+1][0]=i;
        bfsQueue[tail+1][1]=j+1;
        tail++;
       }
     }
     for(i=0;i< m ;i++)
       for(j=0;j < c;j++)
        if ((smallGrid[i][j]== 1) && (mark[i][j] == 0))
         return false;
    return true;
}

void checkSmallGrids()
{
        int i,m,c;
        bool result;

        for (m=1; m < numVertices; m++)
        {
                printf("Grids with small side length %d\n",m);
                for(i=0; i < m; i++)
                        smallGrid[i][0] = 0;
                do
                {
                        c = 1;
                        for (;;)
                        {
                                if (!nextColumn(m,c))
                                {
                                        if (checkSmallC(m,c))
                                          printSmallC(m,c);
                                        break;
                                }
                                c++;
                                if (c > 1998)
                                {
                                        printf("%d\n",c);
                                        getch();
                                }
                        }
                } while (nextSmallB(m));
        }
        getch();
}

int main(int argc, char* argv[])
{
    int i;

    for(i=0; i < numVertices; i++)
        grid[i][0] = 0;
    i = 0;
    do
    {
        buildC();
        if (checkC())
        {
                        i++;
                        printC();
        }
    } while (nextB());
    printf("Candidate CODS: %d\n",i);
    getch();
    printf("Now checking small grids\n");
    checkSmallGrids();
    return 0;
}