Mousetrap in a Labyrinth
In
an NxN dimension matrix a mouse wants to cross from
north to south. We say 1’s are roads and 0’s are walls. Mouse can pass cross,
horizontal or vertical ways.
The Algorithm
C Source Code
typedef struct {
int x;
int y;
}rec;
rec buldum[64]={0};
int giris[8]={0};
int point=0;
int found=0;
int labirent[8][8]={{0,1,0,0,1,0,0,0},
{0,0,1,0,0,1,0,0},
{1,0,1,0,1,0,0,0},
{0,1,1,0,0,0,1,0},
{0,0,1,0,1,1,1,0},
{0,1,0,0,0,1,0,0},
{1,0,0,0,0,1,0,0},
{0,1,0,1,0,0,0,0}};
void Find(int i,int j)
{
int k;
if(found)
return;
if((labirent[i][j])&&(j>=0)&&(j<8)&&(i>=0)&&(i<8))
{
labirent[i][j]=0;
buldum[point].x=i;
buldum[point].y=j;
point++;
Find(i+1,j);
Find(i+1,j-1);
Find(i+1,j+1);
Find(i,j-1);
Find(i,j+1);
Find(i-1,j-1);
Find(i-1,j+1);
if(!found)
{
labirent[i][j]=1;
point--;
}
}
if(i==8)
{
found=1;
for(k=0;k<point;k++)
{
printf("%d %d,",buldum[k].x,buldum[k].y);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int sayi,n=8,m;
int i,k;
m=0;
for(i=0;i<8;i++)
{
if(labirent[0][i])
{
giris[m]=i;
m++;
}
}
for(i=0;i<m;i++)
{
point=0;
found=0;
Find(0,giris[i]);
}
return 0;
}
Example Execution
Sample matrix
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
3 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
4 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
6 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
7 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
8 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
Found labyrinth roads:
1 2
2 3
3 3
4 3
5 3
6 2
7 1
8 2