#include #include #include int random(int n) { return rand() % n; } #define SIZE 100 int maze[SIZE][3]; int L[SIZE*3]; int R[SIZE*3]; bool end[SIZE*3]; #define UNDEFINED -1 void generate_maze(int n) { for (int i = 0; i < n; i++) { maze[i][0] = UNDEFINED; maze[i][1] = UNDEFINED; maze[i][2] = UNDEFINED; } // make first connection { maze[0][0] = 0; int k = random(n); if (k == 0) maze[0][1] = 1; else maze[1][0] = 1; } int l = 1; for (int empty_places = n * 3 - 2; empty_places > 0;) { // find a node with a free place int i1, j1; for (i1 = 0; i1 < n; i1++) if (maze[i1][0] != UNDEFINED && maze[i1][2] == UNDEFINED) break; if (maze[i1][1] == UNDEFINED) j1 = 1; else j1 = 2; maze[i1][j1] = 2*l; //printf("maze[%d][%d] = %d ", i1, j1, l); // find another node with int i2, j2; do { i2 = random(n); //printf(" i2 = %d ", i2); } while (maze[i2][2] != UNDEFINED); while (maze[i2][0] == UNDEFINED && maze[i2-1][0] == UNDEFINED) i2--; if (maze[i2][0] == UNDEFINED) j2 = 0; else if (maze[i2][1] == UNDEFINED) j2 = 1; else j2 = 2; maze[i2][j2] = 2*l + 1; //printf(" maze[%d][%d] = %d ", i2, j2, l); //printf("e = %d ", empty_places); if (empty_places == 2) break; bool can_go_next = false; for (int i = 0; i < n; i++) if (maze[i][0] != UNDEFINED && maze[i][2] == UNDEFINED) { can_go_next = true; break; } if (!can_go_next) { //printf(" go back\n"); maze[i1][j1] = UNDEFINED; maze[i2][j2] = UNDEFINED; } else { //printf(" okay\n"); empty_places -= 2; l++; } } for (int i = 1; i < n; i++) { if (random(2) == 1) { int h = maze[i][1]; maze[i][1] = maze[i][2]; maze[i][2] = h; } } } void print_maze(int n) { for (int i = 0; i < n; i++) printf("%2d %2d %2d\n", maze[i][0]/2, maze[i][1]/2, maze[i][2]/2); printf("\n"); } int reverse(int i) { return (i & ~1) | (~i & 1); } void fill_LR(int n) { for (int i = 0; i < n; i++) { int v0 = maze[i][0]; int v1 = maze[i][1]; int v2 = maze[i][2]; int w0 = reverse(v0); int w1 = reverse(v1); int w2 = reverse(v2); L[v0] = w1; L[v1] = w2; L[v2] = w0; R[v0] = w2; R[v1] = w0; R[v2] = w1; } for (int i = 0; i < n*3; i++) end[i] = false; end[maze[0][0]] = true; end[maze[0][1]] = true; end[maze[0][2]] = true; } void check_LR(int n) { for (int i = 0; i < n; i++) { if ( reverse(L[reverse(R[i])]) != i || reverse(R[reverse(L[i])]) != i || reverse(L[reverse(L[reverse(L[i])])]) != i || reverse(R[reverse(R[reverse(R[i])])]) != i) printf("error %d\n", i); } } void print_LR(int n) { for (int i = 0; i < n; i++) { printf("%2d: %2d %2d %s\n", i, L[i], R[i], end[i] ? "end" : ""); } printf("\n"); } int min[SIZE*3]; void print_LR_min(int n) { for (int i = 0; i < n; i++) { printf("%2d (%2d): %2d (%d) %2d (%d)\n", i, min[i], L[i], min[L[i]], R[i], min[R[i]]); } printf("\n"); } void calculate_min(int n) { for (int i = 0; i < n; i++) min[i] = end[i] ? 0 : n; for (bool modified = true; modified;) { print_LR_min(n); printf("--\n"); modified = false; for (int j = 0; j < n; j++) { int m = min[L[j]] + 1; if (m < min[j]) { min[j] = m; modified = true; } m = min[R[j]] + 1; if (m < min[j]) { min[j] = m; modified = true; } } } } void solve_straight(int n) { int pos[3*SIZE]; for (int i = 0; i < n; i++) pos[i] = i; for (;;) { // Count number at end position int at_end = 0; for (int i = 0; i < n; i++) if (end[pos[i]]) at_end++; if (at_end == n) break; // -- we are done // Evaluate left and right int min_L = n; int nr_at_min_L = 0; int left_L = 0; int min_R = n; int nr_at_min_R = 0; int left_R = 0; for (int i = 0; i < n; i++) if (!end[pos[i]]) { int m = min[L[pos[i]]]; if (m < min_L) { min_L = m; nr_at_min_L = 1; } else if (m == min_L) nr_at_min_L++; left_L += m; m = min[R[pos[i]]]; if (m < min_R) { min_R = m; nr_at_min_R = 1; } else if (m == min_R) nr_at_min_R++; left_R += m; } // make selection // if ( min_L < min_R // || (min_L == min_R && random(2) == 0)) // if ( min_L < min_R // || (min_L == min_R && left_L < left_R) // || (min_L == min_R && left_L == left_R && random(2) == 0)) if ( min_L < min_R || (min_L == min_R && nr_at_min_L > nr_at_min_R) || (min_L == min_R && nr_at_min_L == nr_at_min_R && random(2) == 0)) { printf("L"); for (int i = 0; i < n; i++) { if (!end[pos[i]]) pos[i] = L[pos[i]]; //printf(" %2d", pos[i]); } } else { printf("R"); for (int i = 0; i < n; i++) { if (!end[pos[i]]) pos[i] = R[pos[i]]; //printf(" %2d", pos[i]); } } //printf("\n"); } printf("\n"); } int main(int argc, char *argv[]) { srand(time(0)); int n = 100; generate_maze(n); print_maze(n); fill_LR(n); n = n * 3; check_LR(n); print_LR(n); calculate_min(n); print_LR_min(n); for (int x = 0; x < 50; x++) solve_straight(n); return 0; }