WAP to Finds Number of Blocks in Matrix Efficiently

Given a matrix, you need to find the number of blocks in it.
A block has the same numbers.
EG:
1 1 3
1 2 3
2 2 4
has 4 blocks namely,
1 1
1
2
2 2
3
3
4
1 2 3
4 5 6
7 8 9
has 9 blocks
1 1 1
1 1 3
4 4 5
has 4 blocks,
1 1 1
1 1
3
5
4 4

Algorithm

PS:Though Think Matrix As a Rectangle/Square a Block can have only vertical or Horizontal lines , arrangements of these lines makes a block so consider matrix elements as the end points on horizontal & vertical lines.its approximate though that can give idea how to approach up to some extent.

1. so first Visit all the elements row by row
2. Compare the value of the current element with the values of the above of the
current element left.
3. Compare the value of the current element with the values of the left of the
current element left.
4. Also compare current element with diagonal element & right element no
3. If value of above element is equal to at-least one of them, don't increment
blocks number Otherwise increment blocks number




#include






int numBlocks(int m, int n, int (*a)[3]){


int i, j;

int numblocks = 0;



for(i = 0 ; i < m; ++i){

for(j = 0 ; j < n; ++j){
//for above element
if(i - 1 >= 0 && a[i - 1][j] == a[i][j]) continue;
//for left element
if(j - 1 >= 0 && a[i][j - 1] == a[i][j]) continue;
//for diagonal & right element
if(i - 1 >= 0 && j + 1 < n && a[i - 1][j + 1] == a[i][j] && a[i][j+1] == a[i][j]) continue;

numblocks++;

}
}


return numblocks;


}


int main(){

int a[][3] = {
{1, 1, 3},
{1, 2, 3},
{2, 2, 4}
};

printf("%d\n", numBlocks(3, 3, a));

}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here http://ideone.com/ZeG8i