Code:
/* groups.c Finds distinct contiguous groups in a matrix.
Status: ok
*/
#include <stdio.h>
#define Rows 6
#define Cols 9
int trails(int a[Rows][Cols], int r, int c);
int main(void) {
int r, c, group, links, ready, hit;
int a[Rows][Cols] = {
{ 0,0,0,0,0,0,0,0,0 },
{ 0,1,1,1,1,1,0,0,0 },
{ 0,0,1,0,0,0,0,1,0 },
{ 0,1,0,1,0,1,1,1,0 },
{ 0,0,1,1,1,0,1,1,0 },
{ 0,0,0,0,0,0,0,0,0 },
};
printf("\n\n");
group = links = 0;
ready = 1;
for(r=1, hit= 0;r<Rows-1;r++) {
putchar('\n');
for(c= 1; c<Cols-1;c++) {
printf("%d ", a[r][c]);
if(a[r][c]) {
if(a[r-1][c] == 1) { //12 o'clock
links++; ready = 0;
}
if(a[r][c+1] == 1) { //3 o'clock
links++;
hit = trails(a, r, c);
if(hit) {
ready = 0;
}
}
if(a[r][c-1] == 1) { //9 o'clock
links++;
}
}
if(!links) ready = 1;
if(hit == 0 && ready == 1 && a[r][c]) {
group++;
ready = 0;
}
links = 0; hit = 0;
}
}
printf("\n This matrix has 4 distinct groups. I found: %d groups ", group);
printf("\n\n\t\t\t press enter when ready ");
r = getchar();
return 0;
}
/* recursively calls itself to follow the trail of links upward and to the
right, to see if it hits (is linked with), a previous sqr in an already
counted group.
*/
int trails(int a[Rows][Cols], int r, int c) {
//hit = 1 means you've hit a previous groups sqr
static hit = 0;
int link = 1;
while(link > 0) {
if(a[r-1][c] == 1) { //12 o'clock
hit = 1; break;
}
else
link = 0;
if(a[r][c+1] == 1) { //3 o'clock
trails(a, r, c+1);
}
else
link = 0;
}
return hit;
}