#include #include #include #define BUFFER_SIZE 64 #define MAX_LOG 16*1024 #define FOLLOW_LENGTH 1 #define ROPE_LENGTH 10 void logTailPosition(int, int, int (**)[2]); void move(char, int*); void follow(int*, int*, int*); int main() { char buf[BUFFER_SIZE], *p, c; memset(buf, 0, BUFFER_SIZE); p = buf; int moveCount; // We will keep a log of the tail position just in case it is needed in the second part int tailLog[MAX_LOG][2]; memset(tailLog, 0, MAX_LOG * sizeof(int[2])); int (*tailLogHead)[2] = tailLog; // Relative to the start pos int ropePos[ROPE_LENGTH][2]; memset(ropePos, 0, ROPE_LENGTH * sizeof(int[2])); logTailPosition(0, 0, &tailLogHead); int diff[2]; while ((c = getchar()) != EOF) { *p++ = c; if (c == '\n') { sscanf(buf, "%c %i", &c, &moveCount); for (int i = 0; i < moveCount; i++) { move(c, ropePos[0]); for (int j = 0; j < ROPE_LENGTH - 2; j++) { follow(diff, ropePos[j], ropePos[j+1]); ropePos[j+1][0] += diff[0]; ropePos[j+1][1] += diff[1]; } follow(diff, ropePos[ROPE_LENGTH - 2], *(tailLogHead-1)); logTailPosition((*(tailLogHead-1))[0] + diff[0], (*(tailLogHead-1))[1] + diff[1], &tailLogHead); } memset(buf, 0, BUFFER_SIZE); p = buf; } } // Look at log and find unique places // Using a bintree would be better but its fine for now int uniques[MAX_LOG][2], uniquesLength = 0; for (int i = 1; i < (tailLogHead - tailLog); i++) { int found = 0; for (int j = 0; j < uniquesLength; j++) { if (uniques[j][0] == tailLog[i][0] && uniques[j][1] == tailLog[i][1]) { found = 1; break; } } if (!found) { uniques[uniquesLength][0] = tailLog[i][0]; uniques[uniquesLength][1] = tailLog[i][1]; uniquesLength++; } } printf("%i\n", uniquesLength); } void logTailPosition(int x, int y, int (**tailLogHead)[2]) { (**tailLogHead)[0] = x; (**tailLogHead)[1] = y; *tailLogHead += 1; } void move(char dir, int *pos) { switch (dir) { case 'U': pos[1]++; break; case 'D': pos[1]--; break; case 'R': pos[0]++; break; case 'L': pos[0]--; break; } } void follow(int* diff, int* head, int* tail) { diff[0] = 0; diff[1] = 0; if (head[0] - tail[0] > FOLLOW_LENGTH) { diff[0]++; if (head[1] > tail[1]) { diff[1]++; } else if (head[1] < tail[1]) { diff[1]--; } } else if (tail[0] - head[0] > FOLLOW_LENGTH) { diff[0]--; if (head[1] > tail[1]) { diff[1]++; } else if (head[1] < tail[1]) { diff[1]--; } } else if (head[1] - tail[1] > FOLLOW_LENGTH) { diff[1]++; if (head[0] > tail[0]) { diff[0]++; } else if (head[0] < tail[0]) { diff[0]--; } } else if (tail[1] - head[1] > FOLLOW_LENGTH) { diff[1]--; if (head[0] > tail[0]) { diff[0]++; } else if (head[0] < tail[0]) { diff[0]--; } } }