問題
http://community.topcoder.com/stat?c=problem_statement&pm=12725&rd=15702
解き方
左にある要素から順に、
①アルファベットが一致するか
②Lならばbeginの方が右側にあるか
③Rならばbeginの方が左側にあるか
を調べていき、すべて満たすかどうかを判定すれば良い。
コード
class FoxAndChess {
public: string ableToMove(string begin, string target) {
int n=begin.size();
while(1){
int finish=1;
FORE(i,0,n)if(begin[i]!='.' || target[i]!='.')finish=0;
if(finish)break;
int idx1=-1,idx2=-1;
char ch1='*',ch2='*';
FORE(i,0,n)if(begin[i]!='.'){
ch1=begin[i],idx1=i;
break;
}
FORE(i,0,n)if(target[i]!='.'){
ch2=target[i],idx2=i;
break;
}
if(ch1!=ch2)return "Impossible";
if(ch1=='L' && idx1<idx2)return "Impossible";
if(ch1=='R' && idx1>idx2)return "Impossible";
begin[idx1]='.',target[idx2]='.';
}
return "Possible";
}
};
public: string ableToMove(string begin, string target) {
int n=begin.size();
while(1){
int finish=1;
FORE(i,0,n)if(begin[i]!='.' || target[i]!='.')finish=0;
if(finish)break;
int idx1=-1,idx2=-1;
char ch1='*',ch2='*';
FORE(i,0,n)if(begin[i]!='.'){
ch1=begin[i],idx1=i;
break;
}
FORE(i,0,n)if(target[i]!='.'){
ch2=target[i],idx2=i;
break;
}
if(ch1!=ch2)return "Impossible";
if(ch1=='L' && idx1<idx2)return "Impossible";
if(ch1=='R' && idx1>idx2)return "Impossible";
begin[idx1]='.',target[idx2]='.';
}
return "Possible";
}
};