[[problem:NUINJABMK]]

제 알고리즘은 주어진 직사각형 내부의 모든 가능한 직사각형을 순회합니다. 각각의 내부의 직사각형에 대해서 좌표를 차례대로 순회하면서 각 칸에 대한 해시값을 (i+j)*k (i,j 는 x,y 좌표이고, k는 순회 중 k 번째로 나타난 색깔을 의미) 로 부여하고 모두 더해서 직사각형의 해시값을 계산했습니다. 그리고 겹치지 않는 해시값의 수를 카운트하였습니다.
해시의 크기나 해시함수가 정당한지 여부는 차치하고 TLE가 뜨네요.
어떻게 시간을 줄일 수 있을까요?
아래는 코드입니다.

#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <cassert>
#include <memory.h>

using namespace std;

int hashSize;
void solve();
char **tile;
bool hashTable[52*52+1];
int ans;

void fillHash(int x, int y, int W, int H)
{
    unsigned int hash = 0;
    vector <int> number;
    for(int i=0; i<W; i++)
        for(int j=0; j<H; j++)
        {
            int temp = i+j;
            int k;
            for(k=0; k<number.size(); k++)
                if(number[k] == tile[x+i][y+j])
                {
                    hash += temp*k;
                    break;
                }
            if(k == number.size())
            {
                number.push_back(tile[x+i][y+j]);
                hash += temp*k;
            }
        }
    if(!hashTable[hash%hashSize])
    {
        hashTable[hash%hashSize] = true;
        ans++;
    }
}

int main()
{
    int T;
    cin >> T;
    while(T--)
        solve();
    return 0;
}

void solve()
{
    int W, H;
    cin >> H >> W;
    tile = new char * [W];
    for(int i=0; i<W; i++)
        tile[i] = new char[H];
    string temp;
    for(int i=0; i<H; i++)
    {
        cin >> temp;
        assert(temp.size() == W);
        for(int j=0; j<W; j++)
            tile[j][i] = temp[j]; //tile[i][j] = temp[j] causes no error on given input
    }
    
    ans = 0;
    for(int x=1; x<=W; x++) // x length
    {
        for(int y=1; y<=H; y++) // y length
        {
            hashSize = 100;
//            hashSize = (x+1)*(y+1);
            if(x == W && y == H) continue;
            memset(hashTable,0,hashSize);
            for(int a=0; a<=W-x; a++) // x start
                for(int b=0; b<=H-y; b++) // y start
                    fillHash(a,b,x,y);
        }
    }
    cout << ans << endl;
    for(int i=0; i<W; i++)
        free(tile[i]);
    free(tile);
}