全体公開 > 合同練習会 > 20130323 > C センサー付きロボット

問題の概要

次の3つの命令を受け付けるロボットが居る.

• F: 前へ1単位進む.
• R: 右へ90度回転する.
• L: 左へ90度回転する.

但し, 壁があり, Fで壁に追突する場合は, 前に進む代わりに, 180度回転する.
壁はx, y軸のいずれかに平行に置かれ, 壁同士は接続され, 1つの多角形になっている.
壁, 初期位置, 命令が与えられるので, 最終位置と, ロボットの初期位置からの(ユークリッド)距離で最も離れた点を答えよ.
複数ある場合は, y座標の大きい方, それも複数あればx座標の大きい方.

実装の方針, 注意点

...

座標や向きを, 複素数で管理する.
今の向きから, 右を向くには , 左を向くには を掛ければよい.

出力の2つ目は, (初期位置からの距離の二乗, y座標, x座標) が辞書順で最も大きくなるような点.
距離そのままでも良いが, complex<int> では abs() は異なる動きをするので, 距離の二乗である norm() を用いる.

壁は, 壁である全ての点を set<P> に入れて管理した.
set<P> を使うため, 比較関数の実装が必要.
ついでに, 出力の2つ目を作るのが楽なように, (y座標, x座標) の辞書順で順序を入れた.
これにより, (初期位置からの距離の二乗, その点) が辞書順で大きいものを選べばよく, ''pair<int, P>'' で管理すると楽になる.

また, ''p(x1, y1)'' と ''q(x2, y2)'' を結ぶ壁は, x座標が区間 ''[min(x1, x2), max(x1, x2)]'', y座標が区間 ''[min(y1, y2), max(y1, y2)]'' に入る点全体である事に注意すると,
x軸に平行か, y軸に平行か, どちらが右/上にあるか等で場合分けせずに済む.

ソースコード

Not verified

...

typedef complex<int> P;
#define X real()
#define Y imag()
namespace std{
    bool operator<(const P &p1, const P &p2){
        return p1.Y == p2.Y ?  p1.X < p2.X : p1.Y < p2.Y;
    }
};
bool solve(){
    int n;
    cin >> n;
    if(!n) return false;
 
    // 壁の生成
    vector<P> wall_raw(n);
    rep(i, n) cin >> wall_raw[i].X >> wall_raw[i].Y;
    set<P> wall;
    rep(i, n){
        P crr = wall_raw[i];
        P nex = wall_raw[(i+1)%n];
        REP(x, min(crr.X, nex.X), max(crr.X, nex.X)+1)
            REP(y, min(crr.Y, nex.Y), max(crr.Y, nex.Y)+1)
                wall.insert(P(x, y));
    }
 
    P initial;
    cin >> initial.X >> initial.Y;
 
    P pos = initial;
    P dir = P(0, 1);
    pair<int, P> res(0, initial);
    string s;
    cin >> s;
    repsz(i, s){
        if(s[i] == 'F'){
            if(wall.count(pos + dir)){
                // 反転
                dir *= -1;
            }else{
                // 直進
                pos += dir;
            }
        }else if(s[i] == 'R'){
            // 右回転
            dir *= P(0, -1);
        }else if(s[i] == 'L'){
            // 左回転
            dir *= P(0, 1);
        }
        maxeq(res, make_pair(norm(pos - initial), pos));
    }
    cout << pos.X << " " << pos.Y << " ";
    cout << res.snd.X << " " << res.snd.Y << endl;
    return true;
}
 

編集

---