make_graph.cpp (2364B)
1 #include<cstdio> 2 #include<cassert> 3 #include<unordered_map> 4 #include<vector> 5 6 // load trace produced by bruteforce.cpp and produce a graph including only 7 // reachable configurations (and renumbering configurations to contiguous 8 // ids) 9 10 using namespace std; 11 12 typedef unsigned long long ull; 13 14 vector<ull> n[7]; // the next configuration for each piece in this id 15 vector<int> rot[7]; // the rotation with which to play each piece in this id 16 vector<int> distwin[7]; // the distance to win for each piece in this id 17 vector<int> col[7]; // the column where to play each piece in this id 18 vector<bool> fin; // is id in a won state? 19 vector<bool> seen; // have we seen the id? 20 unordered_map<ull, int> M; // mapping of configurations to contiguous ids 21 22 ull dafind(ull v) { 23 // find config v in M 24 if (M.find(v) == M.end()) { 25 // it does not exist, add it with empty values 26 M[v] = M.size(); 27 for (int i = 0 ; i <7; i++) 28 n[i].push_back(0); 29 for (int i = 0 ; i <7; i++) 30 rot[i].push_back(-1); 31 for (int i = 0 ; i <7; i++) 32 col[i].push_back(-1); 33 for (int i = 0 ; i <7; i++) 34 distwin[i].push_back(-1); 35 fin.push_back(true); 36 seen.push_back(false); 37 return M.size()-1; 38 } 39 return M[v]; 40 } 41 42 void explore(int v) { 43 // dfs exploration to find reachable configurations from v 44 if (fin[v]) 45 return; // leaf 46 if (seen[v]) 47 return; // already seen 48 seen[v] = true; 49 for (int i = 0; i < 7; i++) 50 explore(n[i][v]); 51 } 52 53 int main() { 54 while (true) { 55 ull f, t; 56 int a, rr, cc, dw; 57 58 int ret = scanf("%lld %d %d %d %d %lld", &f, &a, &dw, &rr, &cc, &t); 59 if (ret != 6) 60 break; 61 // get ids of configs 62 ull ff = dafind(f); 63 ull tt = dafind(t); 64 fin[ff] = false; 65 66 // if already known to be winning with a worse score, ignore 67 if (distwin[a][ff] >= 0 && distwin[a][ff] <= dw) 68 continue; 69 70 // store info 71 distwin[a][ff] = dw; 72 n[a][ff] = tt; 73 rot[a][ff] = rr; 74 col[a][ff] = cc; 75 } 76 77 // explore from the first config 78 explore(M[0]); 79 80 // produce the graph: 81 // field 1: the id 82 // field 2: the piece 83 // fields 3 and 4: the rotation and column 84 // field 5: the resulting id 85 for (ull i = 0; i < seen.size(); i++) 86 if (seen[i] && !fin[i]) 87 for (int j = 0; j < 7; j++) 88 printf("%lld %d %d %d %lld\n", i, j, rot[j][i], col[j][i], n[j][i]); 89 return 0; 90 91 92 }