SRM 663 DIV1 Easy - ABBADiv1

SRM 663 DIV1 Easy - ABBADiv1

9:39

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13922&rd=16512

解き方


initialからtargetを生成するよう順に解いていき、部分列が存在しないようなら
打ち切ることで、候補数は限られるので時間内に解くことができる。
targetからinitialに戻せるか試しても良い。

コード


class ABBADiv1 {

public:

string rev(string str){
string ret="";
for(int i=str.size()-1;i>=0;i--)ret+=str[i];
return ret;
}

bool dfs(string cur,string target){
if(cur.size()>target.size())return false;
if(cur.size()==target.size()){
return cur==target;
}

bool valid=false;

string s1=cur+'A';
if(target.find(s1)!=string::npos || target.find(rev(s1))!=string::npos){
valid|=dfs(s1,target);
}
string s2=cur+'B';
if(target.find(s2)!=string::npos || target.find(rev(s2))!=string::npos){
valid|=dfs(rev(s2),target);
}

return valid;
}

string canObtain(string initial, string target) {
return dfs(initial,target) ? "Possible" : "Impossible";
}

};

Share this

Google Facebook Twitter More

Related Posts