TopCoder SRM590 Div1 Easy 250 FoxAndChess

問題文

概要

'L', 'R', '.' からなる文字列 begintarget が与えられる. begin から,

という操作で target を作れるか.

制約

$ 1 \le n \le 50 $

解法

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 242.37 pts

string FoxAndChess::ableToMove( string start, string goal ){
    const int n = size(start);
    string s, g;
    rep(i, n){
        if(start[i] != '.') s += start[i];
        if(goal[i] != '.') g += goal[i];
    }
    if(s != g) return "Impossible";
    vector<int> rs1, rs2;
    vector<int> ls1, ls2;
    rep(i, n){
        if(start[i] == 'R') rs1.emplace_back(i);
        if(start[i] == 'L') ls1.emplace_back(i);
        if(goal[i] == 'R') rs2.emplace_back(i);
        if(goal[i] == 'L') ls2.emplace_back(i);
    }
    repsz(i, rs1) if(rs1[i] > rs2[i]) return "Impossible";
    repsz(i, ls1) if(ls1[i] < ls2[i]) return "Impossible";
    return "Possible";
}

Tags

TopCoder

Comments

comments powered by Disqus