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

//第一题借鉴

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pr make_pairtypedef pair
      
        pii;const int MAX_N = 1e1 + 5; // 对题目中出现的数据范围，可以用这种方法表示，避免重复使用时出错                           // XeY 表示X * 10 ^ Y 也就是X乘以10的Y次方                           // +5 是为了防止数据溢出而额外开的空间const int d[5][3] = {
  {1, 0}, {0, 1}, {-1, 0}, {0, -1}};const char able[5] = "ULDR"; // 确定常量，方便书写bool exitable[MAX_N][MAX_N];char mp[MAX_N][MAX_N];queue
       
         que;int main() {    int ans = 0;    for (int i = 0; i < 10; i++) {        scanf("%s", mp[i]);    }    for (int j = 0; j < 10; j++) {        if (!exitable[0][j] && mp[0][j] == 'U') {            que.push(pr(0, j));            exitable[0][j] = true;        }        if (!exitable[9][j] && mp[9][j] == 'D') {            que.push(pr(9, j));            exitable[9][j] = true;        }        if (!exitable[j][0] && mp[j][0] == 'L') {            que.push(pr(j, 0));            exitable[j][0] = true;        }        if (!exitable[j][9] && mp[j][9] == 'R') {            que.push(pr(j, 9));            exitable[j][9] = true;        }    }    // 下面的这种写法被称之为广度优先搜索    while (!que.empty()) {        ans++;        int x = que.front().fi, y = que.front().se;        que.pop();        for (int i = 0; i < 4; i++) {            int tx = x + d[i][0], ty = y + d[i][1];            if (tx < 0 || tx > 9) continue;            if (ty < 0 || ty > 9) continue;            if (exitable[tx][ty]) continue;            if (mp[tx][ty] == able[i]) {                exitable[tx][ty] = true;                que.push(pr(tx, ty));            }        }    }    printf("\nans = %d\n\n", ans);    // 检验结果正确性    for (int i = 0; i < 10; i++) {        for (int j = 0; j < 10; j++) {            if (exitable[i][j]) printf("%c", mp[i][j]);            else printf("*");        }        printf("\n");    }    return 0;}
       
      
     
    
   

************************************第二道题************************************************

#include 
   
    #include 
    
     #include 
     
      #include 
      
     
    
   

从代码中可以看出，广搜的代码实现一般是这个样子的：

（1）将初始状态放入一个记录状态的queue

（2）不断地取出queue中的状态直至空

（3）每取出一个状态，遍历它所有可以到达的合法状态，并将其装入queue

运行结果（路径是倒过来印的，其实没有区别，蚂蚱可以跳过来就可以跳回去）：

拓展

我们可以发现广搜的运行就像一个三角洲，一条小河慢慢汇入大海那样：

这导致搜索的状态会越来越多，例如这道题，每一种状态有4种转移方式（其中两种是镜像），也就是说，状态数随着步数呈指数级增长。那么怎么减少状态数呢？

我们不仅知道起始状态，还知道终止状态。那么我们从两头同时广搜，结果就会少很多了=w=：

#include 
   
    #include 
    
     #include 
     
      #include 
      
     
    
   

算是对自己的一些勉励吧

#include 
   
    #include 
    
     using namespace std;int d[4]={-2,-1,1,2};int state[9];int zp;//空盘位置int visited[876543211]={0};queue
     
       q;queue
      
        cnt;void setState(int num){    for(int i=8;i>=0;i--){        if(num%10==0)            zp=i;        state[i]=num%10;        num/=10;    }}int getVal(){    int num=0;    for(int i=0;i<9;i++)        num=num*10+state[i];    return num;}bool extend(){    int num=q.front();    if(num==87654321){        return false;    }    if(visited[num])        return true;    visited[num]=true;    setState(num);    for(int i=0;i<4;i++){        state[zp]=state[(zp+d[i]+9)%9];        state[(zp+d[i]+9)%9]=0;        q.push(getVal());        cnt.push(cnt.front()+1);        setState(num);    }    return true;}int main(){    setState(12345678);    q.push(12345678);    cnt.push(0);    while(extend() && !cnt.empty()){        q.pop();        cnt.pop();    }    cout<
       
        <
       
      
     
    
   

**********另一种方法

目前暂时还没有想到可以手算求解或者dp贪心之类的办法，于是选择暴力枚举搜索状态。

关于本题搜索方法的技巧：

1.可以将空盘看成是标号为0或者9的盘子。 

#include
   
    using namespace std;#define maxn 1000000000int s=123456789,t=876543219;bool vis[maxn];int mo[4]={-2,-1,1,2},a[10];int get_val(int *a){    int sum=0;    for(int i=0;i<9;i++)    {        sum*=10;        sum+=a[i];    }    return sum;}int main(){    queue
    
     q;    queue
     
      d;    memset(vis,0,sizeof(vis));    q.push(s);    vis[s]=1;    d.push(0);    while(!d.empty())    {        int x=q.front(),cnt=8,now,dd=d.front();;        while(x>0)        {            if(x%10==9)now=cnt;            a[cnt--]=x%10;            x/=10;        }        for(int i=0;i<4;i++)        {            int k=a[now];            a[now]=a[(now+mo[i]+9)%9];            a[(now+mo[i]+9)%9]=k;            int val=get_val(a);            if(!vis[val])            {                vis[val]=1;                if(val==t)                {                    printf("ans=%d\n",dd+1);                    return 0;                }                //printf("%d\n",val);                q.push(val);                d.push(dd+1);            }            k=a[now];            a[now]=a[(now+mo[i]+9)%9];            a[(now+mo[i]+9)%9]=k;        }        q.pop();        d.pop();    }}
     
    
   

转载地址：https://blog.csdn.net/weixin_38960774/article/details/79411851 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！