[关闭]
@wwwqeqeqeqe 2019-05-05T10:12:08.000000Z 字数 9441 阅读 752

搜索问题讨论（2019.5.7）

搜索

A 生日蛋糕（POJ 1190）

题目：

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q = Sπ 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）

解题思路：

因为题目说了所有数据都是整数，所以，我们可以通过穷举法来进行操作。因为我们的蛋糕一共有m层，而且从上往下是一定递增的。那么，从第1、2、3、······、m层的最小半径和高度都是当前层数的数值。因此，我们就找到了下界。同时，因为n最大为10000，当h=1时，r最大为100，当r=1时，h最大为10000，因此我们找到了上界。我们可以通过枚举来进行查找。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int INF=0x3f3f3f3f;
  10. int n,m;
  11. int ans;
  13. void dfs(int t,int sumS,int sumV,int r,int h)
  14. {
  15.     if(t == 0)
  16.     {
  17.         if(sumV == n)
  18.             ans=min(sumS,ans);
  19.         return;
  20.     }
  21.     for(int i=r-1;i>=t;i--)
  22.     {
  23.         if(t == m)
  24.             sumS = i*i;
  25.         int mh=h-1;
  26.         for(int j=mh;j>=t;j--)
  27.         {
  28.             dfs(t-1,sumS+i*j*2,sumV+i*i*j,i,j);
  29.         }
  30.     }
  31. }
  33. int main()
  34. {
  35.     cin >> n >> m;
  36.     ans=INF;
  37.     dfs(m,0,0,100,10000);
  38.     if(ans == INF)
  39.         ans=0;
  40.     cout << ans << endl;
  41. }
我们就通过题目大意得到了这样一个代码。但是，很显然，如果我们直接交上去，肯定会TLE，因为我们这个代码是没有进行剪枝的。那要如果进行剪枝呢？首先我们知道，我们要求的是最小的表面积，那么，当我们在计算过程中得到的表面积已经比我们得到的最小表面积大了，那么，这个答案肯定不是我们需要的那个答案，可以直接return。同时，当我们的体积已经比n大的时候，很显然我们最后的结果sumV！=n，也直接return。同时，因为2*r*h=S,r*r*h=V,那么，S=V*2/r,r越大，S越小。所以，我们把剩下的体积（n-sumV）全部只用来做成一个圆柱体，他所增加的表面积是最小的。所以，当我们把这个剩余体积全部换成表面积加上之前的表面积大于ans的话，也是直接return掉的。于是，我们得到了最后的代码。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int INF=0x3f3f3f3f;
  10. int n,m;
  11. int ans;
  12. int mnS[50],mnV[50];
  14. void dfs(int t,int sumS,int sumV,int r,int h)
  15. {
  16.     if(t == 0)
  17.     {
  18.         if(sumV == n)
  19.             ans=min(sumS,ans);
  20.         return;
  21.     }
  22.     if(sumS+mnS[t] > ans || sumV+mnV[t] > n)
  23.         return;
  24.     if(2*(n-sumV)/r+sumS >=ans)
  25.         return;
  26.     for(int i=r-1;i>=t;i--)
  27.     {
  28.         if(t == m)
  29.             sumS = i*i;
  30.         int mh=h-1;
  31.         for(int j=mh;j>=t;j--)
  32.         {
  33.             dfs(t-1,sumS+i*j*2,sumV+i*i*j,i,j);
  34.         }
  35.     }
  36. }
  38. int main()
  39. {
  40.     mnS[0]=0;
  41.     mnV[0]=0;
  42.     for(int i=1;i<22;i++)
  43.     {
  44.         mnS[i]=mnS[i-1]+i*i*2;
  45.         mnV[i]=mnV[i-1]+i*i*i;
  46.     }
  47.     cin >> n >> m;
  48.     ans=INF;
  49.     dfs(m,0,0,100,10000);
  50.     if(ans == INF)
  51.         ans=0;
  52.     cout << ans << endl;
  53. }

B Eight（POJ 1077）

题目大意：

题目给你一个3X3的格子，里面有1~8 八个数以及一个字母X，每次将X和旁边的一个数交换，问是否能够得到最后的序列使得图形满足从左往右，从上往下依次为1~8，最后一格为X。如果存在，则输出X运动的轨迹。如果没有，输出unsolvable。

解题思路：

因为一共只有9个格子，我们可以通过康拓展开获取当前状态的一个hash值，接着使用BFS对状态进行搜索，在搜索的过程中保存状态的转移过程。当我们的hash值为1的时候，那么我们就找到了我们需要的答案，return true即可。如果我们没有找到满足条件的答案，则return false。最后根据返回结果来进行答案的输出。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<queue>
  7. using namespace std;
  9. const int maxn=1e6+5;
  10. const int dx[]={-1,1,0,0};
  11. const int dy[]={0,0,-1,1};
  12. const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
  13. const char d[]={'u','d','l','r'};
  15. char path[maxn];
  16. int pre[maxn];
  17. int vis[maxn];
  18. char str[55];
  20. struct node
  21. {
  22.     int status;
  23.     int s[15];
  24.     int loc;
  25. };
  27. int cantor(int s[])
  28. {
  29.     int sum=0;
  30.     for(int i=0;i<9;i++)
  31.     {
  32.         int num=0;
  33.         for(int j=i+1;j<9;j++)
  34.         {
  35.             if(s[j]<s[i])
  36.                 num++;
  37.         }
  38.         sum+=num*fac[8-i];
  39.     }
  40.     return sum+1;
  41. }
  44. bool bfs(node now)
  45. {
  46.     memset(vis,0,sizeof(vis));
  47.     queue<node>q;
  48.     now.status=cantor(now.s);
  49.     pre[now.status]=-1;
  50.     vis[now.status]=1;
  51.     node t;
  52.     q.push(now);
  53.     while(q.size())
  54.     {
  55.         now=q.front();
  56.         q.pop();
  57.         if(now.status == 1)
  58.             return true;
  60.         int x=now.loc/3;
  61.         int y=now.loc%3;
  62.         for(int i=0;i<4;i++)
  63.         {
  64.             int xx=x+dx[i];
  65.             int yy=y+dy[i];
  66.             if(xx>=0 && xx<=2 && yy>=0 && yy<=2)
  67.             {
  68.                 t=now;
  69.                 t.s[x*3+y]=t.s[xx*3+yy];
  70.                 t.s[xx*3+yy]=9;
  71.                 t.status=cantor(t.s);
  72.                 if(!vis[t.status])
  73.                 {
  74.                     vis[t.status]=1;
  75.                     t.loc=xx*3+yy;
  76.                     pre[t.status]=now.status;
  77.                     path[t.status]=d[i];
  78.                     q.push(t);
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     return false;
  84. }
  86. void Print(int status)
  87. {
  88.     if(pre[status] == -1)
  89.         return;
  90.     Print(pre[status]);
  91.     cout << path[status] ;
  92. }
  94. int main()
  95. {
  96.     scanf("%[^\n]s",str);
  97.     node now;
  98.     int cnt=0;
  99.     for(int i=0;str[i]!='\0';i++)
  100.     {
  101.         if(str[i] == ' ')
  102.             continue;
  103.         if(str[i] == 'x')
  104.         {
  105.             now.s[cnt]=9;
  106.             now.loc=cnt++;
  107.         }
  108.         else
  109.         {
  110.             now.s[cnt++]=str[i]-'0';
  111.         }
  112.     }
  113.     if(!bfs(now))
  114.     {
  115.         cout << "unsolvable" <<endl;
  116.     }
  117.     else
  118.     {
  119.         Print(1);
  120.         cout <<endl;
  121.     }
  122.     return 0;
  123. }

C Robot（POJ 1376）

题目大意：

给出一张图，图中有一个机器人，给出机器人的起点和终点以及初始朝向，算出机器人从起点左上角到达终点左上角的最小花费时间。每花费一个单位时间，可以朝当前方向前进1~3格，或者向左或向右旋转一次。

解题思路：

因为题目给出的地图是按照格子给出的，但是机器人是在方格的线上进行移动的，因此，在判断当前方格是否有障碍时需要注意判断一下,另外，地图边界也不能走。其他的就和普通BFS一样做。

AC代码:

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<queue>
  7. using namespace std;
  9. const int maxn=1e2+5;
  10. const int dx[]= {-1,0,1,0};
  11. const int dy[]= {0,1,0,-1};
  13. struct node
  14. {
  15.     int x,y;
  16.     int time;
  17.     int pos;
  18. };
  20. int n,m,mp[maxn][maxn];
  21. int vis[maxn][maxn][5];
  23. int getpos(char *str)
  24. {
  25.     if(!strcmp(str,"north"))
  26.         return 0;
  27.     if(!strcmp(str,"east"))
  28.         return 1;
  29.     if(!strcmp(str,"south"))
  30.         return 2;
  31.     return 3;
  32. }
  34. bool check(int x,int y)
  35. {
  37.     if(x<1||x>=n||y<1||y>=m)
  38.         return false;
  39.     if(mp[x][y]||mp[x+1][y]||mp[x][y+1]||mp[x+1][y+1])
  40.         return false;
  41.     return true;
  42. }
  44. int main()
  45. {
  46.     while(cin >> n >> m &&(n || m))
  47.     {
  48.         for(int i=1; i<=n; i++)
  49.         {
  50.             for(int j=1; j<=m; j++)
  51.             {
  52.                 cin >> mp[i][j];
  53.             }
  54.         }
  55.         node bg,ed;
  56.         memset(vis,0,sizeof(vis));
  57.         cin >> bg.x >> bg.y;
  58.         cin >> ed.x >> ed.y;
  59.         char op[25];
  60.         cin >> op;
  61.         bg.pos=getpos(op);
  62.         bg.time=0;
  63.         queue<node> a;
  64.         a.push(bg);
  65.         vis[bg.x][bg.y][bg.pos]=1;
  66.         int ans=-1;
  67.         if(bg.x == ed.x && bg.y == ed.y)
  68.         {
  69.             cout << 0 << endl;
  70.             continue;
  71.         }
  72.         if(!check(ed.x,ed.y))
  73.         {
  74.             cout << -1 << endl;
  75.             continue;
  76.         }
  77.         while(a.size())
  78.         {
  79.             node aa=a.front();
  80.             a.pop();
  81.             int xx=aa.x;
  82.             int yy=aa.y;
  83.             for(int i=1; i<=3; i++)
  84.             {
  85.                 xx+=dx[aa.pos];
  86.                 yy+=dy[aa.pos];
  87.                 if(!check(xx,yy))
  88.                     break;
  89.                 if(xx == ed.x && yy==ed.y)
  90.                 {
  91.                     ans=aa.time+1;
  92.                     break;
  93.                 }
  94.                 if(!vis[xx][yy][aa.pos])
  95.                 {
  96.                     node ab;
  97.                     ab.x=xx;
  98.                     ab.y=yy;
  99.                     ab.time=aa.time+1;
  100.                     ab.pos=aa.pos;
  101.                     vis[xx][yy][ab.pos]=1;
  102.                     a.push(ab);
  103.                 }
  104.             }
  105.             for(int i=0; i<4; i++)
  106.             {
  107.                 if(max(aa.pos,i)-min(aa.pos,i) == 2)
  108.                     continue;
  109.                 if(vis[aa.x][aa.y][i])
  110.                     continue;
  111.                 node ab=aa;
  112.                 ab.time=aa.time+1;
  113.                 ab.pos=i;
  114.                 vis[ab.x][ab.y][ab.pos]=1;
  115.                 a.push(ab);
  116.             }
  117.             if(ans!=-1)
  118.                 break;
  119.         }
  120.         cout << ans << endl;
  121.     }
  122.     return 0;
  123. }

D Pushing Boxes （POJ 1475）

题目大意：

题目给出一张地图，地图里面给出人的位置，箱子的位置以及箱子到达的目的地。让你设计一种方案，是我们可以推最少次数的箱子让箱子到达目的地。如果没有能将箱子推向目的地的方案，则输出Impossible.，否则，在自己单独行动的时候输出小写的方位，在推箱子的时候输出大写的方位。

解题思路：

我们优先对箱子进行BFS，每移动一次箱子，就对人进行一次BFS，找到人从当前路径走到推箱子的下一步所需要的位置的最短路径。这个位置的具体位置通过箱子对应的下一步移动的相反方向来查找，具体在箱子移动方向相反位置的那个格子内，如果相反方向是墙或者人到不了的地方，就返回false，进而这次箱子的移动无效。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<queue>
  7. #include<string>
  8. using namespace std;
  10. const int dx[]= {-1,0,1,0};
  11. const int dy[]= {0,1,0,-1};
  12. const char dpathB[4] = {'N', 'E', 'S', 'W'};
  13. const char dpathP[4] = {'n', 'e', 's', 'w'};
  15. int n,m;
  16. char mp[25][25];
  17. int sx, sy;
  18. int bx, by;
  19. string ans;
  22. struct person
  23. {
  24.     int x,y;
  25.     string path;
  26. };
  28. struct status
  29. {
  30.     int px,py,bx,by;
  31.     string path;
  32. };
  34. bool check(int x, int y)
  35. {
  36.     if(x<0 || x>=n || y<0 || y>=m)
  37.         return false;
  38.     if(mp[x][y]=='#')
  39.         return false;
  40.     return true;
  41. }
  43. bool bfs2(int ppx, int ppy, int bbx, int bby, int kx, int ky, string &path)
  44. {
  45.     int vis[25][25];
  46.     memset(vis, 0, sizeof(vis));
  47.     vis[ppx][ppy] = 1;
  48.     vis[kx][ky] = 1;
  49.     person first;
  50.     first.x = ppx;
  51.     first.y = ppy;
  52.     first.path = "";
  53.     queue<person> myPerson;
  54.     myPerson.push(first);
  55.     while(!myPerson.empty())
  56.     {
  57.         person now = myPerson.front();
  58.         myPerson.pop();
  59.         if(now.x==bbx && now.y==bby)
  60.         {
  61.             path = now.path;
  62.             return true;
  63.         }
  64.         for(int i=0; i<4; i++)
  65.         {
  66.             int zx = now.x + dx[i];
  67.             int zy = now.y + dy[i];
  68.             if(check(zx, zy) && !vis[zx][zy])
  69.             {
  70.                 vis[zx][zy] = 1;
  71.                 person next;
  72.                 next.x = zx;
  73.                 next.y = zy;
  74.                 next.path = now.path +  dpathP[i];
  75.                 myPerson.push(next);
  76.             }
  77.         }
  78.     }
  79.     return false;
  80. }
  82. bool bfs()
  83. {
  84.     int vis[25][25];
  85.     memset(vis, 0, sizeof(vis));
  86.     status first;
  87.     first.bx = bx;
  88.     first.by = by;
  89.     first.px = sx;
  90.     first.py = sy;
  91.     first.path = "";
  92.     vis[bx][by] = 1;
  93.     queue<status> myPath;
  94.     myPath.push(first);
  95.     while(!myPath.empty())
  96.     {
  97.         status now = myPath.front();
  98.         myPath.pop();
  99.         for(int i=0; i<4; i++)
  100.         {
  101.             int bbx = now.bx + dx[i];
  102.             int bby = now.by + dy[i];
  103.             int tx = now.bx - dx[i];
  104.             int ty = now.by - dy[i];
  105.             string path = "";
  106.             if(check(bbx, bby) && check(tx, ty) && !vis[bbx][bby])
  107.             {
  108.                 if(bfs2(now.px, now.py, tx, ty, now.bx, now.by, path))
  109.                 {
  110.                     vis[bbx][bby] = 1;
  111.                     status next;
  112.                     next.bx = bbx;
  113.                     next.by = bby;
  114.                     next.px = now.bx;
  115.                     next.py = now.by;
  116.                     next.path = now.path + path + dpathB[i];
  117.                     if(mp[bbx][bby]=='T')
  118.                     {
  119.                         ans = next.path;
  120.                         return true;
  121.                     }
  122.                     myPath.push(next);
  123.                 }
  124.             }
  125.         }
  126.     }
  127.     return false;
  128. }
  130. int main()
  131. {
  132.     int cc = 0;
  133.     while(cin >> n >> m)
  134.     {
  135.         ans = '\0';
  136.         cc++;
  137.         getchar();
  138.         memset(mp, 0, sizeof(mp));
  139.         if(n==0 && m==0) break;
  140.         for(int i=0; i<n; ++i)
  141.         {
  142.             scanf("%s", mp[i]);
  143.             getchar();
  144.             for(int j=0; j<m; j++)
  145.             {
  146.                 if(mp[i][j]=='S')
  147.                 {
  148.                     sx = i;
  149.                     sy = j;
  150.                 }
  151.                 if(mp[i][j]=='B')
  152.                 {
  153.                     bx = i;
  154.                     by = j;
  155.                 }
  156.             }
  157.         }
  158.         cout << "Maze #" << cc << endl;
  159.         if(bfs())
  160.             cout << ans << endl;
  161.         else
  162.             cout << "Impossible." << endl;
  163.         cout << endl;
  164.     }
  165.     return 0;
  166. }

E Dearboy's Puzzle （POJ 2308）

题目大意：

题目给出一个地图，里面有ABCD和*五种字符，*表示为空，ABCD表示有四种卡片，然后对这四种卡片进行连连看消除。最后问给出的地图能否通过连连看消除所有的ABCD。

解题思路:

首先统计ABCD四种牌的张数，如果存在某种牌有奇数个，那么无解。接着对地图外层进行DFS查找，指定一张牌来想办法把这张牌消除。再通过BFS以指定的这张牌为起点，查询能够和他配对的牌。找到后，再枚举这张牌与哪一张牌相消或者当前这张牌不消。在消除的过程中，需要单独判断AB这种情况。
          BA

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<queue>
  7. using namespace std;
  9. const int dx[]= {1,-1,0,0};
  10. const int dy[]= {0,0,1,-1};
  12. int mp[12][12],n,m,num[5],sum;
  13. bool flag,vis[11][11];
  14. char str[12];
  16. struct Node
  17. {
  18.     int x,y,turn,d;
  19.     Node() {}
  20.     Node(int a,int b,int c,int dd)
  21.     {
  22.         x = a;
  23.         y = b;
  24.         turn = c;
  25.         d = dd;
  26.     }
  27. };
  29. void Init()
  30. {
  31.     memset(mp,0,sizeof mp);
  32.     memset(num,0,sizeof num);
  33.     sum = flag = 0;
  34. }
  36. bool inarea(int x,int y)
  37. {
  38.     if(x<1||y<1||x>n||y>m) return false;
  39.     else return true;
  40. }
  42. void bfs(int x,int y,int w,Node *can,int &len)
  43. {
  44.     memset(vis,0,sizeof vis);
  45.     queue<Node> Q;
  46.     Q.push(Node(x,y,0,-1));
  47.     vis[x][y] = 1;
  48.     while(!Q.empty())
  49.     {
  50.         Node u = Q.front();
  51.         Q.pop();
  52.         if(mp[u.x][u.y] == w)
  53.         {
  54.             can[++len].x = u.x;
  55.             can[len].y = u.y;
  56.             continue;
  57.         }
  58.         for(int i = 0; i < 4; i++)
  59.         {
  60.             int tx = u.x+dx[i],ty = u.y+dy[i],tturn = 0;
  61.             if(!inarea(tx,ty) || (mp[tx][ty] != -1&&mp[tx][ty] != w) || vis[tx][ty]) continue;
  62.             if(u.d == i||u.d == -1)
  63.                 tturn = u.turn;
  64.             else tturn = u.turn+1;
  65.             if(tturn > 2) continue;
  66.             vis[tx][ty] = 1;
  67.             Q.push(Node(tx,ty,tturn,i));
  68.         }
  69.     }
  70. }
  72. bool check()
  73. {
  74.     for(int i = 1; i < n; i++)
  75.         for(int j = 1; j < m; j++)
  76.         {
  77.             if(mp[i][j] != -1&&mp[i][j+1] != -1&&mp[i][j] != mp[i][j+1])
  78.             {
  79.                 if(mp[i][j] == mp[i+1][j+1]&&mp[i][j+1] == mp[i+1][j]&&num[mp[i][j]] == 2&&num[mp[i][j+1]] == 2)
  80.                     return false;
  81.             }
  82.         }
  83.     return true;
  84. }
  86. void dfs(int cur)
  87. {
  88.     if(cur == 0)
  89.     {
  90.         flag = 1;
  91.         return;
  92.     }
  93.     if(flag) return;
  94.     if(!check()) return;
  95.     for(int i = 1; i <= n; i++)
  96.         for(int j = 1; j <= n; j++)
  97.         {
  98.             if(flag) return;
  99.             if(mp[i][j] != -1)
  100.             {
  101.                 int w = mp[i][j],len = 0;
  102.                 Node can[110];
  103.                 mp[i][j] = -1;
  104.                 bfs(i,j,w,can,len);
  105.                 for(int k = 1; k <= len; k++)
  106.                 {
  107.                     mp[can[k].x][can[k].y] = -1;
  108.                     num[w] -= 2;
  109.                     dfs(cur-2);
  110.                     num[w] += 2;
  111.                     mp[can[k].x][can[k].y] = w;
  112.                 }
  113.                 mp[i][j] = w;
  114.             }
  115.         }
  116. }
  118. int main()
  119. {
  120.     while(scanf("%d%d",&n,&m) != EOF&&n+m)
  121.     {
  122.         Init();
  123.         for(int i = 1; i <= n; i++)
  124.         {
  125.             scanf("%s",str+1);
  126.             for(int j = 1; j <= m; j++)
  127.             {
  128.                 if(str[j] == '*') mp[i][j] = -1;
  129.                 else mp[i][j] = str[j]-'A'+1,num[str[j]-'A'+1]++;
  130.             }
  131.         }
  132.         sum = num[1]+num[2]+num[3]+num[4];
  133.         if(num[1]%2||num[2]%2||num[3]%2||num[4]%2)
  134.         {
  135.             printf("no\n");
  136.             continue;
  137.         }
  138.         dfs(sum);
  139.         if(flag) printf("yes\n");
  140.         else printf("no\n");
  141.     }
  142. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注