I tried solving this problem in Java and believe I know how it works, and I get right answers for all the test cases, but WA when I submit. Could anyone help me figure out why?
The problem says the elegance is only determined by the number of squares, should we count rectangles too?
Full solution: http://www.codechef.com/viewsolution/4371438
Method to count elegance:
public static int computeElegance(String[] garden){
int squares = 0;
int rows = garden.length;
int columns = garden[0].length();
for(int i = 0; i < rows-1; i += 1){ //for each row in garden
for(int j = 0; j < columns-1; j +=1){ //for each column in garden
char tLeftChar = garden[i].charAt(j); //char at topLeftCorner
for(int tRight = j+1; tRight < columns; tRight +=1){ //for each cell to right
for(int bLeft = i+1; bLeft < rows; bLeft += 1){ //for each cell below
if(garden[i].charAt(tRight) == tLeftChar) //topRight
if(garden[bLeft].charAt(j) == tLeftChar) //bottomLeft
if(garden[bLeft].charAt(tRight) == tLeftChar) //bottomRight
squares += 1;
}
}
}
}
return squares;
}//end computeElegance()
I check every possible square in the garden in an order like this:
EDIT: [Solved]
My issue was that it was counting rectangles in certain cases. Correct solution for anyone interested: http://www.codechef.com/viewsolution/4371630