KRECT - Counting K-Rectangle
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.
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')
Write one integer - the number of K-rectangles in the given board.
Input: 4 3 3 CED CEB CBC DDA Output: 12
Jelle van den Hooff:
O((NM)^2) works great, but you have to keep the constant factor _low_.
My solution is a O(n^2*m^2) algorithm and it is the fastest at the moment.Last edit: 2009-06-03 19:22:36
I think no.
.:: Pratik ::.:
Just a hint.