제 알고리즘은 주어진 직사각형 내부의 모든 가능한 직사각형을 순회합니다. 각각의 내부의 직사각형에 대해서 좌표를 차례대로 순회하면서 각 칸에 대한 해시값을 (i+j)*k (i,j 는 x,y 좌표이고, k는 순회 중 k 번째로 나타난 색깔을 의미) 로 부여하고 모두 더해서 직사각형의 해시값을 계산했습니다. 그리고 겹치지 않는 해시값의 수를 카운트하였습니다.
해시의 크기나 해시함수가 정당한지 여부는 차치하고 TLE가 뜨네요.
어떻게 시간을 줄일 수 있을까요?
아래는 코드입니다.
#include <vector>#include <iostream>#include <set>#include <algorithm>#include <cassert>#include <memory.h>usingnamespacestd;inthashSize;voidsolve();char**tile;boolhashTable[52*52+1];intans;voidfillHash(intx,inty,intW,intH){unsignedinthash=0;vector<int>number;for(inti=0;i<W;i++)for(intj=0;j<H;j++){inttemp=i+j;intk;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++;}}intmain(){intT;cin>>T;while(T--)solve();return0;}voidsolve(){intW,H;cin>>H>>W;tile=newchar*[W];for(inti=0;i<W;i++)tile[i]=newchar[H];stringtemp;for(inti=0;i<H;i++){cin>>temp;assert(temp.size()==W);for(intj=0;j<W;j++)tile[j][i]=temp[j];//tile[i][j] = temp[j] causes no error on given input}ans=0;for(intx=1;x<=W;x++)// x length{for(inty=1;y<=H;y++)// y length{hashSize=100;// hashSize = (x+1)*(y+1);if(x==W&&y==H)continue;memset(hashTable,0,hashSize);for(inta=0;a<=W-x;a++)// x startfor(intb=0;b<=H-y;b++)// y startfillHash(a,b,x,y);}}cout<<ans<<endl;for(inti=0;i<W;i++)free(tile[i]);free(tile);}
sven
NUINJABMK
제 알고리즘은 주어진 직사각형 내부의 모든 가능한 직사각형을 순회합니다. 각각의 내부의 직사각형에 대해서 좌표를 차례대로 순회하면서 각 칸에 대한 해시값을 (i+j)*k (i,j 는 x,y 좌표이고, k는 순회 중 k 번째로 나타난 색깔을 의미) 로 부여하고 모두 더해서 직사각형의 해시값을 계산했습니다. 그리고 겹치지 않는 해시값의 수를 카운트하였습니다.
해시의 크기나 해시함수가 정당한지 여부는 차치하고 TLE가 뜨네요.
어떻게 시간을 줄일 수 있을까요?
아래는 코드입니다.
11년 전