【九度OJ】题目1204：农夫、羊、菜和狼的故事 -----------状态压缩+搜索-白红宇

【九度OJ】题目1204：农夫、羊、菜和狼的故事 -----------状态压缩+搜索

阅读量：7106 次

发布时间：2019-06-28

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

题目描述：

有一个农夫带一只羊、一筐菜和一只狼过河.

果没有农夫看管，则狼要吃羊，羊要吃菜.

但是船很小，只够农夫带一样东西过河。

问农夫该如何解此难题？

输入：

题目没有任何输入。

输出：

题目可能有种解决方法，求出步骤最少的解决方法，

按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。

如果需要将羊带过河去则输出“sheep_go”。

如果需要将羊带回来则输出“sheep_come”。

如果需要将菜带过河去则输出“vegetable_go”。

如果需要将菜带回来则输出“vegetable_come”。

如果需要将狼带过河去则输出“wolf_go”。

如果需要将狼带回来则输出“wolf_come”。

如果需要空手返回则输出“nothing_come”。

如果需要空手过河则输出“nothing_go”。

每输出一种方案，输出一行“succeed”。

样例输入：

样例输出：

提示：

题目可能有多组解决方法，每种方法输出后要再空一行。

一种方法中的多句话，每句话占一行。

来源：

1 #include
        
           2 #include
         
            3 #include
          
             4 #include
           
              5 #include
            
               6 #include
             
               7 #include
              
                8 #include
               
                 9 #include
                 10 #include
                 
                   11 12 using namespace std; 13 14 typedef long long ll; 15 16 queue
                  
                   
                     > q; 17 int pre[20],ans[20]; 18 bool vis[20]; 19 20 bool check(int x){ 21 if((((x>>0)&1)^((x>>2)&1))==0 && (((x>>3)&1)^((x>>2)&1))==1) 22 return true; 23 if((((x>>1)&1)^((x>>2)&1))==0 && (((x>>3)&1)^((x>>2)&1))==1) 24 return true; 25 return false; 26 } 27 28 void bfs(){ 29 while(!q.empty()) 30 q.pop(); 31 int st = 0; 32 for(int i=0;i<4;i++) 33 st |= (1<
                    
                      cur = q.front(); 40 q.pop(); 41 // cout<<"test:"<
                     
                      <<' '<
                      
                       <
                       
                        0;j--){ //j大是前面的状态 53 int a = ans[j]^ans[j-1]; 54 if(a&(1<<3)){ 55 if(a&(1<<2)){ 56 if((ans[j-1]&(1<<3)) && (ans[j-1]&(1<<2))) 57 printf("sheep_come\n"); 58 else{ 59 printf("sheep_go\n"); 60 } 61 } 62 else if(a&(1<<1)){ 63 if((ans[j-1]&(1<<3)) && (ans[j-1]&(1<<1))) 64 printf("vegetable_come\n"); 65 else{ 66 printf("vegetable_go\n"); 67 } 68 } 69 else if(a&(1<<0)){ 70 if((ans[j-1]&(1<<3)) && (ans[j-1]&(1<<0))) 71 printf("wolf_come\n"); 72 else{ 73 printf("wolf_go\n"); 74 } 75 } 76 else{ 77 if(ans[j-1]&(1<<3)){ 78 printf("nothing_come\n"); 79 } 80 else{ 81 printf("nothing_go\n"); 82 } 83 } 84 } 85 } 86 printf("succeed\n"); 87 return; 88 } 89 int x; 90 x = (cur.first^(1<<3)); 91 92 if(!check(x) && !vis[x]){ 93 q.push(make_pair(x,cur.second+1)); 94 vis[x] = true; 95 pre[x] = cur.first; 96 } 97 98 for(int i=0;i<3;i++){ 99 if(~((cur.first&(1<
                        
                         <<3))))100 x = ((cur.first^(1<
                         
                          <<3));101 if(check(x)) continue;102 if(vis[x]) continue;103 q.push(make_pair(x,cur.second+1));104 vis[x] = true;105 pre[x] = cur.first;106 }107 }108 }109 110 int main()111 {112 bfs();113 return 0;114 }

View Code

转载于:https://www.cnblogs.com/hadis-yuki/p/4835613.html

你可能感兴趣的文章