KRECT - Counting K-Rectangle
English | Vietnamese |
Given a M×N square board. Each square contains a letter of the English alphabet ('A' .. 'Z').
A K-rectangle of the board is a rectangle whose sides are parallel to the sides of the board, and contains exactly K different types of letter.
For example, with this 4×3 board:
CED CEB CBC DDA
The rectangle [(1,1), (2, 2)] is a 2-rectangle of the board because it contains 2 different letters: C and E.
Given M, N, K and the M×N board. Determine how many K-rectangles there are in the board.
Input
The first line contains 3 integers M, N and K. (1 ≤ M, N ≤ 100, 1 ≤ K ≤ 26)
The following M lines, each contains N letters of the English alphabet ('A' .. 'Z')
Output
Write one integer - the number of K-rectangles in the given board.
Example
Input: 4 3 3 CED CEB CBC DDA Output: 12
Added by: | Race with time |
Date: | 2009-05-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Based on problem CRECT - @vnoi |