[关闭]
@wwwqeqeqeqe 2019-05-10T07:20:39.000000Z 字数 16978 阅读 1022

搜索问题讨论（2019.5.11）

搜索

A Cleaning Robot （POJ 2688）

题目大意：

题目给出一张地图，地图中有四种符号，其中，'o'表示机器人的初始位置，'.'表示可以通过的地板，'x'表示家具的位置，相当于墙，'*'表示脏地板，需要我们去清扫。题目要求机器人清扫完所有的脏地板并且所走距离最小，如果存在，则输出这个最小距离，如果不存在，则输出-1.

解题思路：

我们将机器人和每一块脏地板看成一个图上的各个顶点，那么题目就变为了在一个无向图中，遍历各个顶点至少一次，使总路程最小的问题，这样就变为了一个典型的TSP问题，我们再通过状压DP来进行解决。

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 INF=0x3f3f3f3f;
  10. const int dx[]= {1,0,-1,0};
  11. const int dy[]= {0,1,0,-1};
  13. int r,c,psum,ans;
  14. char s[25][25];
  15. int mp[12][12];
  16. bool f[12];
  18. struct node
  19. {
  20.     int x,y,l;
  21. };
  22. node P[12];
  24. int fnd(int x,int y)
  25. {
  26.     for(int i=0; i<psum; ++i)
  27.     {
  28.         if(P[i].x==x && P[i].y==y)
  29.             return i;
  30.     }
  31. }
  33. int init()
  34. {
  35.     cin >> c >> r;
  36.     if(r==0 && c==0)
  37.         return 0;
  38.     int i,j;
  39.     psum=1;
  40.     for(int i=0; i<r; ++i)
  41.     {
  42.         cin >> s[i];
  43.         for(j=0; j<c; ++j)
  44.         {
  45.             if(s[i][j]=='o')
  46.             {
  47.                 P[0].x=i;
  48.                 P[0].y=j;
  49.                 s[i][j]='*';
  50.             }
  51.             else if(s[i][j]=='*')
  52.             {
  53.                 P[psum].x=i;
  54.                 P[psum++].y=j;
  55.             }
  56.         }
  57.     }
  58.     queue<node> q;
  59.     node u,v;
  60.     for(i=0; i<12; ++i)
  61.         for(j=0; j<12; ++j)
  62.             mp[i][j]=INF;
  64.     int xx,yy;
  65.     for(i=0; i<psum; ++i)
  66.     {
  67.         int f[25][25];
  68.         memset(f,0,sizeof(f));
  69.         u.x=P[i].x;
  70.         u.y=P[i].y;
  71.         u.l=0;
  72.         q.push(u);
  73.         f[u.x][u.y]=1;
  74.         int cnt=psum;
  75.         while(!q.empty()&&cnt)
  76.         {
  77.             u=q.front();
  78.             q.pop();
  79.             for(j=0; j<4&&cnt; ++j)
  80.             {
  81.                 xx=u.x+dx[j];
  82.                 yy=u.y+dy[j];
  83.                 if(xx<0 || xx>=r || yy<0 || yy>=c)
  84.                     continue;
  85.                 if(s[xx][yy]=='x' || f[xx][yy])
  86.                     continue;
  87.                 if(s[xx][yy]=='*')
  88.                 {
  89.                     cnt--;
  90.                     mp[i][fnd(xx,yy)]=u.l+1;
  91.                 }
  92.                 f[xx][yy]=1;
  93.                 v.x=xx;
  94.                 v.y=yy;
  95.                 v.l=u.l+1;
  96.                 q.push(v);
  97.             }
  98.         }
  99.         while(!q.empty())
  100.             q.pop();
  101.     }
  102.     return 1;
  103. }
  105. bool is()
  106. {
  107.     int i;
  108.     for(i=1; i<psum; ++i)
  109.         if(mp[0][i]==INF)
  110.             return 1;
  111.     return 0;
  112. }
  114. void dfs(int t,int sum,int cur)
  115. {
  116.     if(cur==psum)
  117.     {
  118.         if(sum<ans) ans=sum;
  119.             return;
  120.     }
  121.     for(int i=1; i<psum; ++i)
  122.     {
  123.         if(!f[i] && sum+mp[t][i]<ans)
  124.         {
  125.             f[i]=1;
  126.             dfs(i,sum+mp[t][i],cur+1);
  127.             f[i]=0;
  128.         }
  129.     }
  130. }
  132. int main()
  133. {
  134.     while(init())
  135.     {
  136.         if(is())
  137.         {
  138.             cout << -1 << endl;
  139.             continue;
  140.         }
  141.         ans=INF;
  142.         memset(f,0,sizeof(f));
  143.         dfs(0,0,1);
  144.         if(ans==INF || ans==0)
  145.             ans=-1;
  146.         cout << ans << endl;
  147.     }
  148.     return 0;
  149. }

B Bloxorz I (POJ 3322)

题目大意：

题目给出一张地图，地图中有一个1*2的方块，题目要求求出最少的滚动次数，将这个1*2的方块从地图中的某个空格处滑落。地图中一共有五种字符，其中，'#'表示墙，是不能通过的，'X'表示初始方块的位置，可能有1到2个，表示方块一开始是横放或竖放在这1到2个方格上的。'E'表示这个方块是脆弱的方块，只能承受横放方块的重量，即方块不能竖立在这种方块上，'.'表示可以正常通过的方块，'O'表示最后我们要滑落的终点。题目保证'x'和'O'的位置的方块都能承受单个方块的重量（即不是脆弱的方块），而且最后到达终点时，方块一定是竖着的（因为最终终点只有一个O）。

解题思路：

我们可以将方块的方向分别用数字表示，0表示竖着的方块，1表示竖着放置的方块，2表示横着放置的方块。记录完方块姿态后，将横放着的方块标记为左边那个点，竖放着的点记录为上面那个点。接着，就可以通过BFS对方块进行搜索，注意搜索过程中对‘E’和‘#’的判断，最后得到状态为0的时候标记点在终点的最小答案。

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 INF = 0x3f3f3f3f;
  10. const int MAXN = 1e3 + 5;
  11. const int MAXM = 1e3 + 5;
  13. const int dx[3][4] = {{-2,1,0,0},{-1,2,0,0},{0,0,-1,1}};
  14. const int dy[3][4] = {{0,0,-2,1},{0,0,-1,1},{-1,2,0,0}};
  15. const int dz[3][4] = {{1,1,2,2},{0,0,1,1},{0,0,2,2}};
  17. char g[MAXN][MAXM];
  18. int n,m,sx,sy,sz,ex,ey;
  20. struct Point
  21. {
  22.     int x,y,z,step;
  23.     Point() {}
  24.     Point(int _x, int _y, int _z, int _step)
  25.     {
  26.         x = _x;
  27.         y = _y;
  28.         z = _z;
  29.         step = _step;
  30.     }
  31. };
  33. queue<Point> q;
  34. int b[MAXN][MAXM][4];
  36. int check(Point a)
  37. {
  38.     if(a.z == 0 && !(a.x > n || a.x < 1 || a.y > m || a.y < 1) && !b[a.x][a.y][a.z] && g[a.x][a.y] != 'E' && g[a.x][a.y] != '#')
  39.         return 0;
  40.     if(a.z == 1 && !(a.x < 1 || a.x + 1 > n || a.y < 1 || a.y > m) && !b[a.x][a.y][a.z] && g[a.x][a.y] != '#' && g[a.x + 1][a.y] != '#')
  41.         return 0;
  42.     if(a.z == 2 && !(a.x < 1 || a.x > n || a.y < 1 || a.y + 1 > m) && !b[a.x][a.y][a.z] && g[a.x][a.y] != '#' && g[a.x][a.y + 1] != '#')
  43.         return 0;
  44.     return 1;
  45. }
  47. int bfs()
  48. {
  49.     memset(b, 0, sizeof(b));
  50.     while(q.size())
  51.         q.pop();
  52.     q.push(Point(sx, sy, sz, 0));
  53.     Point now;
  54.     b[sx][sy][sz] = true;
  55.     while(q.size())
  56.     {
  57.         now = q.front();
  58.         q.pop();
  59.         for(int i = 0; i < 4; ++ i)
  60.         {
  61.             Point tmp;
  62.             tmp = Point(now.x + dx[now.z][i],now.y + dy[now.z][i], dz[now.z][i], now.step + 1);
  63.             if(check(tmp))
  64.                 continue;
  65.             if(tmp.x == ex && tmp.y == ey && !tmp.z)
  66.                 return tmp.step;
  67.             q.push(tmp);
  68.             b[tmp.x][tmp.y][tmp.z] = 1;
  69.         }
  70.     }
  71.     return -1;
  72. }
  74. int main()
  75. {
  76.     while (~scanf("%d %d", &n, &m) && n)
  77.     {
  78.         for(int i = 1; i <= n; ++ i)
  79.             scanf("%s", g[i] + 1);
  80.         for (int i = 1; i <= n; ++ i)
  81.         {
  82.             for (int j = 1; j <= m; ++ j)
  83.             {
  85.                 if (g[i][j] == 'O')
  86.                     ex = i,ey = j;
  87.                 else if (g[i][j] == 'X' && g[i + 1][j] == 'X')
  88.                 {
  89.                     sx = i,sy = j;
  90.                     g[i + 1][j] = '.';
  91.                     sz = 1;
  92.                 }
  93.                 else if(g[i][j] == 'X' && g[i][j + 1] == 'X')
  94.                 {
  95.                     g[i][j + 1] = '.';
  96.                     sx = i,sy = j;
  97.                     sz = 2;
  98.                 }
  99.                 else if(g[i][j] == 'X')
  100.                 {
  101.                     sx = i,sy = j ;
  102.                     sz = 0;
  103.                 }
  104.             }
  105.         }
  106.         int ans = bfs();
  107.         if(ans == -1)
  108.             printf("Impossible\n");
  109.         else
  110.             printf("%d\n", ans);
  111.     }
  112.     return 0;
  113. }

C Remmarguts' Date （POJ 2449）

题目大意：

题目给出一张有向图，图中有n个点m条边，接下来给出m条边的起始端点，结束端点以及他们之间的距离。最后给出地图的起点和终点，问从起点到终点的第K大的距离时多少。没有就输出-1.

解题思路：

首先，我们可以通过dijkstra或者spfa处理出所有点到终点的距离，保存在一个数组中。然后采用A*算法，按照g+h从小到大的顺序进行排序，其中，g表示从起点到当前点的距离，h表示当前点到终点的预期距离，即之前通过最短路求到的那个值。然后用times记录每个点被找到的次数，直到记录到第k次找到终点即可。因为我们要求的是所有点到终点的距离，而且这个图是有向图，所以我们还需要建立一个反图来跑dijkstra。

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <queue>
  7. using namespace std;
  9. typedef long long ll;
  10. const int INF = 0x3f3f3f3f;
  11. const int MAXN = 1e3+5;
  13. struct vertex
  14. {
  15.     int sum, h, pos;
  16.     bool operator < (vertex a) const
  17.     {
  18.         return a.sum + a.h < sum + h;
  19.     }
  20. };
  22. struct sc
  23. {
  24.     int u, v, w, next;
  25. };
  27. sc line1[MAXN*MAXN],line2[MAXN*MAXN];
  28. int link1[MAXN],link2[MAXN],h[MAXN],times[MAXN];
  29. int n, m, s, e, k;
  30. bool vis[MAXN];
  31. priority_queue <vertex> que;
  33. void init()
  34. {
  35.     memset(link1, 0, sizeof(link1));
  36.     memset(link2, 0, sizeof(link2));
  37.     memset(vis,0,sizeof(vis));
  38.     memset(h,0x3f,sizeof(h));
  39.     while (!que.empty())
  40.         que.pop();
  41.     memset(times,0,sizeof(times));
  42. }
  44. void djikstra()
  45. {
  46.     int i,k,p;
  47.     h[e] = 0;
  48.     for (p = 1; p <= n; ++p)
  49.     {
  50.         k = 0;
  51.         for (i = 1; i <= n; ++i)
  52.             if (!vis[i] && (!k||h[i]<h[k])) k = i;
  53.         vis[k] = true;
  54.         k = link2[k];
  55.         while (k)
  56.         {
  57.             if (h[line2[k].v] > h[line2[k].u] + line2[k].w)
  58.                 h[line2[k].v] = h[line2[k].u] + line2[k].w;
  59.             k = line2[k].next;
  60.         }
  61.     }
  62. }
  64. int Astar()
  65. {
  66.     int t;
  67.     vertex g,temp;
  68.     g.pos = s;
  69.     g.sum = 0;
  70.     g.h = h[s];
  71.     que.push(g);
  72.     if (s==e) ++k;
  73.     while (!que.empty())
  74.     {
  75.         g = que.top();
  76.         que.pop();
  77.         ++times[g.pos];
  78.         if (times[g.pos] == k && g.pos == e) 
  79.             return g.sum + g.h;
  80.         if (times[g.pos] > k) 
  81.             continue;
  82.         t = link1[g.pos];
  83.         while (t)
  84.         {
  85.             temp.sum = g.sum + line1[t].w;
  86.             temp.h = h[line1[t].v];
  87.             temp.pos = line1[t].v;
  88.             que.push(temp);
  89.             t = line1[t].next;
  90.         }
  91.     }
  92.     return -1;
  93. }
  95. int main()
  96. {
  97.     while(cin >> n >> m)
  98.     {
  99.         init();
  100.         for (int i = 1; i <= m; ++i)
  101.         {
  102.             cin >> line1[i].u >> line1[i].v >> line1[i].w;
  103.             line1[i].next = link1[line1[i].u];
  104.             link1[line1[i].u] = i;
  105.             line2[i].u = line1[i].v;
  106.             line2[i].v = line1[i].u;
  107.             line2[i].w = line1[i].w;
  108.             line2[i].next = link2[line2[i].u];
  109.             link2[line2[i].u] = i;
  110.         }
  111.         cin >> s >> e >> k;
  112.         djikstra();
  113.         cout << Astar() << endl;
  114.     }
  115.     return 0;
  116. }

D Weather Forecast (POJ 2044)

题目大意：

题目给出一个由4*4的方格组成的图形，表示一个国家和这个国家的16个地区。我们作为风神，需要使一个2*2的云在这个国家中运动，每次这个云可以向东西南北四个方向中的一个运动1或2格，或者这个云不动。输入首先输入一个n表示我们需要探测的n天，接下来的n行，每行16个数表示这16个地区，其中0表示平时，1表示赶集日或节日，其中这一天这个地区不能下雨（及有云）。并且我们还必须保证每个地区不会出现连续7天没有下雨的情况。

解题思路：

我们要保证16个方格中，每个方格7天内都下过雨，因为云是2*2的，那么，我们只需要保证7天内四个角都下过去即可。对于云，我们每次都九种不同的运动规则，暴力循环搜索即可。在搜索的过程中，我们开一个6维的数组，分别表示第i天，云处于第x个位置，四个角落有多少天没有被下雨，在后面查找的过程中，如果发现这个状态已经找过，就不用再找了。对于某个城市某一天的情况，可以使用位运算来进行表示。

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <queue>
  7. using namespace std;
  9. int DAY[367];
  10. bool mark[366][10][8][8][8][8];
  11. int ys[12] = {0,1,2,3,0,4,5,6,0,7,8,9};
  12. int dir[9][2] = {0,0,0,1,0,-1,1,0,-1,0,0,2,0,-2,2,0,-2,0};
  13. int OK,T;
  16. bool ok(int t,int x,int y,int a[])
  17. {
  18.     int aa = (x - 1) * 4 + y;
  19.     int bb= (x - 1 + 1) * 4 + y;
  20.     int cc = (x - 1) * 4 + y + 1;
  21.     int dd = (x - 1 + 1) * 4 + y + 1;
  22.     if(x < 1 || x > 3 || y < 1 || y > 3)
  23.         return 0;
  24.     if(a[1] >= 7 || a[2] >= 7 || a[3] >= 7 || a[4] >= 7)
  25.         return 0;
  26.     if(((1 << aa) & DAY[t]) || ((1 << bb) & DAY[t]) || ((1 << cc) & DAY[t]) || ((1 << dd) & DAY[t]))
  27.         return 0;
  28.     if(mark[t][ys[aa]][a[1]][a[2]][a[3]][a[4]])
  29.         return 0;
  30.     return 1;
  31. }
  34. void DFS(int t,int x,int y,int a[])
  35. {
  36.     if(t == T)
  37.         OK = 1;
  38.     if(OK)
  39.         return ;
  40.     int b[5];
  41.     for(int i = 0 ; i < 9 ; i ++)
  42.     {
  43.         if(t == 0 && i)
  44.             break;
  45.         int nowt = t + 1;
  46.         int nowx = x + dir[i][0];
  47.         int nowy = y + dir[i][1];
  48.         for(int j = 1 ; j <= 4 ; j ++)
  49.             b[j] = a[j] + 1;
  50.         if(nowx == 1 && nowy == 1) b[1] = 0;
  51.         if(nowx == 1 && nowy == 3) b[2] = 0;
  52.         if(nowx == 3 && nowy == 1) b[3] = 0;
  53.         if(nowx == 3 && nowy == 3) b[4] = 0;
  54.         if(ok(nowt,nowx,nowy,b))
  55.         {
  56.             mark[nowt][ys[(nowx-1)*4+nowy]][b[1]][b[2]][b[3]][b[4]] = 1;
  57.             DFS(nowt,nowx,nowy,b);
  58.         }
  59.     }
  60.     return ;
  61. }
  64. int main ()
  65. {
  66.     int i,j;
  67.     while(cin >> T && T)
  68.     {
  69.         memset(DAY,0,sizeof(DAY));
  70.         for(i = 1 ; i <= T ; i ++)
  71.         {
  72.             int tmp;
  73.             for(j = 1 ; j <= 16 ; j ++)
  74.             {
  75.                 cin >> tmp;
  76.                 DAY[i] = DAY[i] | (tmp << j);
  77.             }
  78.         }
  79.         memset(mark,0,sizeof(mark));
  80.         OK = 0;
  81.         int a[5];
  82.         a[1] = a[2] = a[3] = a[4] = 0;
  83.         DFS(0,2,2,a);
  84.         cout << OK << endl;
  85.     }
  86.     return 0;
  87. }

E Holedox Moving （POJ 1324）
题目大意:

题目首先给出一张地图，地图中有一条蛇，蛇的长度为L，接下来L行，每行表示蛇身从头到尾的坐标。接下来有K行，每行也有一个坐标，表示地图中墙的位置。最后问蛇能否从当前位置移动到（1,1）这个位置（即蛇头到达（1,1）），蛇不能通过墙和自己的身体。

解题思路：

因为蛇身长度最大为8并且是连续的，那么，我们可以通过一个状态压缩，来表示每两个蛇身之间的相对应位置。每个相对位置占用两位，最多就7对，即14个相对位置，即可把所有情况表示完。所以，我们可以开一个三维数组，前两位表示蛇头的位置，第三位表示后面蛇身相对于他的前一个位置的方向，每两位表示一个方向。即vis[21][21][1<<14]即可表示出所有情况。接下来，我们就可以通过A*或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. int n,m,l,k,mp[25][25];
  10. int dir[3][3]= {-1,1,-1,3,-1,2,-1,0,-1};
  11. int D[4][2]= {1,0,-1,0,0,1,0,-1};
  12. bool vis[21][21][1<<14];
  14. struct Body
  15. {
  16.     int x[10],y[10];
  17.     int cnt;
  18. } body,bb;
  20. bool check(int a,int b,Body c)
  21. {
  22.     for(int i=2; i<=l; i++)
  23.     {
  24.         if(a==c.x[i]&&b==c.y[i])
  25.             return true;
  26.     }
  27.     return false;
  28. }
  30. int bfs()
  31. {
  32.     queue<Body>q;
  33.     body.cnt=0;
  34.     q.push(body);
  35.     while(!q.empty())
  36.     {
  37.         body=q.front();
  38.         q.pop();
  39.         if(body.x[1]==1&&body.y[1]==1)
  40.             return body.cnt;
  41.         for(int i=0; i<4; i++)
  42.         {
  43.             int x=body.x[1]+D[i][0],y=body.y[1]+D[i][1];
  44.             if(x<1||x>n||y<1||y>m||mp[x][y])
  45.                 continue;
  46.             if(check(x,y,body))
  47.                 continue;
  48.             body.x[0]=x;
  49.             body.y[0]=y;
  50.             int sta=0,tmp1,tmp2;
  51.             for(int j=l; j>=1; j--)
  52.             {
  53.                 bb.x[j]=body.x[j-1];
  54.                 bb.y[j]=body.y[j-1];
  55.                 if(j!=l)
  56.                 {
  57.                     tmp1=bb.x[j]-bb.x[j+1]+1;
  58.                     tmp2=bb.y[j]-bb.y[j+1]+1;
  59.                     int tmp=dir[tmp1][tmp2];
  60.                     tmp=(tmp<<(14-j*2));
  61.                     if(dir[tmp1][tmp2]!=-1) sta=(sta|tmp);
  62.                 }
  63.             }
  64.             if(vis[x][y][sta])
  65.                 continue;
  66.             vis[x][y][sta]=1;
  67.             bb.cnt=body.cnt+1;
  68.             q.push(bb);
  69.         }
  70.     }
  71.     return -1;
  72. }
  74. int main()
  75. {
  76.     int cas=0,x,y;
  77.     while(cin >> n >> m >> l&&n&&m&&l)
  78.     {
  79.         memset(mp,0,sizeof(mp));
  80.         memset(vis,0,sizeof(vis));
  81.         int sta=0;
  82.         scanf("%d%d",&body.x[1],&body.y[1]);
  83.         for(int i=2; i<=l; i++)
  84.         {
  85.             cin >> body.x[i] >> body.y[i];
  86.             x=body.x[i-1]-body.x[i]+1;
  87.             y=body.y[i-1]-body.y[i]+1;
  88.             int tmp=dir[x][y];
  89.             tmp=(tmp<<(14-(i-1)*2));
  90.             if(dir[x][y]!=-1)
  91.                 sta=(sta|tmp);
  92.         }
  93.         vis[body.x[1]][body.y[1]][sta]=1;
  94.         cin >> k;
  95.         for(int i=0; i<k; i++)
  96.         {
  97.             cin >> x >> y;
  98.             mp[x][y]=1;
  99.         }
  100.         cout << "Case " << ++cas << ": " << bfs() << endl;
  101.     }
  102.     return 0;
  103. }

F Quantum (POJ 2908)

题目大意：

题目第一行给出一个数字N，表示接下来有N组测试数据。对于每组测试数据，输入三个数L，nop，nw，表示要处理的二进制串的长度，操作种类数以及当前需要操作的二进制串的数量。最后，要求出对于给出的所有二进制串的花费的最小值。

解题思路：

我们看到这样的题，因为L是≤20的，那么，我们就可以将每个串转化为十进制进行存储。因为我们要得到的是消耗最小，我们可以通过BFS来枚举我们得到的每一种变换后的情况是怎么样的，再通过优先队列，并手写一个结构体来实现优先队列的排序，每次BFS之后把消耗最小的优先出队列。因为对于每个点，我们有多种到达的方法，我们在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. typedef long long ll;
  10. const int N=1<<22;
  11. const int INF=0x3f3f3f3f;
  13. int vis[N+5];
  14. char c[35][35];
  15. char c1[35],c2[35],c3[35];
  16. int a1[35],a2[35];
  17. int a[35];
  18. int l,n,m,ans;
  20. struct node
  21. {
  22.     char s[35];
  23.     int h;
  24.     bool operator<(const node &k) const
  25.     {
  26.         return h>k.h;
  27.     }
  28. };
  30. int vs(char k[])
  31. {
  32.     int s=0;
  33.     int i=0;
  34.     while(k[i++])
  35.         s=s*2+k[i-1]-'0';
  36.     return s;
  37. }
  39. void vc(char s1[],char s2[])
  40. {
  41.     for(int i=0;i<l;i++)
  42.     {
  43.         if(s2[i]=='N')
  44.             c3[i]=s1[i];
  45.         if(s2[i]=='F')
  46.         {
  47.             if(s1[i]=='0')
  48.                 c3[i]='1';
  49.             if(s1[i]=='1')
  50.                 c3[i]='0';
  51.         }
  52.         if(s2[i]=='S')
  53.             c3[i]='1';
  54.         if(s2[i]=='C')
  55.             c3[i]='0';
  56.     }
  57. }
  59. void bfs()
  60. {
  61.     memset(vis,0,sizeof(vis));
  62.     priority_queue<node> que;
  63.     node st;
  64.     strcpy(st.s,c1);
  65.     st.h=0;
  66.     que.push(st);
  67.     ans=INF;
  68.     node k1;
  69.     while(!que.empty())
  70.     {
  71.         node k=que.top();
  72.         que.pop();
  73.         if(vis[vs(k.s)]) 
  74.             continue;
  75.         if(strcmp(k.s,c2)==0)
  76.         {
  77.             ans=k.h;
  78.             break;
  79.         }
  80.         vis[vs(k.s)]=1;
  81.         for(int i=1;i<=n;i++)
  82.         {
  83.             vc(k.s,c[i]);
  84.             if(!vis[vs(c3)])
  85.             {
  86.                 strcpy(k1.s,c3);
  87.                 k1.h=k.h+a[i];
  88.                 que.push(k1);
  89.             }
  90.         }
  91.     }
  92. }
  94. int main()
  95. {
  96.     int T;
  97.     cin >> T;
  98.     while(T--)
  99.     {
  100.         cin >> l >> n >> m;
  101.         for(int i=1;i<=n;i++)
  102.             cin >> c[i] >> a[i];
  103.         for(int i=1;i<=m;i++)
  104.         {
  105.             memset(c3,0,sizeof(c3));
  106.             cin >> c1 >> c2;
  107.             bfs();
  108.             if(i!=1)
  109.                 cout << " ";
  110.             if(ans==INF)
  111.                 cout << "NP";
  112.             else
  113.                 cout << ans;
  114.         }
  115.         cout << endl;
  116.     }
  117. }

G Full Tank? (POJ 3635)
题目大意：

给出一张图，共有n个小镇和m条公路，小镇编号为0~n-1。然后给出每个小镇加每升油需要多少钱。接着一共m行，每行3个数，表示从小镇u到小镇v需要d升汽油。然后输入一个数q表示查询次数，每次查询输入三个数，分别表示汽车的油箱容量，起始小镇和最终要到达的小镇。问完成这些旅行至少需要花费多少钱。（一开始油箱为空）。若无法到达，则输出“impossible”。

解题思路：

我们可以设置一个数组dp[i][j]，表示到达点i时，还剩j升油的最小花费，那么，显然，dp[i][j]=min(dp[i][j],(edge(i,i')+(j-k))*price[i']+dp[i'][k]).然后每次都把得到的dp[i][j]的值放入一个优先队列中，每次从中间取出最小的那个进行计算更新。然后，就TLE了。为什么呢？因为我们这里每次计算的是加(edge(i,i')+(j-k))这么多升油，而在加这么多升油的过程中，我们可能会把许多比较劣的情况加到我们的优先队列里，使得后面我们计算了许多没必要的东西。那么怎么改呢？我们只需要改为每个点只枚举不加油直接走和只加一升油的情况就可以了，这样同样可以找遍所有的走法，但因为我们每次加的油比较少，就可以避免很多加X升油浪费掉这种比较劣的情况，极大的减少了每次的分支数量。

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=1005;
  10. const int MAXM=100005;
  11. const int INF=0x3f3f3f3f;
  13. struct Edge
  14. {
  15.     int v, w, next;
  16. }edge[MAXM];
  18. struct Node
  19. {
  20.     int v, cost, f;
  21.     bool operator <(const Node &a) const{
  22.         return a.cost < cost;
  23.     }
  24. };
  26. int head[MAXN], e, n, m, cap;
  27. int dp[MAXN][105], used[MAXN][105], p[MAXN];
  28. int s, t, T;
  29. priority_queue<Node>q;
  31. void init()
  32. {
  33.     memset(head, -1, sizeof(head));
  34.     e = 0;
  35. }
  37. void ready()
  38. {
  39.     for(int i = 0; i < n; i++)
  40.         for(int j = 0; j <= 100; j++)
  41.             dp[i][j] = INF;
  42.     dp[s][0] = 0;
  43.     memset(used, 0, sizeof(used));
  44.     while(!q.empty())
  45.         q.pop();
  46. }
  48. void insert(int x, int y, int w)
  49. {
  50.     edge[e].v = y;
  51.     edge[e].w = w;
  52.     edge[e].next = head[x];
  53.     head[x] = e++;
  54. }
  56. int bfs()
  57. {
  58.     Node a, b;
  59.     a.v = s, a.cost = 0, a.f = 0;
  60.     q.push(a);
  61.     while(!q.empty())
  62.     {
  63.         a = q.top();
  64.         q.pop();
  65.         int u = a.v;
  66.         int cost = a.cost;
  67.         int f = a.f;
  68.         used[u][f] = 1;
  69.         if(u == t)
  70.             return cost;
  71.         if(f + 1 <= cap && !used[u][f + 1] && dp[u][f + 1] > dp[u][f] + p[u])
  72.         {
  73.             dp[u][f + 1] = dp[u][f] + p[u];
  74.             b.v = u;
  75.             b.f = f + 1;
  76.             b.cost = dp[u][f + 1];
  77.             q.push(b);
  78.         }
  79.         for(int i = head[u]; i != -1; i = edge[i].next)
  80.         {
  81.             int v = edge[i].v;
  82.             int w = edge[i].w;
  83.             if(f >= w && !used[v][f - w] && dp[v][f - w] > cost)
  84.             {
  85.                 dp[v][f - w] = cost;
  86.                 b.v = v;
  87.                 b.f = f - w;
  88.                 b.cost = dp[v][f - w];
  89.                 q.push(b);
  90.             }
  91.         }
  92.     }
  93.     return -1;
  94. }
  95. int main()
  96. {
  97.     int x, y, w;
  98.     cin >> n >> m;
  99.     init();
  100.     for(int i = 0; i < n; i++)
  101.         cin >> p[i];
  102.     while(m--)
  103.     {
  104.         cin >> x >> y >> w;
  105.         insert(x, y, w);
  106.         insert(y, x, w);
  107.     }
  108.     cin >> T;
  109.     while(T--)
  110.     {
  111.         cin >> cap >> s >> t;
  112.         ready();
  113.         int ans = bfs();
  114.         if(ans != -1)
  115.             cout << ans << endl;
  116.         else
  117.             cout << "impossible" <<endl;
  118.     }
  119.     return 0;
  120. }

H Remainder (POJ 2426)

题目大意：

题目给出三个数n,k,m，每次对n进行一个操作，可以‘+’，‘-’，‘*’，‘%’m，然后使得到的数成为一个新的n。问最少需要多少次操作，才能使（最初始的n+1）%k=（当前n）%k。如果不存在，输出0，如果存在，输出最小次数并输出他们计算的符号顺序。如果存在多种顺序，按照'+'<'-'<'*'<'%'的顺序操作。

解题思路：

很显然，我们可以通过最初始的n，把这四种运算看做是四条边，每次BFS搜索这四种运算符即可。但是，我们发现，在我们进行运算的过程中，对同一个数取多次模运算是不会改变计算结果的，即，我们不管对m取多少次模，我们的答案是肯定不会变的，所以，'%'这个符号只会在我们的运算中出现一次。而又因为我们不管'+'或'-'多少个m，对于n%m的答案也是不会变的。（如果改变n的正负号是可以改变的，但m是正数，当n为正数时，最初始的n%k肯定为正，而负数模正数为负，肯定不会是我们需要的答案之一。）所以取模只会有两种情况，一开始就对n取模和n*m%m=0这两种。所以，对于我们的搜索就可以剪枝，减少大量搜索。

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <queue>
  7. using namespace std;
  8. const int maxn = 1e3+5;
  10. int n,k,m,big;
  11. char op_table[] = {'+','-','*','%'};
  12. char op[maxn];
  14. struct point
  15. {
  16.     int num;
  17.     int father;
  18.     char op_pre;
  19. } p[maxn];
  20. bool exist[maxn];
  22. void bfs()
  23. {
  24.     int father=0,child=1;
  25.     int dest = (n+1+big)%k;
  26.     p[0].num = (n+big)%k;
  27.     p[0].op_pre = 0;
  28.     bool finish_flag = false,repeat_flag = false;
  29.     memset(exist,0,sizeof(exist));
  30.     memset(op,0,sizeof(op));
  31.     exist[p[0].num] = true;
  32.     int tmp;
  33.     while(father<child && !finish_flag && !repeat_flag)
  34.     {
  35.         bool validflag=false;
  36.         for(int i=0; i<4; i++)
  37.         {
  38.             switch(op_table[i])
  39.             {
  40.             case '+':
  41.                 tmp = (p[father].num+m + big)%k;
  42.                 break;
  43.             case '-':
  44.                 tmp = (p[father].num-m + big)%k;
  45.                 break;
  46.             case '*':
  47.                 tmp = (p[father].num*m + big)%k;
  48.                 break;
  49.             case '%':
  50.                 if(father == 0 || (p[father].father == 0 && p[father].op_pre == '*') )
  51.                 {
  52.                     tmp = (father == 0) ? ((n%m+m)%m + big)%k : 0;
  53. //father==0的情况，输入值不能是p[0].num，必须是n，因为前者已经对k取模了，而%不符合交换率；另一种情况，就直接赋值为0就可以了
  54.                     break;
  55.                 }
  56.                 else
  57.                 {
  58.                     validflag = true;
  59.                 }
  60.             default:
  61.                 break;
  62.             }
  63.             if(validflag)//不符合两个条件的%操作符，就不需要考虑了
  64.                 continue;
  65.             if(!exist[tmp])
  66.             {
  67.                 exist[tmp] = true;
  68.                 p[child].num = tmp;
  69.                 p[child].father = father;
  70.                 p[child].op_pre = op_table[i];
  71.                 ++child;
  72.             }
  73.             if(tmp==dest)
  74.             {
  75.                 //output?
  76.                 finish_flag = true;
  77.                 break;
  78.             }
  79.         }
  80.         father++;
  81.     }
  82.     if(father == child)
  83.     {
  84.         cout << 0 << endl;
  85.     }
  86.     else if(finish_flag)
  87.     {
  88.         int x = child-1,count=0;
  89.         while(p[x].op_pre!=0)
  90.         {
  91.             op[count++] = p[x].op_pre;
  92.             x = p[x].father;
  93.         }
  94.         cout << count << endl;
  95.         for(int i=count-1; i>=0; --i)
  96.         {
  97.             cout << op[i];
  98.         }
  99.         cout << endl;
  100.     }
  101. }
  103. int main()
  104. {
  105.     while(cin >> n >> k >> m)
  106.     {
  107.         if(n==0 && k==0 && m==0)
  108.         {
  109.             break;
  110.         }
  111.         big = k<<20;
  112.         bfs();
  113.     }
  114.     return 0;
  115. }

I The Buses （POJ 1167）

题目大意：

题目给出某一车站12点到12点59分时所有公交车停靠这个公交车站的时间表，题目保证每一条公交线路的公交车到达车站的时间间隔是相同的，且最少每条公交线路有2辆车经过，最多有17条公交线路。问最少有可能有多少条公交线路。

解题思路:

我们可以根据题目预处理出所有的公交车线路，在通过DFS，看选择哪几条线路能恰好是数据中所有的数据刚好使用一次切选择的线路最少。由于每一条公交线路最少有2辆车经过，那么，只有前0~29分钟到车站的车才有可能是始发车。我们对所有的公交车线路按照停靠次数从大到小的顺序进行排序，当 当前已选的线路 加上 剩余没有安排的车辆除以当前路线需要的车 （即估计需要的线路数）比已经得到的答案大的，直接剪枝。

AC代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <queue>
  7. using namespace std;
  9. int ct[60];//ct[i]表示第i分钟到达的车数
  10. int n,ans,tp;//车数 答案 总备选线路数
  12. struct node
  13. {
  14.     int s;//第一次到达时间
  15.     int j;//发车间隔
  16.     int t;//需要车数
  17. } p[301];
  19. int cmp(node a,node b)
  20. {
  21.     return a.t>b.t;
  22. }
  24. bool test(int s,int ti) //s_起始时间 ti_间隔时间
  25. {
  26.     for(int i=s; i<60; i+=ti)
  27.         if(!ct[i])
  28.             return false;
  29.     return true;
  30. }
  32. void dfs(int t,int now)
  33. {
  34.     int i,tmp;
  35.     if(n==0)
  36.     {
  37.         if(now<ans)
  38.             ans=now;
  39.         return;
  40.     }
  41.     for(i=t; i<=tp && p[i].t>n; i++); //寻找合适线路，排除需要车数比剩余车数大的线路
  42.     for(int k=i; k<=tp; k++)
  43.     {
  44.         if(now+n/p[k].t>=ans)
  45.             return;//剪枝
  46.         if(test(p[k].s,p[k].j))
  47.         {
  48.             tmp=p[k].j;
  49.             for(int j=p[k].s; j<60; j+=tmp)
  50.             {
  51.                 ct[j]--;
  52.                 n--;
  53.             }
  54.             dfs(k,now+1);
  55.             for(int j=p[k].s; j<60; j+=tmp)
  56.             {
  57.                 ct[j]++;
  58.                 n++;
  59.             }
  60.         }
  61.     }
  62. }
  64. int main()
  65. {
  66.     scanf("%d",&n);
  67.     int a;
  68.     for(int i=1; i<=n; i++)
  69.     {
  70.         scanf("%d",&a);
  71.         ct[a]++;
  72.     }
  73.     tp=0;
  74.     for(int i=0; i<=29; i++)
  75.     {
  76.         if(!ct[i])
  77.             continue;
  78.         for(int j=i+1; j<=59-i; j++)
  79.         {
  80.             if(test(i,j))
  81.             {
  82.                 tp++;
  83.                 p[tp].s=i;
  84.                 p[tp].j=j;
  85.                 p[tp].t=1+(59-i)/j;
  86.             }
  87.         }
  88.     }
  89.     sort(p+1,p+tp+1,cmp);
  90.     ans=17;
  91.     dfs(1,0);
  92.     printf("%d",ans);
  93.     return 0;
  94. }

J Sudoku (POJ 2676)

题目大意：

题目给出多组数据，每组数据给出一个9*9的数独格子，题目要你将这个数独全部填完。（即把0全部填完）

解题思路：

我们可以开三个二维数组，row[i][x]表示在第i行数字x是否出现，col[i][x]表示在第i列数字x是否出现，grid[i][x]表示 在第i个3*3的格子内数字x是否出现。对于如何判断哪个位置在第i个3*3的格子内，可以通过图形式子进行推断。最后，直接暴力DFS即可。

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <queue>
  7. using namespace std;
  9. int mp[10][10];
  11. bool row[10][10];    //row[i][x]  标记在第i行中数字x是否出现了
  12. bool col[10][10];    //col[j][y]  标记在第j列中数字y是否出现了
  13. bool grid[10][10];   //grid[k][x] 标记在第k个3*3子格中数字z是否出现了
  15. bool DFS(int x,int y)
  16. {
  17.     if(x==10)
  18.         return true;
  19.     bool flag=false;
  20.     if(mp[x][y])
  21.     {
  22.         if(y==9)
  23.             flag=DFS(x+1,1);
  24.         else
  25.             flag=DFS(x,y+1);
  26.         if(flag)  //回溯
  27.             return true;
  28.         else
  29.             return false;
  30.     }
  31.     else
  32.     {
  33.         int k=3*((x-1)/3)+(y-1)/3+1;
  34.         for(int i=1; i<=9; i++) //枚举数字1~9填空
  35.             if(!row[x][i] && !col[y][i] && !grid[k][i])
  36.             {
  37.                 mp[x][y]=i;
  38.                 row[x][i]=true;
  39.                 col[y][i]=true;
  40.                 grid[k][i]=true;
  41.                 if(y==9)
  42.                     flag=DFS(x+1,1);
  43.                 else
  44.                     flag=DFS(x,y+1);
  45.                 if(!flag)   //回溯，继续枚举
  46.                 {
  47.                     mp[x][y]=0;
  48.                     row[x][i]=false;
  49.                     col[y][i]=false;
  50.                     grid[k][i]=false;
  51.                 }
  52.                 else
  53.                     return true;
  54.             }
  55.     }
  56.     return false;
  57. }
  59. int main(int i,int j)
  60. {
  61.     int test;
  62.     cin>>test;
  63.     while(test--)
  64.     {
  65.         memset(row,false,sizeof(row));
  66.         memset(col,false,sizeof(col));
  67.         memset(grid,false,sizeof(grid));
  68.         char MAP[10][10];
  69.         for(i=1; i<=9; i++)
  70.             for(j=1; j<=9; j++)
  71.             {
  72.                 cin>>MAP[i][j];
  73.                 mp[i][j]=MAP[i][j]-'0';
  75.                 if(mp[i][j])
  76.                 {
  77.                     int k=3*((i-1)/3)+(j-1)/3+1;
  78.                     row[i][ mp[i][j] ]=true;
  79.                     col[j][ mp[i][j] ]=true;
  80.                     grid[k][ mp[i][j] ]=true;
  81.                 }
  82.             }
  83.         DFS(1,1);
  84.         for(i=1; i<=9; i++)
  85.         {
  86.             for(j=1; j<=9; j++)
  87.                 cout<<mp[i][j];
  88.             cout<<endl;
  89.         }
  90.     }
  91.     return 0;
  92. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注