Facebook Hacker Cup 2014 – Qualification Round Problem 'Square Detector'

This is easiest problem of this year's hackercup and straightforward to solve  :)

Problem Statement :

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.

Sample Input :

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


Sample Output :

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

Solving problem :
There are few observations to start with
1. If number of black cells in the given input is not perfect square then print "NO".
2. If black cell found at row index i and column index j , and suppose x is square root of number of black cells and size is size of grid then , If (size-i) < x or (size-j) < x print "NO"

Solution in C++ :

/* Author : Nitendra Bhosle
 * Date : 22/11/2013
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>

bool isPerfectSquare(int num)
{
int squareArray[] = { 1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400 };

for(int i = 0;i<20;++i)
{
if(num == squareArray[i])
return true;
}

return false;
}

std::string isSquare(const std::vector<std::string>& inputVec)
{
int numOfBalckCells = 0;
int size = inputVec.size();

for(int i=0;i<size;++i)
{
//std::cout<<"\n"<<inputVec[i];
for(int j=0;j<size;++j)
{
if(inputVec[i][j] == '#')
{
++numOfBalckCells;
}
}
}

//std::cout<<"\n numOfBalckCells "<<numOfBalckCells;
if(!isPerfectSquare(numOfBalckCells))
return "NO";

int squaRoot = (int)std::sqrt((double)numOfBalckCells);
//std::cout<<"\n squaRoot "<<squaRoot;
for(int i=0;i<size;++i)
{
for(int j=0;j<size;++j)
{
if(inputVec[i][j] == '#')
{
//std::cout<<"\n i : "<<i<<"\t j : "<<j<<"\t size : "<<size<<"\t squaRoot : "<<squaRoot;
if(((size-i) < squaRoot) || ((size-j) < squaRoot))
return "NO";

for(int l=0;l<squaRoot;++l)
{
for(int m=0;m<squaRoot;++m)
{
//std::cout<<"\n inputVec[i+l][j+m] : "<<inputVec[i+l][j+m];
if(inputVec[i+l][j+m] != '#')
return "NO";
}
}
//Everything Currect
return "YES";
}
}
}
return "YES";
}

int main(int argc, char **argv)
{
int T,N;
char inpArray[30];
std::vector<std::string> inputVec;

std::cin>>T;
for(int testCase=1;testCase<=T;testCase++)
{
std::cin>>N;
inputVec.clear();
for(int i=0;i<N;++i)
{
memset(inpArray,'/0',sizeof(inpArray));
fscanf(stdin,"%s",inpArray);
inputVec.push_back(inpArray);
}

std::cout<<"Case #"<<testCase<<":"<<isSquare(inputVec)<<std::endl;
}
return 0;
}