Facebook Hacker Cup 2014 Square Detector Solution

by
Square Detector
Square Detector      20 points
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

Solution


<?php

// get and import the input file
if(isset($_GET['file'])) { $file = $_GET['file']; } else { $file="input.txt"; }
$input = file("C:\\Users\\NEO\\Downloads\\".$file);
$test_cases = reset($input);
$output = '';

//Skip key 0 as it is the number of test cases!, start looping from 1
for ($case_number = 1, $i=1; $i<count($input); $i++) {

//get number of graphic lines
$canvas_size = $input[$i];
//slice out the graphic lines without preserving keys
$graphical_data = array_slice($input, $i+1, $canvas_size, FALSE);

$s = is_square($graphical_data, $canvas_size);

$output.= "Case #{$case_number}: ".is_square($graphical_data, $canvas_size).PHP_EOL;

$i+= $canvas_size;//skip to the begining of the next case
$case_number++;
}

// Save results to output file
file_put_contents('output.txt', $output);
echo "DONE!";
// Mark Clear Rows With 0s
function removeClearRow($graphical_data, $n, &$clear_rows) {
if(strpos($graphical_data[$n],'#') === false) {
$graphical_data[$n] = str_replace('.', '0', $graphical_data[$n]);
$clear_rows ++;
}
return $graphical_data;
}

// Mark Clear Columns with 0s
function removeClearColumn($graphical_data, $n, &$clear_columns) {
$draft = $graphical_data;
foreach($graphical_data as $r => $row) {
if($row[$n] == '#') { return $graphical_data; }
$draft[$r][$n] = '0';
}
$clear_columns++;
return $draft;
}

// Determin where the graphical data creates a single square
function is_square($graphical_data, $canvas_size) {

// Every test case contains at least one black cell, so we don't need to worry about checking that
//if (strpos(implode('', $graphical_data), '#') === false) {return 'NO'; }

$clear_rows = 0;
$clear_columns = 0;

for($i=0; $i<$canvas_size; $i++) {
$graphical_data = removeClearColumn($graphical_data, $i, $clear_rows);
$graphical_data = removeClearRow($graphical_data, $i, $clear_columns);
}

// same amount of clear rows and columns is necessary
if($clear_rows !== $clear_columns) {
return 'NO';
}

// are there any holes in the square that was not marked with 0
if (strpos( implode( '', $graphical_data) , '.') !== false) {
return 'NO';
}

//It must be a square
return 'YES';
}

 

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.

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