Mock CCC '18 Contest 5 S5 - Carol's Cute Construction

View as PDF

Submit solution



Points: 20 (partial)
Time limit: 1.0s
Java 2.0s
Memory limit: 1G
Java 1G
Author:

Problem type

Carol wants to go to California!

Tudor recently gave Carol a game with similarities to Boggle. There is an N \times N grid of letters, all of which are either C, A, L, or I. In a single turn, Carol must select a C, an A, an L, and an I such that the C and A touch in at least one corner, as do the A and L as well as the L and I. Carol gains one point for doing so, but cannot select any of those letters in future turns.

Compute the maximum number of points Carol can earn.

Constraints

1 \le N \le 200

In tests worth 3 marks, you may assume N \le 4.

In tests worth an additional 5 marks, you may assume N \le 10.

Input Specification

The first line of the input contains a single integer, N.

The next N lines contain N characters, all of which appear in CALI.

Output Specification

Output, on a single line, the maximum number of points Carol can earn if she plays optimally.

Sample Input

4
CALI
ILAC
CLLC
IAAI

Sample Output

4

Comments

There are no comments at the moment.