NUINJABMK 질문드립니다.

  • sven
    sven

    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);
    }
    

    11년 전
1개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    일단 떠오르는건 모든 n^4조합에 대해 fillHash를 독립적으로
    돌리지마시고 한 줄 늘어날때마다 이전에 채운 Hash를 이용하시면
    시간복잡도를 한 차원 줄이실수 있을듯하네여


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.