#include<stdio.h>
#include<malloc.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include<time.h>

# define N 5000
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///// Linked List /////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct node{
int matrow;
int matcol;
struct node *next;
}

*temp,*temp1,*f,*r;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////// initialize //////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void init(){ f=r=NULL;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////// insert ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void insert(int x, int y){
temp1=(struct node*)malloc(sizeof(struct node));
temp1->matrow=x;
temp1->matcol=y;
temp1->next=NULL;
if(f==NULL)
{
f=r=temp1;
}
else{ r->next=temp1;
r=temp1;
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///// ispath //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int ispath (int* a)
{
int i;
int* visited;
visited = (int *) malloc(N*N*sizeof(int));
for(i=0; i<N*N; i++)
{
visited[i]=0;
}

init();
for (i=0; i< N; i++)
{
if(a[i]==1)
{
insert(i,0);
}

visited[i]=1;
}

temp = f;
while ( temp != NULL)
{
//down
if( (temp->matrow) <(N -1) && a[ N*(temp->matcol)+(temp->matrow)+1]==1 && visited[ N*(temp->matcol)+(temp->matrow)+1]==0 )
{
insert((temp->matrow)+1, temp->matcol);
visited[ N*(temp->matcol)+(temp->matrow)+1]=1;
}

//up
if( (temp->matrow) > 0 && a[N*(temp->matcol)+(temp->matrow)-1] ==1 && visited[N*(temp->matcol)+(temp->matrow)-1]==0 )
{
insert((temp->matrow )-1, temp->matcol);
visited[N*(temp->matcol)+(temp->matrow)-1]=1;
}

//left
if( (temp->matcol) >0 && a[((temp->matcol)-1)*N+temp->matrow]==1 && visited[((temp->matcol)-1)*N+temp->matrow]==0 )
{
insert(temp->matrow, (temp->matcol) -1);
visited[((temp->matcol)-1)*N+temp->matrow]=1;
}

//right
if( (temp->matcol) < (N-2) && a[((temp->matcol)+1)*N+temp->matrow]==1 && visited[((temp->matcol)+1)*N+temp->matrow]==0 )
{
insert(temp->matrow, (temp->matcol) +1);
visited[((temp->matcol)+1)*N+temp->matrow]=1;
}

if( (temp->matcol) ==(N -2) && a [((temp->matcol)+1)*N+temp->matrow]==1 )
{
while(f)
{
temp=f;
f=f->next;
free(temp);
}
free(visited);
return 1;
}

temp = temp->next;
}

while(f)
{
temp=f;
f=f->next;
free(temp);
}
free(visited);
return 0;

}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///// swap ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void swap (int a, int b)
{
a=a+b;
b=a-b;
a=a-b;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///// strans //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void strans( int* mtx )
{
int i,j;
for( i=0; i< N ; i++)
{
for(j=0;j<N;j++)
{
if(mtx[j*N+i]!=10)
{
mtx[j*N+i]=1-mtx[j*N+i];
}
}
}

for(i=0;i<N;i++)
{
for(j=0;j<=i;j++)
{
swap(mtx[j*N+i],mtx[i*N+j]);
}
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{

int r0,r1,r2;
double p,q,e,lambda1,lambda2,lambda0;

printf(“Total visible area is %d x %d\n\n”,N,N);
printf(“Radius of colour 0 in integer\n”);
scanf(“%d”, & r0);
printf(“Radius of colour 1 in integer\n”);
scanf(“%d”, & r1);
printf(“Radius of colour 2 in integer\n”);
scanf(“%d”, & r2);

printf(“Intensity of colour 0\n”);
scanf(“%lf”, & lambda0);
printf(“Intensity of colour 1\n”);
scanf(“%lf”, & lambda1);
printf(“Intensity of colour 2\n”);
scanf(“%lf”, & lambda2);

p= (lambda0/(lambda1+lambda2+lambda0));
q= (lambda1/(lambda1+lambda2+lambda0));

printf(“error (enter a number between 0 and 1)\n”);
scanf(“%lf”, & e);
printf(“\n\n”);

int i,j,k,l,s;

int d[3][3];
for(i =0; i<3; i++)
{
for(j=0; j<3; j++)
{
d[i][j]=0;
}
}

for(s=0;s<1000;s++)
{

int * a0; int* a1; int* a2;

// N x N matrices with all entries 10.

a0 = (int *) malloc(N*N*sizeof(int));
a1 = (int *) malloc(N*N*sizeof(int));
a2 = (int *) malloc(N*N*sizeof(int));
for( i=0; i<N*N; i++)
{
a0[i]=10;
a1[i]=10;
a2[i]=10;
}

int y; // y takes value (0,1,2) with probabilities (p, q, 1-p-q)

int count_empty=3*N*N; // total number of zeros

int minimum_count_empty = floor(e*count_empty);

int Row, Column, r; // r is radius

double coinToss=0; // coinToss is uniform (0,1)

srand(time(NULL)); // seeding

while(count_empty > minimum_count_empty)
{
Row=floor(((double) rand() / (double)RAND_MAX)*N); // row and column are discrete uniform {0,1,2,…,N-1}
Column=floor(((double) rand() / (double)RAND_MAX)*N);

coinToss= ((double) rand() / (double)RAND_MAX);

if(coinToss<p){y=0; r=r0;}
else if (coinToss<(p+q)){y=1;r=r1;}
else{y=2;r=r2;}

// Matrix update

if(y==0)
{
for( i=Row-r; i<=Row+r; i++)
{
for(j=Column-r; j<=Column+r; j++)
{
k=(i+2*N)%N;
l=(j+2*N)%N;
if (a0[l*N+k]==10)
{
count_empty–;
a0[l*N+k]=0;
}
if (a2[l*N+k]==10)
{
count_empty–;
a2[l*N+k]=1;
}
}
}
}

if(y==1)
{
for( i=Row-r; i<=Row+r; i++)
{
for(j=Column-r; j<=Column+r; j++)
{
k=(i+2*N)%N;
l=(j+2*N)%N;
if (a0[l*N+k]==10)
{
count_empty–;
a0[l*N+k]=1;
}
if (a1[l*N+k]==10)
{
count_empty–;
a1[l*N+k]=0;
}
}
}
}

if(y==2)
{
for( i=Row-r; i<=Row+r; i++)
{
for(j=Column-r; j<=Column+r; j++)
{
k=(i+2*N)%N;
l=(j+2*N)%N;
if (a2[l*N+k]==10)
{
count_empty–;
a2[l*N+k]=0;
}
if (a1[l*N+k]==10)
{
count_empty–;
a1[l*N+k]=1;
}
}
}
}
}

if(ispath(a0)==1)
{
d[0][1]=d[0][1]+1;
}
else
{
strans(a0);
if ( ispath (a0)==1 )
{
d[0][0]=d[0][0]+1;
}
else
{
d[0][2]=d[0][2]+1;
}
}

if(ispath(a1)==1)
{
d[1][1]=d[1][1]+1;
}
else
{
strans(a1);
if ( ispath (a1) ==1)
{
d[1][0]=d[1][0]+1;
}
else
{
d[1][2]=d[1][2]+1;
}
}

if(ispath(a2)==1)
{
d[2][1]=d[2][1]+1;
}
else
{
strans(a2);
if ( ispath (a2)==1 )
{
d[2][0]=d[2][0]+1;
}
else
{
d[2][2]=d[2][2]+1;
}
}

free(a0);
free(a1);
free(a2);

}

printf(“In model 0-1 color 0 path %d, color 1 path %d, no path %d\n”,d[0][0],d[0][1],d[0][2]);
printf(“In model 1-2 color 1 path %d, color 2 path %d, no path %d\n”,d[1][0],d[1][1],d[1][2]);
printf(“In model 2-0 color 2 path %d, color 0 path %d, no path %d\n”,d[2][0],d[2][1],d[2][2]);

return 0;
}