Tuesday, November 6, 2012

Number of closed rectangles in a matrix

Given a matrix containing only 1 and 0, find the number of closed rectangles. A closed rectangle is represented by at least one 0 surrounded by eight 1's. There is no overlap of closed rectangles.

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt);
int A[][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{1,1,1,0,0,0,1,1,1,1},
{0,0,1,0,0,0,1,0,1,1},
{1,1,1,0,0,0,1,1,1,1}
};
int cnt=0;
for(int i=0;i<8;i++)
{
for(int j=0;j<10;j++)
{
cout<<A[i][j]<<" ";
}
cout<<endl;
}
for(int i=0;i<8;i++)
{
for(int j=0;j<10;j++)
{
if(A[i][j]>0)
{
cnt=rectangle(A,i,j,8,10,cnt);
}
}
}
cout<<"The number of closed rectangles is: "<<cnt<<endl;
}

int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt)
{
cnt++;
int rnd=1;
if(i<d1-1 && j<d2-1 && A[i+1][j+1]==0)
{
j++;
while(j<d2 && i<d1-1 && A[i][j]==1 && A[i+1][j]==0)
{
A[i][j]=-1*cnt;
j++;
}
A[i][j]=-1*cnt;
rnd++;
}
if(i<d1-1 && j>0 && A[i+1][j-1]==0 && A[i][j]==-1*cnt)
{
i++;
while(i<d1 && j>0 && A[i][j]==1 && A[i][j-1]==0)
{
A[i][j]=-1*cnt;
i++;
}
A[i][j]=-1*cnt;
rnd++;
}
if(i>0 && j>0 && A[i-1][j-1]==0 && A[i][j]==-1*cnt)
{
j--;
while(j>=0 && i>0 && A[i-1][j]==0 && A[i][j]==1)
{
A[i][j]=-1*cnt;
j--;
}
A[i][j]=-1*cnt;
rnd++;
}
if(i>0 && j<d2-1 && A[i-1][j+1]==0 && A[i][j]==-1*cnt)
{
i--;
while(i>=0 && j<d2-1 && A[i][j+1]==0 && A[i][j]==1)
{
A[i][j]=-1*cnt;
i--;
}
A[i][j]=-1*cnt;
rnd++;
}
if(rnd!=5 || (A[i][j]!=0 && A[i][j]!=A[i][j+1]))
{
cnt--;
}
return cnt;
}
Output:
The number of closed rectangles is: 2

No comments:

Post a Comment