KRECT  Counting KRectangle
English  Vietnamese 
Given a M*N square board. Each square contains a letter of the English alphabet ('A' .. 'Z').
A Krectangle 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 2rectangle of the board because it contains 2 different letters: C and E.
Given M, N, K and the M*N board. Determine how many Krectangles 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 Krectangles in the given board.
Example
Input: 4 3 3 CED CEB CBC DDA Output: 12
hide comments
Jelle van den Hooff:
20091002 05:48:01
O((NM)^2) works great, but you have to keep the constant factor _low_. 

stjepan:
20091002 05:48:01
My solution is a O(n^2*m^2) algorithm and it is the fastest at the moment. Last edit: 20090603 19:22:36 

Robert Gerbicz:
20091002 05:48:01
I think no.


.:: Pratik ::.:
20091002 05:48:01
Just a hint.

Added by:  Race with time 
Date:  20090505 
Time limit:  0.343s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Based on problem CRECT  @vnoi 