mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 039 C - 幼稚園児高橋君

ARCに参加しました。結果はABだけ解いて(◞‸◟)でした。

解法

解説(AtCoder Regular Contest 039 解説)の通り実装したつもりです。
毎回自分の位置を更新するたびに4方向の近傍が次にどこに向かうのかを更新していきます。

const int MAXK = 200200;

set<pii> visit;
map<pii, pii> neig[4];

pii dfs(const pii& p, const int dir) {
    if (visit.count(p) == 0) return p;
    if (neig[dir].count(p) != 0) {
        return neig[dir][p] = dfs(neig[dir][p], dir);
    } else {
        return neig[dir][p] = dfs(pii(p.first+dx[dir], p.second+dy[dir]), dir);
    }
}

int parse(char c) {
    if (c == 'R') return 0;
    if (c == 'U') return 1;
    if (c == 'L') return 2;
    if (c == 'D') return 3;
    return 0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    string str;
    cin >> str;
    pii now(0, 0);
    for (int i = 0; i < K; i++) {
        visit.insert(now);
        for (int k = 0; k < 4; k++) {
            pii np = dfs(now, k);
            int tmp = (k+2)%4;
            dfs(np, tmp);
        }
        int dir = parse(str[i]);
        now = dfs(now, dir);
    }
    cout << now.first << " " << now.second << endl;
    return 0;
}