USACO 3.2 msquare 裸BFS-白红宇

USACO 3.2 msquare 裸BFS

阅读量：5329 次

发布时间：2019-06-14

本文共 1788 字，大约阅读时间需要 5 分钟。

又是个裸BFS...

和西安网赛那道1006一样的，只不过加上了要记录方案。顺便复习map

记录方案直接在bfs队列的结点里加一个vector<int> opt，把从开头一直到当前结点的操作序列记下来

1 /*  2 PROB:msquare  3 LANG:C++  4 */  5   6 #include 
      
         7 #include 
       
          8 #include 
        
           9 #include 
          10 #include 
          
            11 #include 
           
             12 using namespace std; 13 14 struct node 15 { 16 vector
            
              seq; 17 int step; 18 vector
             
               opt; 19 node(vector
              
                x,int m,vector
               
                 o,int op):seq(x),step(m),opt(o) 20 { 21 opt.push_back(op); 22 } 23 }; 24 25 map
                
                 
                  ,int> M; 26 queue
                  
                    Q; 27 vector
                   
                     a; //tmp2 28 vector
                    
                      A; //init 29 vector
                     
                       y; //tmp1 30 vector
                      
                        B; //goal 31 vector
                       
                         ans; 32 vector
                        
                          yy; 33 int b[10]; 34 35 bool same() 36 { 37 for (int i=0;i<8;i++) 38 if (y[i]!=b[i]) 39 return false; 40 return true; 41 } 42 43 int main() 44 { 45 freopen("msquare.in","r",stdin); 46 freopen("msquare.out","w",stdout); 47 48 B.clear(); 49 a.clear(); 50 A.clear(); 51 for (int i=0;i<=3;i++) 52 { 53 cin>>b[i]; 54 A.push_back(i+1); 55 } 56 for (int i=7;i>=4;i--) 57 { 58 cin>>b[i]; 59 A.push_back(i+1); 60 } 61 for (int i=0;i<8;i++) 62 B.push_back(b[i]); 63 64 //for (int i=0;i<8;i++) 65 // cout<
                         
                          <<" "<
                          
                           <

,int>(A,1)); 71 while (!Q.empty()) 72 { 73 node tmp=Q.front(); 74 Q.pop(); 75 int st=tmp.step; 76 //cout<<"step "<

,int>(a,1));103 Q.push(node(a,st+1,yy,1));104 }105 //opr2106 a=y;107 int t1=a[3],t2=a[7];108 a[3]=a[2]; a[7]=a[6];109 a[2]=a[1]; a[6]=a[5];110 a[1]=a[0]; a[5]=a[4];111 a[0]=t1; a[4]=t2;112 if (!M.count(a))113 {114 M.insert(pair

,int>(a,1));115 Q.push(node(a,st+1,yy,2));116 }117 //opr3118 a=y;119 int tm=a[1];120 a[1]=a[5]; a[5]=a[6]; a[6]=a[2]; a[2]=tm;121 if (!M.count(a))122 {123 M.insert(pair

,int>(a,1));124 Q.push(node(a,st+1,yy,3));125 }126 }127 }128 129 return 0;130 }

View Code

转载于:https://www.cnblogs.com/pdev/p/4032031.html