IEEE XTREME 7.0

Solution Facebook Hacker Cup 2013

Square Detector

You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.

You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.

Input

The first line of the input consists of a single number T, the number of test cases.

Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either "." symbolizing a white cell, or "#" symbolizing a black cell. Every test case contains at least one black cell.

Output

For each test case i numbered from 1 to T, output "Case #i: ", followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells.

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 20

Example

Test cases 1 and 5 represent valid squares. Case 2 has an extra cell that is outside of the square. Case 3 shows a square not filled inside. And case 4 is a rectangle but not a square.

Example input

5
4
..##
..##
....
....
4
..##
..##
#...
....
4
####
#..#
#..#
####
5
#####
#####
#####
#####
.....
5
#####
#####
#####
#####
#####

Example output 

Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO
Case #5: YES



Note: Just omit the last line in your outpfile cause that is extra and your file won't be 
accepted.


SOLUTION :
 #include <iostream>  
 #include <vector>  
 #include <algorithm>  
 #include <fstream>  
 using namespace std;  
 int main()  
 {  
   //ifstream in("in.txt");  
   //ofstream out("out.txt");  
   char a[21][21];  
   int t,num=0,n;  
   cin>>t;  
   //INPUT FROM THE USER  
   while(t--)  
   {  
     num++;  
     int i,j,flag=0,k,x,count=0,final_count=0;  
           vector<int> y;  
     cin>>n;  
     for(i=1;i<=n;i++)  
   {  
     for(j=1;j<=n;j++)  
     {  
       cin>>a[i][j];  
       if (a[i][j]=='#')  
       {  
         final_count++;  
       }  
     }  
   }  
   //STORING FIRST ROW WITH THE OCCURENCE OF "#"  
   for(i=1;i<=n;i++)  
   {  
     for(j=1;j<=n;j++)  
     {  
       if (a[i][j]=='#')  
       {  
           flag=1;  
           x=i;  
           y.push_back(j);  
           //cout<<i<<","<<j<<endl;  
       }  
     }  
     if(flag==1)  
     {  
       break;  
     }  
   }  
   int z=0;  
   for(i=1;i<=n;i++)  
   {  
     for(j=1;j<=n;j++)  
     {  
       if (a[i][j]=='#')  
       {  
         for(k=0;k<y.size();k++)  
         {  
           if(j==y[k])  
           {  
             count++;  
           }  
         }  
       }  
     }  
     if(count==y.size())  
     {  
         //cout<<"row "<<i<<"matched"<<endl;  
         if(x==i)  
         {  
           z++;  
           x++;  
         }  
     }  
     count=0;  
   }  
      //cout<<"z "<<z <<" y.size() "<<y.size()<<endl;  
   cout<<"Case #"<<num;  
   if(final_count!=(z*z))  
   {  
     cout<<": NO"<<endl;  
   }  
   else if(z==y.size())  
   {  
     cout<<": YES"<<endl;  
   }  
   else  
   {  
     cout<<": NO"<<endl;  
   }  
   }  
 return 0;  
 }  




WANT A PROPER EXPLANATION FOR THIS SOLUTION, JUST Comment below . 
#Happy Coding

#CodeScripter

Go Ahead,Do Mistakes,Take Challenges !

Be brave. Even if you’re not, pretend to be. No one can tell the difference. Don’t allow the phone to interrupt important moments. It’s there for your convenience, not the callers. Don’t be afraid to go out on a limb. That’s where the fruit is. 

Don’t burn bridges. You’ll be surprised how many times you have to cross the same river. Don’t forget, a person’s greatest emotional need is to feel appreciated. Don’t major in minor things. Don’t say you don’t have enough time. You have exactly the same number of hours per day that were given to Pasteur, Michaelangelo, Mother Teresa, Helen Keller, Leonardo Da Vinci, Thomas Jefferson, and Albert Einstein. Don’t spread yourself too thin. Learn to say no politely and quickly. Don’t use time or words carelessly. Neither can be retrieved.

Don’t waste time grieving over past mistakes Learn from them and move on. Every person needs to have their moment in the sun, when they raise their arms in victory, knowing that on this day, at his hour, they were at their very best.

Get your priorities straight. No one ever said on his death bed, ‘Gee, if I’d only spent more time at the office’. Give people a second chance, but not a third. Judge your success by the degree that you’re enjoying peace, health and love. Learn to listen. Opportunity sometimes knocks very softly. Leave everything a little better than you found it. Live your life as an exclamation, not an explanation. Loosen up. Relax. Except for rare life and death matters, nothing is as important as it first seems.

Never cut what can be untied. Never overestimate your power to change others. Never underestimate your power to change yourself. Remember that overnight success usually takes about fifteen years. Remember that winners do what losers don’t want to do. Seek opportunity, not security. A boat in harbor is safe, but in time its bottom will rot out. Spend less time worrying who’s right, more time deciding what’s right. Stop blaming others. Take responsibility for every area of your life.

Success is getting what you want. Happiness is liking what you get. The importance of winning is not what we get from it, but what we become because of it. When facing a difficult task, act as though it’s impossible to fail.