DMPG '16 G2 - Kabane Apocalypse

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.4s
Memory limit: 256M

Author:
Problem types

The world is in turmoil, undead zombies are roaming the Earth, and there's no time for a fancy legend. You are in charge of planning where to develop a human stronghold to fight back against the zombies.

You know there are 5 essential things humanity needs to establish a stronghold: food, water, ammunition, building supplies, and a power source. For simplicity, we will assign a letter from A to E to represent each of these essentials, in that order. Since it's well known that the world is square and flat, you can view it as a 2 dimensional grid of N rows of N cells each. Each cell may be empty, or it may contain one of the essentials for a stronghold.

The human stronghold should be located in an axis-aligned sub-grid of the original grid that contains at least one of each of the five essentials. How many ways can you choose a sub-grid such that all of the five essentials appear at least once in it?

Input Specification

The first line of input will contain N.
The next N lines of input will contain N characters each, each one either an uppercase letter from A to E or a period (.). Letters represent that the cell contains one of the five essentials that is represented by the letter, and a period represents that none of the five essentials is present in that cell.

Output Specification

Output the number of ways to choose a sub-grid for the human stronghold.

Constraints

For all subtasks:

1 \le N \le 1\,000

Subtask 1 [15%]

1 \le N \le 20

Subtask 2 [15%]

Each of the five essentials will appear only once in the grid.

Subtask 3 [70%]

No additional constraints.

Sample Input

4
.A.E
..D.
.CB.
E..A

Sample Output

6

Comments

There are no comments at the moment.