ポンゴネット英雄会第1回オンラインプログラミング大会:単語ゲーム

class Test {
public:
    typedef map<string, bool> Map;
    static int who (string   word)
    {
        // map     ，      
        //amap[s]     s          
        //bmap[s]     s          
        Map amap, bmap;
        return (int)dfs(word, 1, amap, bmap);
    }
private:
    //           
    static bool isIncrease(string &s)
    {
        int len = s.size();
        for(int i = 1; i < len; i++)
            if(s[i] <= s[i-1])return false;
        return true;
    }

    //id == 1         ，    
	//  true        ，  false    
    static bool dfs(string &s, bool id, Map &amap, Map &bmap)
    {
        if(isIncrease(s))
        {
            if(id == 0)
                return true;
            else return false;
        }
        int len = s.size();
        for(int i = 0; i < len; i++)
        {
            string subs = s;
            subs.erase(i,1);
            bool tmp;
            if(id == 0)
            {//     ，       true,         ，      
                if(bmap.find(subs) == bmap.end())
                {
                    tmp = dfs(subs, id^true, amap, bmap);
                    bmap[subs] = tmp;
                }
                else tmp = bmap[subs];
                if(tmp == false)return false;
            }
            else
            {//     ，        true，      
                if(amap.find(subs) == amap.end())
                {
                    tmp = dfs(subs, id^true, amap, bmap);
                    amap[subs] = tmp;
                }
                else tmp = amap[subs];
                if(tmp == true)return true;
            }
        }
        if(id == 0)
            return true;
        else return false;
    }
};