这道题目是这个学期一个作业，分享一下我的解法

题目描述：

突出重围（IQ Car）是一款儿童益智类游戏，其具体游戏规则为：

1. 先将大小车按图册上的位置摆好
2. 每局摆好后,你需要将挡住红车的其他车移开,令红车推出缺口
3. 这样为一局过关,所有的车只能前进后退,不能横行或拿起

图2.2 IQ Car游戏示例
请设计一个算法，在给定的车子的初始状态下，帮助小红车突出重围。另外，如何判定红车是否能够冲出突围？
以下是初始布局，可以根据布局测试程序：

讯享网
在4399小游戏中搜索“汽车华容道”能够找到这个游戏，可以去玩一下。

我是用bfs做的，由于时间仓促，有些地方设置的不合理，没来得及进行优化，但是运行的结果好像还可以，在代码最后面附上了两个测试样例，可以试一试。

c++代码：

//汽车华容道 #include<bits/stdc++.h> using namespace std; #define SUM 10  typedef struct node{ 
   //汽车地图的结构体  int a[6][6]; //当前地图信息  int n; //汽车数量 int d[SUM]; //记录每辆车可以行使的方向，假设最多有SUM辆车  int nomove; //记录不能移动的车，即当前状态有移动此车得到的 struct node *next; struct node *pre; }*Car,IQCar; Car end=NULL; //用来记录当前链表的结尾  void init(Car car){ 
    //地图初始化  int i,j; for(i=0;i<6;i++) for(j=0;j<6;j++) car->a[i][j]=0; } bool judge(Car car){ 
   //判断新得到的节点是否可以直接结束  // printf("judging...\n"); for(int i=5;i>=0;i--){ 
   //从出口位置向里进行判断  if(car->a[2][i]==0) continue; if(car->a[2][i]==1) { 
    // printf("now is %d\n",car->a[2][i]); return true; } else return false; } } bool repeat(Car begin,Car car){ 
   //如果要把节点加入到队列中必须保证，和之前的任何节点都没有重复的  Car p=begin; //printf("repeating...\n"); while(p!=NULL){ 
    int flag=0; for(int i=0;i<6;i++){ 
    for(int j=0;j<6;j++){ 
    if(p->a[i][j]!=car->a[i][j]) { 
    flag=1; break; } } if(flag==1)break; } if(flag==0)return false; p=p->next; } return true; } void f(Car begin,int x1,int y1,int x2,int y2,int n){ 
   //向地图中加入汽车  int i,j; if(x1==x2){ 
   //车辆是横向的  for(i=y1;i<=y2;i++) begin->a[x1][i]=n; begin->d[n]=1; //记录车的方向是横向的  } else{ 
   //车辆是纵向的  for(i=x1;i<=x2;i++) begin->a[i][y1]=n; begin->d[n]=0; //记录车的方向是纵向的  } } void canmove(Car car,int n,int &one,int &two,int &x,int &y){ 
   //one 和 two 代表两个方向可以移动的最大距离 int i,j; int flag=0; one=two=0; // printf("n==%d\n",n); // printf("car.d[n]==%d\n",car->d[n]); for(i=0;i<6;i++){ 
    for(j=0;j<6;j++){ 
    if(car->a[i][j]==n){ 
   //说明找到这辆车了  flag=1; x=i; y=j; break; } } if(flag==1)break; } if(car->d[n]==1){ 
   //如果车是横向的  int jj=j; jj--; //printf("jj=%d\n",jj); while(jj>=0){ 
    if(car->a[i][jj]==0)one++;//表示左侧空间加一 else break;//遇到不是0的位置就直接退出  jj--; } while(j<6){ 
    if(car->a[i][j]==n){ 
    j++; continue; } if(car->a[i][j]==0)two++; else break;//遇到其它车辆就直接退出  j++; } } else{ 
   //如果车是纵向的  int ii=i; ii--; while(ii>=0){ 
    if(car->a[ii][j]==0)one++; //上方空闲位置加一 else break; ii--; } while(i<6){ 
    if(car->a[i][j]==n){ 
    i++; continue; } if(car->a[i][j]==0)two++;//下方空闲位置加一 else break; i++; } }//else } void Create(Car parent,Car &son,int n,int l,int d,int x,int y){ 
    //创建一个新的节点  //n表示车的编号，l表示移动距离，d表示移动方向，x,y车的坐标  son=(Car)malloc(sizeof(IQCar)); son->next=NULL; son->nomove=n; son->n=parent->n; for(int i=0;i<SUM;i++) son->d[i]=parent->d[i];//复制车辆方向  //复制地图  for(int i=0;i<6;i++) for(int j=0;j<6;j++) son->a[i][j]=parent->a[i][j]; if(parent->d[n]==1){ 
   //要移动的车是横向的  if(d==1){ 
   //向左移动  int j=y; int jj=y-1; while(j<6){ 
    if(son->a[x][j]==n) j++; else break; }//得到车辆最右侧的坐标  j--; while(l--){ 
    swap(son->a[x][jj],son->a[x][j]); jj--; j--; } } else{ 
   //向右移动  int j=y; int jj=j; while(jj<6){ 
    if(son->a[x][jj]==n) jj++; else break; } while(l--){ 
    swap(son->a[x][j],son->a[x][jj]); j++; jj++; } } } else{ 
   //要移动的车是纵向的  if(d==1){ 
   //向上移动  int i=x; int ii=x-1; while(i<6){ 
    if(son->a[i][y]==n) i++; else break; } i--; while(l--){ 
    swap(son->a[ii][y],son->a[i][y]); ii--; i--; } } else{ 
   //向下移动  int i=x; int ii=x; while(ii<6){ 
    if(son->a[ii][y]==n) ii++; else break; } while(l--){ 
    swap(son->a[ii][y],son->a[i][y]); i++; ii++; } } } } void bfs(Car begin){ 
    //用分支限界法搜索答案  if(judge(end))return; Car left=begin,p; int i; int one,two; int x,y;//同时求出第i辆汽车的开始坐标  while(left!=NULL){ 
    for(i=1;i<=left->n;i++){ 
   //依次  if(i==left->nomove) continue; //这辆车不能移动  canmove(left,i,one,two,x,y); // if(i==1) // printf("one=%d, two=%d\n",one,two); //printf("x=%d, y=%d\n",x,y); while(one>0){ 
    //第一个方向上移动这辆车  Create(left,p,i,one,1,x,y);//创建一个子节点 ,1表示想左或上移动  if(repeat(begin,p)){ 
   //如果不重复  p->pre=left; end->next=p; end = p; // if(i==2)printf("one=%d\n",one); if(judge(end))return; } else free(p);//如果重复  one--; } while(two>0){ 
    //第二个方向上移动这辆车  Create(left,p,i,two,2,x,y); if(repeat(begin,p)){ 
   //不重复返回true  p->pre=left; end->next=p; end = p; if(judge(end))return; } else free(p); two--; } }//for  left=left->next; }//while  } void Printanswer(Car car){ 
    //构造答案输出结果  if(car->pre==NULL){ 
    printf("初始状态：\n"); for(int i=0;i<6;i++){ 
    for(int j=0;j<6;j++) printf("%d ",car->a[i][j]); printf("\n"); } } else{ 
    Printanswer(car->pre); printf("中间状态：\n"); for(int i=0;i<6;i++){ 
    for(int j=0;j<6;j++) printf("%d ",car->a[i][j]); printf("\n"); } } } void Destroy(Car begin){ 
    //销毁链表  Car p=begin,q=begin; p=p->next; while(p!=NULL){ 
    free(q); q=p; p=p->next; } free(q); } int main(){ 
    Car begin; begin=(Car)malloc(sizeof(IQCar)); //创建头节点 init(begin); int n; int x1,y1,x2,y2; //输入初始状态 //{  printf("输入目标车的位置，起始位置坐标："); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); //目标车的长度为2  begin->a[x1][y1]=1; begin->a[x2][y2]=1; if(x1!=2||x2!=2) printf("*横坐标输入不合法*\n\n"); //错误提示  //===============================================================================  printf("输入其它车辆的个数："); scanf("%d",&n); begin->n=n+1; //================================================================================ printf("依次输入他们的位置，起始位置坐标：\n"); int x=1; for(int i=0;i<n;i++){ 
    x++; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); f(begin,x1,y1,x2,y2,x); } //================================================================================= //其它设置  begin->d[1]=1; begin->nomove=-1; begin->next=NULL; begin->pre=NULL; end=begin; //此时的开始和结尾指向同一位置，初始状态 //} //利用分支限界法搜索结果 bfs(begin); printf("bfs end ...\n"); //构造最优解并输出 Printanswer(end); printf("\n此时可以将目标车(1号车)向右驶出,结束\n"); //销毁链表 Destroy(begin); return 0; } /*测试样例1 2 0 2 1 7 0 0 0 2 2 2 3 2 4 2 5 2 3 3 4 3 5 3 5 5 3 4 3 5 0 5 2 5 */ /* 测试样例2 2 0 2 1 3 3 0 5 0 3 1 3 3 0 3 2 3 */