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; }