Created
February 23, 2012 09:36
-
-
Save kghost/1891936 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string.h> | |
#include <stdio.h> | |
#include <queue> | |
#define LOWER 0 | |
#define UPPER 10000 | |
#define S_MID_TOP_TO_LEFT 0 | |
#define S_MID_BOTTOM_TO_LEFT 1 | |
#define S_LEFT_TOP_TO_MID 2 | |
#define S_LEFT_BOTTOM_TO_MID 3 | |
#define S_RIGHT_TOP_TO_MID 4 | |
#define S_RIGHT_BOTTOM_TO_MID 5 | |
#define S_MID_TOP_TO_RIGHT 6 | |
#define S_MID_BOTTOM_TO_RIGHT 7 | |
std::pair<bool,int> path_1 (int i) { return std::make_pair(i+7 > LOWER && i+7 < UPPER, i + 7); } | |
std::pair<bool,int> path_2 (int i) { return std::make_pair(i/2 > LOWER && i/2 < UPPER && i%2 == 0, i/2); } | |
std::pair<bool,int> path_3 (int i) { return std::make_pair(i*3 > LOWER && i*3 < UPPER, i*3); } | |
std::pair<bool,int> path_4 (int i) { return std::make_pair(i-5 > LOWER && i-5 < UPPER, i-5); } | |
typedef std::pair<bool,int> (*path) (int i); | |
path routes[8] = { path_1, path_2, path_1, path_2, path_3, path_4, path_3, path_4 }; | |
char (*dp)[8]; | |
std::queue<std::pair<int, int> > search; | |
bool check_path(int i, int step, int route) { | |
std::pair<bool,int> t = routes[route](i); | |
if (t.first && dp[t.second][route] == 0) { | |
dp[t.second][route] = step; | |
search.push(std::make_pair(t.second, route)); | |
return t.second == 2012; | |
} | |
return false; | |
} | |
void reverse(int step, int route); | |
int main () { | |
dp = new char[UPPER-LOWER][8]; | |
memset(dp, (UPPER-LOWER)*8, 0); | |
dp = &dp[LOWER]; | |
search.push(std::make_pair(2018, S_LEFT_TOP_TO_MID)); | |
dp[2018][S_LEFT_TOP_TO_MID] = 1; | |
while (!search.empty()) { | |
std::pair<int, int> p = search.front(); | |
search.pop(); | |
char step = dp[p.first][p.second] + 1; | |
//printf ("step %d, year %d, route %d\n", step, p.first, p.second); | |
switch (p.second) { | |
case S_MID_TOP_TO_LEFT: | |
check_path(p.first, step, S_LEFT_BOTTOM_TO_MID); | |
break; | |
case S_MID_BOTTOM_TO_LEFT: | |
check_path(p.first, step, S_LEFT_TOP_TO_MID); | |
break; | |
case S_LEFT_TOP_TO_MID: | |
check_path(p.first, step, S_MID_BOTTOM_TO_LEFT); | |
if (check_path(p.first, step, S_MID_TOP_TO_RIGHT)) | |
reverse(step, S_MID_TOP_TO_RIGHT); | |
if (check_path(p.first, step, S_MID_BOTTOM_TO_RIGHT)) | |
reverse(step, S_MID_BOTTOM_TO_RIGHT); | |
break; | |
case S_LEFT_BOTTOM_TO_MID: | |
check_path(p.first, step, S_MID_TOP_TO_LEFT); | |
if (check_path(p.first, step, S_MID_TOP_TO_RIGHT)) | |
reverse(step, S_MID_TOP_TO_RIGHT); | |
if (check_path(p.first, step, S_MID_BOTTOM_TO_RIGHT)) | |
reverse(step, S_MID_BOTTOM_TO_RIGHT); | |
break; | |
case S_RIGHT_TOP_TO_MID: | |
check_path(p.first, step, S_MID_TOP_TO_LEFT); | |
check_path(p.first, step, S_MID_BOTTOM_TO_LEFT); | |
if (check_path(p.first, step, S_MID_BOTTOM_TO_RIGHT)) | |
reverse(step, S_MID_BOTTOM_TO_RIGHT); | |
break; | |
case S_RIGHT_BOTTOM_TO_MID: | |
check_path(p.first, step, S_MID_TOP_TO_LEFT); | |
check_path(p.first, step, S_MID_BOTTOM_TO_LEFT); | |
if (check_path(p.first, step, S_MID_TOP_TO_RIGHT)) | |
reverse(step, S_MID_TOP_TO_RIGHT); | |
break; | |
case S_MID_TOP_TO_RIGHT: | |
check_path(p.first, step, S_RIGHT_BOTTOM_TO_MID); | |
break; | |
case S_MID_BOTTOM_TO_RIGHT: | |
check_path(p.first, step, S_RIGHT_TOP_TO_MID); | |
break; | |
} | |
} | |
} | |
int reverse_path_1 (int i) { return i-7; } | |
int reverse_path_2 (int i) { return i*2; } | |
int reverse_path_3 (int i) { return i/3; } | |
int reverse_path_4 (int i) { return i+5; } | |
typedef int (*reverse_path) (int i); | |
reverse_path reverse_routes[8] = { reverse_path_1, reverse_path_2, reverse_path_1, reverse_path_2, reverse_path_3, reverse_path_4, reverse_path_3, reverse_path_4 }; | |
#define reverse_check_path(year, step, previous_route) \ | |
{ \ | |
if (dp[year][previous_route] == step) { \ | |
route = previous_route; \ | |
continue; \ | |
} \ | |
} | |
const char* route_text(int route) { | |
switch (route) { | |
case 0: | |
return "+7"; | |
case 1: | |
return "/2"; | |
case 2: | |
return "+7"; | |
case 3: | |
return "/2"; | |
case 4: | |
return "*3"; | |
case 5: | |
return "-5"; | |
case 6: | |
return "*3"; | |
case 7: | |
return "-5"; | |
} | |
} | |
// back trace to find path O(step) | |
void reverse(int step, int route) { | |
printf("Total step: %d, path below (reversed):\n", step); | |
int year = 2012; | |
for (step -= 1; step >= 0; step -= 1) { | |
printf ("step %d, year %d (%s)\n", step+1, year, route_text(route)); | |
year = reverse_routes[route](year); | |
switch (route) { | |
case S_LEFT_BOTTOM_TO_MID: | |
reverse_check_path(year, step, S_MID_TOP_TO_LEFT); | |
break; | |
case S_LEFT_TOP_TO_MID: | |
reverse_check_path(year, step, S_MID_BOTTOM_TO_LEFT); | |
break; | |
case S_MID_TOP_TO_LEFT: | |
reverse_check_path(year, step, S_LEFT_BOTTOM_TO_MID); | |
reverse_check_path(year, step, S_RIGHT_TOP_TO_MID); | |
reverse_check_path(year, step, S_RIGHT_BOTTOM_TO_MID); | |
break; | |
case S_MID_TOP_TO_RIGHT: | |
reverse_check_path(year, step, S_LEFT_TOP_TO_MID); | |
reverse_check_path(year, step, S_LEFT_BOTTOM_TO_MID); | |
reverse_check_path(year, step, S_RIGHT_BOTTOM_TO_MID); | |
break; | |
case S_MID_BOTTOM_TO_LEFT: | |
reverse_check_path(year, step, S_LEFT_TOP_TO_MID); | |
reverse_check_path(year, step, S_RIGHT_TOP_TO_MID); | |
reverse_check_path(year, step, S_RIGHT_BOTTOM_TO_MID); | |
break; | |
case S_MID_BOTTOM_TO_RIGHT: | |
reverse_check_path(year, step, S_LEFT_TOP_TO_MID); | |
reverse_check_path(year, step, S_LEFT_BOTTOM_TO_MID); | |
reverse_check_path(year, step, S_RIGHT_TOP_TO_MID); | |
break; | |
case S_RIGHT_BOTTOM_TO_MID: | |
reverse_check_path(year, step, S_MID_TOP_TO_RIGHT); | |
break; | |
case S_RIGHT_TOP_TO_MID: | |
reverse_check_path(year, step, S_MID_BOTTOM_TO_RIGHT); | |
break; | |
} | |
throw "ERROR"; | |
} | |
printf ("step %d, year %d\n", 0, 2011); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Worship