【搜索】魔板问题(BFS)-白红宇

【搜索】魔板问题(BFS)

阅读量：5965 次

发布时间：2019-06-19

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

【搜索】魔板问题

时间限制: 1 Sec 内存限制: 64 MB

提交: 5 解决: 3

[][][]

题目描述

据说能使持有者成为世界之主的上古神器隐藏在魔板空间，魔板由8个同样大小的方块组成，每个方块颜色均不相同，按顺时针方向依次写下各方块的颜色代号，例如序列（1，2，3，4，5，6，7，8）即代表图所示的魔板状态。

对于魔板可施加三种不同的操作，分别以A，B，C标识，具体操作方法如图所示。

对于每种可能的状态，这三种基本操作都可以使用。你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。

输入

只有一行，包括8个整数，用空格分开（这些整数在范围 1~8 之间），表示目标状态。

输出

第一行包括一个整数，表示最短操作序列的长度。

第二行在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。

样例输入

2 6 8 4 5 7 3 1

样例输出

7BCABCCB

提示

样例的输入目标状态是由BCABCCB这7步操作获得的，如图所示。

【分析】化为一维字符串，反正也只有八个，暴力BFS。

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define inf 0x3f3f3f3f#define mod 1000000007typedef long long ll;using namespace std;const int N = 25;const int MAX = 2000;int n,m,maxn=-1;int vis[N];string s="",anss;bool flag=false;map
                    
                     p;struct man{ string str; string ans; int step;};queue
                     
                      q;void bfs(){ string str="12348765"; string ans=""; man d;d.ans=ans;d.step=0;d.str=str; p[str]=1; q.push(d); while(!q.empty()){ man t=q.front(); // cout<
                      
                       <<" "<
                       
                        <
                        
                         =5;i--){ s+=aa[i-1]+'0'; } bfs(); cout<
                         
                          <
                          
                           <
                           
                            <

View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5743757.html

你可能感兴趣的文章

很实用的小功能，通过配置Web.xml让点击文件路径的超链接，直接下载而不会在浏览器上尝试打开...