#include #include #include //#define ANIMATE #ifdef ANIMATE #include #endif using namespace std; enum Dir { UP, DOWN, RIGHT, LEFT }; struct Instr { enum Dir dir; unsigned steps; }; struct Pos2d { int x, y; Pos2d operator+(const Pos2d &r) const { return {this->x + r.x, this->y + r.y}; } void operator+=(const Pos2d &r) { *this = *this + r; } Pos2d operator-(const Pos2d &r) const { return {this->x - r.x, this->y - r.y}; } bool operator==(const Pos2d &r) const { return this->x == r.x && this->y == r.y; } }; Pos2d dirs[] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; typedef vector Input; template<> struct std::hash { size_t operator()(const Pos2d &r) const { return hash{}(r.x) ^ (hash{}(r.y) << 1); } }; Input parse() { Input data; for (string line; getline(cin, line);) { Instr instr; if (line.size() < 3 || line.at(1) != ' ') throw "parse"; switch (line.at(0)) { case 'U': instr.dir = UP; break; case 'D': instr.dir = DOWN; break; case 'L': instr.dir = LEFT; break; case 'R': instr.dir = RIGHT; break; } instr.steps = stoi(line.substr(2)); data.push_back(instr); } return data; } #ifdef ANIMATE bool animate; int min_x, max_x, min_y, max_y; unsigned frame; void output_img(const vector &knot, const unordered_set &visited) { enum Grid { NONE, VISITED, TAIL, HEAD }; unsigned width = max_x + 1 - min_x; unsigned height = max_y + 1 - min_y; auto map = vector(width * height); for (auto i : visited) map[(i.y - min_y) * width + (i.x - min_x)] = VISITED; for (auto i : knot) map[(i.y - min_y) * width + (i.x - min_x)] = TAIL; map[(knot.front().y - min_y) * width + (knot.front().x - min_x)] = HEAD; char fname[] = "img/00000.pam"; sprintf(fname, "img/%05d.pam", frame++); auto file = ofstream(fname); file << "P7\n"; file << "WIDTH " << width << "\n"; file << "HEIGHT " << height << "\n"; file << "DEPTH 3\n"; file << "MAXVAL 255\n"; file << "TUPLTYPE RGB\n"; file << "ENDHDR\n"; for (auto i : map) { uint32_t color = 0; switch (i) { case NONE: color = 0x000000; break; case VISITED: color = 0xFF0000; break; case TAIL: color = 0x00FF00; break; case HEAD: color = 0x0000FF; break; } file.write((char *)&color, 3); } file.close(); } #endif unsigned p1(const Input &input, unsigned count = 2) { auto knot = vector(count); unordered_set visited; visited.insert(knot.back()); for (auto x : input) { for (unsigned i = 0; i < x.steps; i++) { knot.front() += dirs[x.dir]; for (auto el = knot.begin(); el < knot.end() - 1; el++) { Pos2d dist = el[0] - el[1]; if (abs(dist.x) >= 2 || abs(dist.y) >= 2) { if (abs(dist.x) >= 2) dist.x = dist.x > 0 ? 1 : -1; if (abs(dist.y) >= 2) dist.y = dist.y > 0 ? 1 : -1; el[1] += dist; continue; } break; } visited.insert(knot.back()); #ifdef ANIMATE if (!animate) { for (auto cur : knot) { if (cur.x < min_x) min_x = cur.x; if (cur.x > max_x) max_x = cur.x; if (cur.y < min_y) min_y = cur.y; if (cur.y > max_y) max_y = cur.y; } } else { output_img(knot, visited); } #endif } } return visited.size(); } unsigned p2(const Input &input) { return p1(input, 10); } int main() { auto input = parse(); #ifdef ANIMATE animate = false; p1(input, 10); animate = true; p1(input, 10); return 0; #endif cout << p1(input) << endl; cout << p2(input) << endl; }