SRM525 slow

DropCoins.cpp

typedef vector<bitset<30> > Grid;
        
        template <>
        struct hash<Grid>
        {
            std::size_t operator()(const Grid& k) const
            {
                size_t ret;
                for(int i=0;i<k.size();++i)
                    for(int j=0;j<k[0].size();++j)
                        ret += 57*i*j+k[i][j];
                return ret%(k.size()*k[0].size() );
            }
        };

class DropCoins {
    public:
        int N, M, K;
        unordered_map<Grid, int> dp;
        const int MAX = 99999;
        enum{
            UP=0,
            DOWN,
            LEFT,
            RIGHT
        };
        int count(Grid g){
            int c=0;
            for(int row=0;row<g.size();++row){
                c+=g[row].count();
            }
            return c;
        }
        Grid turn(Grid orig, int direction){
            Grid ret(N);
            if(direction==UP){
                for(int i=1;i<N;++i)
                    ret[i-1]=orig[i]; 
            }
            else if(direction==DOWN){
                for(int i=0;i<N-1;++i)
                    ret[i+1]=orig[i];
            }
            if(direction==LEFT){
                for(int c=1;c<M;++c)
                    for(int r=0;r<N;++r)
                        ret[r][c-1]=orig[r][c]; 
            }
            else if(direction==RIGHT){
                for(int c=0;c<M-1;++c)
                    for(int r=0;r<N;++r)
                        ret[r][c+1]=orig[r][c];
            }
            return ret;
        }

        int bf(int level, Grid bd){

            if(dp.count(bd)>0){
                // cout<<"cache:"<<dp[bd]<<endl;
                // debug(bd, level);
                return dp[bd];//
            }
            if(count(bd)==K){
                return dp[bd]=level;
            } 
            if(level>=N+M-1||count(bd)<K) return MAX;
            
            int ans=MAX;
            for(int dir=0;dir<4;++dir){
                Grid yy = turn(bd, dir);
                int xx=bf(level+1, yy);
                ans=min(ans, xx);
            }
            return dp[bd]=ans;
        }

        int getMinimum(vector<string> board, int kk) {
            K=kk;
            N=board.size(), M=board[0].size();
            Grid bd(N);
            for(int i=0;i<N;++i){
                for(int j=0;j<M;++j){
                    if(board[i][j]=='o'){
                        bd[i][j]=1;
                    }
                    else{
                        bd[i][j]=0;
                    }
                }
            }
            int ret = bf(0, bd); 
            return ret==MAX?-1:ret;
        }

        void debug(Grid g, int l){
            cout<<"["<<count(g)<<"]->"<<l<<"\n";
            for(int i=0;i<N;++i){
                for(int j=0;j<M;++j)
                    cout<<g[i][j]<<" ";
                cout<<endl;
            }
            cout<<"-------------------------------"<<endl;
        }
};