Topcoder SRM 590 DIV1 EASY

if the number of pawns of begin and target are not equal, return with impossible
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