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

int ROW,COL;
typedef struct Node node;

int **allocateTable(int row,int col); 
void initTable(int **table);
void initNeighborTB(int **table1,int **table2);
int countNeighbor(int **table,int pos_i,int pos_j);
void intit_LinkList(node **mayl,node **mayd,int **aliveTB,int **neightborTB);
void displayTable(int **table);
void updateNewlive(int **aliveTB,int **neighborTB,node *maylive,node **newlive);
void updateNewdie(int **aliveTB,int **neighborTB,node *maydie,node **newdie);
void predict_for_newlive(int **aliveTB,int **neighborTB,
node *newlive,node **maylive, node **maydie);
void predict_for_newdie(int **aliveTB,int **neighborTB,
node *newdie,node **maylive, node **maydie);
void traverse(node *list);
int CountAlive(int **table);

node *createNode();
void addNode(node **list,int i,int j);
void removeALLNODE(node **list);

struct Node{
       int i;
       int j;
       struct Node *next;
};
int main()
{   int i;
    int numalive;
    int numloop=0;
    int **aliveTable;
    int **neighborsTable;
    node *maylive;
    node *maydie;
    node *newlive;
    node *newdie;
    maylive      = NULL;
    maydie       = NULL;
    newlive      = NULL;
    newdie       = NULL;
    clrscr();
    printf("Enter Row = ");scanf("%d",&ROW);
    printf("Enter COL = ");scanf("%d",&COL);
    aliveTable = allocateTable(ROW,COL);
    neighborsTable = allocateTable(ROW,COL);
    initTable(aliveTable);
    initNeighborTB(aliveTable,neighborsTable);
    displayTable(aliveTable);
    numalive = CountAlive(aliveTable);
    intit_LinkList(&maylive,&maydie,aliveTable,neighborsTable);
 
    while(numalive!=0&&numloop!=100)
    {
         removeALLNODE(&newlive); 
         removeALLNODE(&newdie);
         updateNewlive(aliveTable,neighborsTable,maylive,&newlive); 
         updateNewdie(aliveTable,neighborsTable,maydie,&newdie);    
         removeALLNODE(&maylive); 
         removeALLNODE(&maydie);
         numalive = CountAlive(aliveTable);
         printf("\n");
	     displayTable(aliveTable);

	     predict_for_newlive(aliveTable,neighborsTable,newlive,&maylive,&maydie);
	     predict_for_newdie(aliveTable,neighborsTable,newdie,&maylive,&maydie);
         numloop++;
    }

    free(aliveTable);    for(i=0;i<ROW;i++)free(aliveTable[i]);
    free(neighborsTable);for(i=0;i<ROW;i++)free(neighborsTable[i]);
    getch();
    return 0;
}
int CountAlive(int **table)
{  int numalive=0;
   int i,j;
    for(i=0;i<ROW;i++)
     for(j=0;j<COL;j++)
       if(table[i][j]==1)
          numalive++; 

    return numalive;
}

int **allocateTable(int row,int col)
{
    int **table,i;
    table = (int**)malloc(sizeof(int*)*row);
    for(i=0;i<row;i++)
	 *(table+i) = (int*)malloc(sizeof(int)*col);
    return table;
}

void initTable(int **table)
{
     int i,j;

     srand(time(NULL));
     for(i=0;i<ROW;i++)
	 for(j=0;j<COL;j++)
	    table[i][j] = rand()%2;
}

void initNeighborTB(int **table1,int **table2)
{
    int i,j;
    for(i=0;i<ROW;i++)
	 for(j=0;j<COL;j++)
	     table2[i][j] = countNeighbor(table1,i,j);
}

int countNeighbor(int **table,int pos_i,int pos_j)
{
    int neighbors = 0 ,x,y;
    for(x=pos_i-1;x<=pos_i+1;x++)
	 for(y=pos_j-1;y<=pos_j+1;y++)
	      if((x>=0&&x<ROW)&&(y>=0&&y<COL)&&(x!=pos_i||y!=pos_j))
		   if(table[x][y]==1) neighbors++;
    return neighbors;
}
void displayTable(int **table)
{
     int i,j;
     for(i=0;i<ROW;i++)
     {
	 for(j=0;j<COL;j++)
	    
	    
  printf("%3d",table[i][j]);  
    if(i==(ROW/2))        
    printf("\tNumStillAlive = %d",CountAlive(table));
     printf("\n");
	 
     }
}

node *createNode()
{
     node *list;
     list = (node*)malloc(sizeof(node));
     list->next = NULL;
     if(list==NULL) printf("Connot Allocate");
     return list;
}

void addNode(node **list,int x,int y)
{
     node *newNode;
     node *p;
     p = *list;
     while(p!=NULL)
     {
	if((p->i==x)&&(p->j)==y)
		return;
	p = p->next;
     }
     p = *list;
     newNode = createNode();
     newNode->i = x;
     newNode->j = y;
     *list = newNode;
     newNode->next = p;
}

void removeALLNODE(node **list)
{
     node *p,*q;
     p = *list;
     q = *list;
     *list = NULL;
     while(p!=NULL)
     {
         q = p->next;
         free(p);
         p = q;
     }
}

void intit_LinkList(node **mayl,node **mayd,int **aliveTB,int **neighborTB)
{
    int i,j;
    for(i=0;i<ROW;i++)
         for(j=0;j<COL;j++)
            if(aliveTB[i][j]==1)
            {
                addNode(mayd,i,j);                    
            }else{
                if(neighborTB[i][j]==3)
                     addNode(mayl,i,j);                   
            }
                         
}
void updateNewlive(int **aliveTB,int **neighborTB,node *maylive,node **newlive)
{
     while(maylive!=NULL)
     {
          if(neighborTB[maylive->i][maylive->j]==3)
          {
               addNode(newlive,maylive->i,maylive->j);
               aliveTB[maylive->i][maylive->j]=1;
          }
          maylive = maylive->next;                    
     }     
}

void updateNewdie(int **aliveTB,int **neighborTB,node *maydie,node **newdie)
{
     while(maydie!=NULL)
     {
          if(neighborTB[maydie->i][maydie->j]<=1||
              neighborTB[maydie->i][maydie->j]>=4)
          {
               addNode(newdie,maydie->i,maydie->j);
               aliveTB[maydie->i][maydie->j]=0;
          }
          maydie = maydie->next;                    
     }     
}

void predict_for_newlive(int **aliveTB,int **neighborTB,
node *newlive,node **maylive, node **maydie)
{
     int x,y;
     while(newlive!=NULL){
     for(x=(newlive->i)-1;x<=(newlive->i)+1;x++)
	  for(y=(newlive->j)-1;y<=(newlive->j)+1;y++)
	  {
	       if((x>=0&&x<ROW)&&(y>=0&&x<COL)
	       &&(x!=newlive->i||y!=newlive->j))
	       {
		    neighborTB[x][y]++;
		    if(aliveTB[x][y]==1)
		    {
			 if(neighborTB[x][y]<=1 || neighborTB[x][y]>=4)
			      addNode(maydie,x,y);
		    }else{
			 if(neighborTB[x][y]==3)
			      addNode(maylive,x,y);
		    }
	       }
	  }
	  newlive = newlive->next;
	  }
}

void predict_for_newdie(int **aliveTB,int **neighborTB,
node *newdie,node **maylive, node **maydie)
{
     int x,y;
     while(newdie!=NULL){
     for(x=(newdie->i)-1;x<=(newdie->i)+1;x++)
	  for(y=(newdie->j)-1;y<=(newdie->j)+1;y++)
	  {
	       if((x>=0&&x<ROW)&&(y>=0&&x<COL)
	       &&(x!=newdie->i||y!=newdie->j))
	       {
		    neighborTB[x][y]--;
		    if(aliveTB[x][y]==1)
		    {
			 if(neighborTB[x][y]<=1 || neighborTB[x][y]>=4)
			      addNode(maydie,x,y);
		    }else{
			 if(neighborTB[x][y]==3)
			      addNode(maylive,x,y);
		    }
	       }
	  }
	  newdie = newdie->next;
	  }
}

void traverse(node *list)
{
     if(list == 0)return;
     while(list != NULL)
     {
          printf("%d %d\n",list->i,list->j);
          list = list->next;
     }    
}