C++实现超赞的解魔方的机器人代码

2015/05/18 42204

清华大佬耗费三个月吐血整理的几百G的资源，免费分享！....>>>

C++实现超赞的解魔方的机器人代码，这段代码精简实用，作者的脑子不知道是怎么长的，厉害。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
/**********************************************************************
 *
 * A cube 'state' is a vector<int> with 40 entries, the first 20
 * are a permutation of {0,...,19} and describe which cubie is at
 * a certain position (regarding the input ordering). The first
 * twelve are for edges, the last eight for corners.
 *
 * The last 20 entries are for the orientations, each describing
 * how often the cubie at a certain position has been turned
 * counterclockwise away from the correct orientation. Again the
 * first twelve are edges, the last eight are corners. The values
 * are 0 or 1 for edges and 0, 1 or 2 for corners.
 *
 * http://www.sharejs.com
 **********************************************************************/
  
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
  
//----------------------------------------------------------------------
  
typedef vector<int> vi;
  
//----------------------------------------------------------------------
  
int applicableMoves[] = { 0, 262143, 259263, 74943, 74898 };
  
// TODO: Encode as strings, e.g. for U use "ABCDABCD"
  
int affectedCubies[][8] = {
  {  0,  1,  2,  3,  0,  1,  2,  3 },   // U
  {  4,  7,  6,  5,  4,  5,  6,  7 },   // D
  {  0,  9,  4,  8,  0,  3,  5,  4 },   // F
  {  2, 10,  6, 11,  2,  1,  7,  6 },   // B
  {  3, 11,  7,  9,  3,  2,  6,  5 },   // L
  {  1,  8,  5, 10,  1,  0,  4,  7 },   // R
};
  
vi applyMove ( int move, vi state ) {
  int turns = move % 3 + 1;
  int face = move / 3;
  while( turns-- ){
    vi oldState = state;
    for( int i=0; i<8; i++ ){
      int isCorner = i > 3;
      int target = affectedCubies[face][i] + isCorner*12;
      int killer = affectedCubies[face][(i&3)==3 ? i-3 : i+1] + isCorner*12;;
      int orientationDelta = (i<4) ? (face>1 && face<4) : (face<2) ? 0 : 2 - (i&1);
      state[target] = oldState[killer];
      //state[target+20] = (oldState[killer+20] + orientationDelta) % (2 + isCorner);
      state[target+20] = oldState[killer+20] + orientationDelta;
      if( !turns )
    state[target+20] %= 2 + isCorner;
    }
  }
  return state;
}
  
int inverse ( int move ) {
  return move + 2 - 2 * (move % 3);
}
  
//----------------------------------------------------------------------
  
int phase;
  
//----------------------------------------------------------------------
  
vi id ( vi state ) {
    
  //--- Phase 1: Edge orientations.
  if( phase < 2 )
    return vi( state.begin() + 20, state.begin() + 32 );
    
  //-- Phase 2: Corner orientations, E slice edges.
  if( phase < 3 ){
    vi result( state.begin() + 31, state.begin() + 40 );
    for( int e=0; e<12; e++ )
      result[0] |= (state[e] / 8) << e;
    return result;
  }
    
  //--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
  if( phase < 4 ){
    vi result( 3 );
    for( int e=0; e<12; e++ )
      result[0] |= ((state[e] > 7) ? 2 : (state[e] & 1)) << (2*e);
    for( int c=0; c<8; c++ )
      result[1] |= ((state[c+12]-12) & 5) << (3*c);
    for( int i=12; i<20; i++ )
      for( int j=i+1; j<20; j++ )
    result[2] ^= state[i] > state[j];
    return result;
  }
    
  //--- Phase 4: The rest.
  return state;
}
  
//----------------------------------------------------------------------
  
int main ( int argc, char** argv ) {
    
  //--- Define the goal.
  string goal[] = { "UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
            "UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR" };
    
  //--- Prepare current (start) and goal state.
  vi currentState( 40 ), goalState( 40 );
  for( int i=0; i<20; i++ ){
      
    //--- Goal state.
    goalState[i] = i;
      
    //--- Current (start) state.
    string cubie = argv[i+1];
    while( (currentState[i] = find( goal, goal+20, cubie ) - goal) == 20){
      cubie = cubie.substr( 1 ) + cubie[0];
      currentState[i+20]++;
    }
  }
    
  //--- Dance the funky Thistlethwaite...
  while( ++phase < 5 ){
      
    //--- Compute ids for current and goal state, skip phase if equal.
    vi currentId = id( currentState ), goalId = id( goalState );
    if( currentId == goalId )
      continue;
      
    //--- Initialize the BFS queue.
    queue<vi> q;
    q.push( currentState );
    q.push( goalState );
      
    //--- Initialize the BFS tables.
    map<vi,vi> predecessor;
    map<vi,int> direction, lastMove;
    direction[ currentId ] = 1;
    direction[ goalId ] = 2;
      
    //--- Dance the funky bidirectional BFS...
    while( 1 ){
        
      //--- Get state from queue, compute its ID and get its direction.
      vi oldState = q.front();
      q.pop();
      vi oldId = id( oldState );
      int& oldDir = direction[oldId];
        
      //--- Apply all applicable moves to it and handle the new state.
      for( int move=0; move<18; move++ ){
    if( applicableMoves[phase] & (1 << move) ){
        
      //--- Apply the move.
      vi newState = applyMove( move, oldState );
      vi newId = id( newState );
      int& newDir = direction[newId];
        
      //--- Have we seen this state (id) from the other direction already?
      //--- I.e. have we found a connection?
      if( newDir  &&  newDir != oldDir ){
          
        //--- Make oldId represent the forwards and newId the backwards search state.
        if( oldDir > 1 ){
          swap( newId, oldId );
          move = inverse( move );
        }
          
        //--- Reconstruct the connecting algorithm.
        vi algorithm( 1, move );
        while( oldId != currentId ){
          algorithm.insert( algorithm.begin(), lastMove[ oldId ] );
          oldId = predecessor[ oldId ];
        }
        while( newId != goalId ){
          algorithm.push_back( inverse( lastMove[ newId ] ));
          newId = predecessor[ newId ];
        }
          
        //--- Print and apply the algorithm.
        for( int i=0; i<(int)algorithm.size(); i++ ){
          cout << "UDFBLR"[algorithm[i]/3] << algorithm[i]%3+1;
          currentState = applyMove( algorithm[i], currentState );
        }
          
        //--- Jump to the next phase.
        goto nextPhasePlease;
      }
        
      //--- If we've never seen this state (id) before, visit it.
      if( ! newDir ){
        q.push( newState );
        newDir = oldDir;
        lastMove[ newId ] = move;
        predecessor[ newId ] = oldId;
      }
    }
      }
    }
  nextPhasePlease:
    ;
  }
}