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

题目：

在一个网格w*h(w,h<=16)中有n个小写字母（代表鬼），要求它们分别移动到对应的大写字母里，每步可以有多个鬼同时移动，但每步结束后任意两个鬼不能占同一个位置，也不能在一步之内交换位置。

思路：

这题目如果纯暴力搜的话会超时，因为每步都有5^3种情况。

题目中有个条件是任何一个2*2的子网格中至少有一个障碍物，所以我们可以先建个图，将图中每个点能走的点建成边，这样搜索的时候会节省很多时间。

搜索的时候可以用双向bfs进行搜索，即从起点和终点分别开始搜索。

记录每个边状态的时候可以用hash的方法记录，因为不加障碍物一共二百个点，用hash的话只需要二进制24位就行。

代码如下：

代码是参考着别人写的，写的时候一脸蒙蔽。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int maxn=205;int w,h,n;char a[20][20];int pos[5][2]={
  {0,0},{1,0},{-1,0},{0,1},{0,-1}};int s[5],e[5];int deg[maxn];int edge[maxn][maxn];int vis[maxn][maxn][maxn];int step[maxn][maxn][maxn];//hashint change(int a,int b,int c){    return (a<<16)|(b<<8)|c;}//判断是否冲突bool isSame(int a1,int b1,int a2,int b2){    return ((a2==b2)||(a1==b2&&b1==a2));}int bfs (){    queue
        
         q[2]; vis[s[0]][s[1]][s[2]]=1; vis[e[0]][e[1]][e[2]]=2; step[s[0]][s[1]][s[2]]=0; step[e[0]][e[1]][e[2]]=1; q[0].push(change(s[0],s[1],s[2])); q[1].push(change(e[0],e[1],e[2])); while(!q[0].empty()||!q[1].empty()) { int Size1=q[0].size(),Size2=q[1].size(); while(Size1--) { int now=q[0].front(); q[0].pop(); //解码 int a=(now>>16)&0xff,b=(now>>8)&0xff,c=now&0xff; for (int i=0;i
         
          >16)&0xff,b=(now>>8)&0xff,c=now&0xff; for (int i=0;i
         
        
       
      
     
    
   

转载地址：http://lwoen.baihongyu.com/