mg.cpp

迷宫问题与运动会,有丰富的实例与测试数据

#include<stdlib.h>
#include<iostream.h>
#include"o.h"
#include"mg.h"

void zou::Initzou(int x,int y,int zz)
{
 int i(0),j(0);
 for(i=0;i<x;i++)
  for(j=0;j<y;j++)
  {
   m[i][j].tbt=0;
   m[i][j].mx=i;
   m[i][j].my=j;
   m[i][j].lks=0;
   m[i][j].tgcs=0;
  }
 for(i=1;i<x-1;i++)
  for(j=1;j<y-1;j++)
  {
   if(rand()%zz!=0)//根据随机数能不能被zz整除来生成障碍
     m[i][j].tbt=1;
   else
    m[i][j].tbt=0;
  }
  m[1][1].tbt=4;
  m[i-1][j-1].tbt=3;
  for(i=0;i<x;i++)
 {
  cout<<endl;
  for(j=0;j<y;j++)
   cout<<m[i][j].tbt<<" ";
 }
 cout<<endl<<endl;
  xianz=m[i-2][j-2];
  ganglk=m[i-2][j-2];
  m[i-2][j-2].tbt=1;
}
bool zou::ifgoon(zou& Z)
{
 int x(0),y(0),xx(0),yy(0);
 x=Z.xianz.mx;
 y=Z.xianz.my;
 xx=Z.ganglk.mx;
 yy=Z.ganglk.my;
 int temp(0);
 temp=Z.m[xx][yy].tbt;
 Z.m[xx][yy].tbt=0;
 file://如果现在的位置的四个方向不可以通过或者找到终点
 if(Z.m[x][y+1].tbt==0&&Z.m[x][y-1].tbt==0&&Z.m[x+1][y].tbt==0&&Z.m[x-1][y].tbt==0||Z.m[x][y].tbt==4)
 {
  Z.m[xx][yy].tbt=temp;
  return false;
 }
 else
 {
  Z.m[xx][yy].tbt=temp;
  return true;
 }
 
}
void zou::xingzou(zou& Z)
{
 int fangx(4);
 int jg1=Z.xianz.my-Z.ganglk.my;
 int jg2=Z.xianz.mx-Z.ganglk.mx;
 if(jg1<0&&jg2==0)
 {
  fangx=0;//现在来时的左边
 }
 else if(jg1>0&&jg2==0)
 {
  fangx=1;//在右边
 }
 else if(jg1==0&&jg2<0)
 {
  fangx=2;//在上边
 }
 else if(jg1==0&&jg2>0)
 {
  fangx=3;//在下边
 }
 else if(jg1==0&&jg2==0)
 {
  fangx=4;//在原处
 }
 else 
  cout<<"ifgoon() has problem!"<<endl;

 switch(fangx) {
 case 0:
  if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往上走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go north"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
  {//往左走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go west"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx+1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx+1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往下走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx+1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go south"<<endl;   
   return;
  }
  else
   {
  xianz.tbt=4;
  cout<<"sir,no way for search anymore!!"<<endl;
  }

  break;
 case 1:
  if(Z.m[Z.xianz.mx+1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx+1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往下走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx+1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go south"<<endl;   
   return;
  }
  else if(Z.m[Z.xianz.mx][Z.xianz.my+1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my+1].tgcs<Z.getlukoushu())
  {//往右走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my+1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go east"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往上走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go north"<<endl;
   return;
  }
  else
   {
  xianz.tbt=4;
  cout<<"sir,no way for search anymore!!"<<endl;
  }
  break;
 case 2:
  if(Z.m[Z.xianz.mx][Z.xianz.my+1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my+1].tgcs<Z.getlukoushu())
  {//往右走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my+1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go east"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往上走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go north"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
  {//往左走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go west"<<endl;
   return;
  }
  else
   {
  xianz.tbt=4;
  cout<<"sir,no way for search anymore!!"<<endl;
  }
  break;
 case 3:
  if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
  {//往左走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go west"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx+1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx+1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往下走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx+1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go south"<<endl;   
   return;
  }
  else if(Z.m[Z.xianz.mx][Z.xianz.my+1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my+1].tgcs<Z.getlukoushu())
  {//往右走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my+1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go east"<<endl;
   return;
  }
  else
   {
  xianz.tbt=4;
  cout<<"sir,no way for search anymore!!"<<endl;
  }
  break;
 case 4:
  if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
  {//往上走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go north"<<endl;
   return;
  }
  else if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
  {//往左走
   Z.ganglk=Z.xianz;
   Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
   Z.xianz.tgcs=Z.xianz.tgcs+1;
   cout<<"yes,sir,i go west"<<endl;
   return;
  }
  else
   {
  xianz.tbt=4;
  cout<<"sir,no way for search anymore!!"<<endl;
  }
  break;
 default:
  {
   xianz.tbt=4;
  cout<<"sir,no way for search anymore!!"<<endl;
  return;
  }
 }
}
void zou::houtui()
{
 Mg M;
 int x(0),y(0),xx(0),yy(0);
 x=xianz.mx;
 y=xianz.my;
 xx=ganglk.mx;
 yy=ganglk.my;
 int temp(0);
 temp=m[xx][yy].tbt;
 m[xx][yy].tbt=0;
 if(m[x][y+1].tbt==0&&m[x][y-1].tbt==0&&m[x+1][y].tbt==0&&m[x-1][y].tbt==0&&ganglk.tgcs<2)
 {
  M=xianz;
 xianz=ganglk;
 ganglk=M;
 xianz.tgcs=xianz.tgcs+1;
 m[xx][yy].tbt=temp;
 cout<<"sir,i go back"<<endl;
 }
 else
 {
  xianz.tbt=4;
  m[xx][yy].tbt=temp;
  cout<<"sir,no way for search anymore!!"<<endl;
 }
}
int zou::getlukoushu()
{
 int e(0),s(0),w(0),n(0);
 if(m[xianz.mx][xianz.my+1].tbt==1)
  e=1;
 else
  e=0;
 if(m[xianz.mx][xianz.my-1].tbt==1)
  w=1;
 else
  w=0;
 if(m[xianz.mx-1][xianz.my].tbt==1)
  n=1;
 else
  n=0;
 if(m[xianz.mx+1][xianz.my].tbt==1)
  s=1;
 else
  s=0;
 return e+w+n+s;
}