大意是用N个灯，有4种操作，然后有些限制条件，操作C次后，可能出现的灯的状态。
刚开始直接用N个灯来BFS，对状态数的数目不太了解，而且还不是一层一层的扩展，还跨过层，也就是说状态数就变成C*(<2^N)了，而且还没判重，弄晕掉。
后来，仔细观察状态，发现对于N个灯泡，4种操作时有循环节的，为6，就是说状态数只有2^6，然后用BFS一层一层扩展，扩展到C层，复杂度就是2^6 * C，BFS的过程其实可以看成从X层到X+1层的扩展，然后用个S[1 << 6][2]标记数组来标记X,X+1层的状态，进行判重。在这过程中都不对状态数进行状态限制，直到扩展到C层时，判断限制条件，符合就放进ANS。注意2进制的字典序和高地位顺序问题。
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < map > 8 #include < time.h > 9 #include < queue > 10 #include < set > 11 using namespace std; 12 13 int N, C, SN; 14 15 int s[ 1 << 6 ][ 2 ]; 16 int on, off; 17 18 vector < int > ans; 19 20 bool check( int t) 21 { 22 if (((t & on) != on)) return false ; 23 if (t & off) return false ; 24 return true ; 25 } 26 27 string turn( int x, int len) 28 { 29 string res = "" ; 30 for ( int i = 0 ; i < len; i ++ ) 31 { 32 if (x & ( 1 << i)) res.push_back( ' 1 ' ); 33 else res.push_back( ' 0 ' ); 34 } 35 return res; 36 } 37 38 void go() 39 { 40 // SN = (N - 1) % 6 + 1; 41 if (N > 6 ) SN = 6 ; 42 else SN = N; 43 memset(s, 0 , sizeof (s)); 44 vector < pair < int , int > > v; 45 int mask[ 4 ]; 46 memset(mask, 0 , sizeof (mask)); 47 mask[ 0 ] = ( 1 << SN) - 1 ; 48 for ( int i = 0 ; i < SN; i += 2 ) mask[ 1 ] |= ( 1 << i); 49 for ( int i = 1 ; i < SN; i += 2 ) mask[ 2 ] |= ( 1 << i); 50 for ( int i = 0 ; i < SN; i += 3 ) mask[ 3 ] |= ( 1 << i); 51 v.push_back(make_pair(( 1 << SN) - 1 , 0 )); 52 s[( 1 << SN) - 1 ][ 0 ] = 1 ; 53 for ( int i = 0 ; i < v.size(); i ++ ) 54 { 55 int a = v[i].first; 56 int b = v[i].second; 57 if (b > C) break ; 58 if (b == C) // && check(a)) 59 { 60 if (check(a) == false ) continue ; 61 ans.push_back(a); 62 } 63 s[a][b % 2 ] = 0 ; // 已经不在队列 64 // 扩展 65 int t; 66 for ( int j = 0 ; j < 4 ; j ++ ) 67 { 68 t = a ^ mask[j]; 69 if (s[t][(b + 1 ) % 2 ] == 0 ) 70 { 71 s[t][(b + 1 ) % 2 ] = 1 ; 72 v.push_back(make_pair(t, b + 1 )); 73 } 74 } 75 } 76 if (ans.size() == 0 ) 77 { 78 printf( " IMPOSSIBLE\n " ); 79 return ; 80 } 81 vector < string > str; 82 for ( int i = 0 ; i < ans.size(); i ++ ) 83 { 84 str.push_back(turn(ans[i], SN)); 85 } 86 sort(str.begin(), str.end()); 87 for ( int i = 0 ; i < str.size(); i ++ ) 88 { 89 for ( int j = 0 ; j < N; j ++ ) printf( " %c " , str[i][j % 6 ]); 90 printf( " \n " ); 91 } 92 } 93 94 int main() 95 { 96 freopen( " lamps.in " , " r " , stdin); 97 freopen( " lamps.out " , " w " , stdout); 98 99 scanf( " %d%d " , & N, & C); 100 int t; 101 on = 0 ; 102 off = 0 ; 103 while (scanf( " %d " , & t) && t != - 1 ) 104 { 105 t -- ; 106 t %= 6 ; 107 on |= ( 1 << t); 108 } 109 while (scanf( " %d " , & t) && t != - 1 ) 110 { 111 t -- ; 112 t %= 6 ; 113 off |= ( 1 << t); 114 } 115 go(); 116 }
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/30/1724829.html
