/
SquareDetector.java
104 lines (86 loc) · 2.58 KB
/
SquareDetector.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package com.jlhuertas.fbhackercup.qualifying;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/**
* Problem: https://www.facebook.com/hackercup/problems.php?pid=318555664954399&round=598486203541358
* Suggested solution: https://www.facebook.com/notes/facebook-hacker-cup/2014-qualification-round-solutions/775180192497884
*
* @author jlhuertas
*
*/
public class SquareDetector {
private static final int FINDING_CORNER = 0;
private static final int CALCULATING_SIZE = 1;
private static final int CHECKING_SQUARE = 2;
public static void main(String[] args) throws FileNotFoundException {
Scanner inputFile = new Scanner(new FileInputStream(args[0]));
int T = inputFile.nextInt();
for (int testCase = 1; testCase <= T; testCase++) {
/*
* Three steps:
* 1) Finding the top-left corner
* 2) Finding the side of the square
* 3) Checking if everything inside the hypothetical bounds of the square is black and everything outside white.
*/
int N = inputFile.nextInt();
inputFile.nextLine();
int i = 0;
int j = 0;
String row = null;
int left = 0;
int top = 0;
boolean isSquare = true;
int status = FINDING_CORNER;
int squareSize = 0;
while (i < N) {
row = inputFile.nextLine();
j = 0;
while (j < N && isSquare) {
switch (status) {
case FINDING_CORNER:
if (row.charAt(j) == '#') {
left = j;
top = i;
squareSize = 1;
if (left == N - 1) {
status = CHECKING_SQUARE;
} else {
status = CALCULATING_SIZE;
}
}
break;
case CALCULATING_SIZE:
if (row.charAt(j) == '#') {
squareSize++;
} else {
status = CHECKING_SQUARE;
}
case CHECKING_SQUARE:
if (top + squareSize > N || left + squareSize > N) {
isSquare = false;
} else {
if (i >= top && i < top + squareSize && j >= left && j < left + squareSize ) {
//inside theorical square bounds
isSquare = (row.charAt(j)) == '#';
} else {
//outside theorical square bounds
isSquare = (row.charAt(j)) == '.';
}
}
break;
default:
break;
}
j++;
}
if (status == CALCULATING_SIZE) {
status = CHECKING_SQUARE;
}
i++;
}
String result = isSquare ? "YES" : "NO";
System.out.println("Case #" + testCase + ": " + result);
}
}
}