it has 3 conditions that begin can't turn to target:
1 pawns' order is not the same
2 pawn R in target is shifted left to the position in begin
3 pawn L in target is shifted right to the position in begin
/* Topcoder SRM */
/*****************************************************************************/
vector<int> filt(string s) {
vector<int> r;
for (int i=0; i<sz(s); i++) {
if (s[i]!='.') {
r.pb(i);
}
}
return r;
}
string FoxAndChess::ableToMove(string begin, string target) {
vector<int> b=filt(begin), t=filt(target);
if (sz(b)!=sz(t)) {
return "Impossible";
}
for (int i=0; i<sz(b); i++) {
if (begin[b[i]]!=target[t[i]]||
begin[b[i]]=='R'&&t[i]<b[i]||
begin[b[i]]=='L'&&t[i]>b[i]) {
return "Impossible";
}
}
return "Possible";
}
/*****************************************************************************/
No comments :
Post a Comment