正文

[代码]搬运工12006-02-08 18:25:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/rickone/10022.html

分享到：

//: PORTER.H - PORTER HEADER - 2006.2 rickone
#include<iostream.h>
#ifndef _PORTER_HEADERFILE
#define _PORTER_HEADERFILE
class PorterMap
{
 int width,height;
 int *data;/* map data means :
     0 - empty place
     1 - goal place without box
     2 - box on empty place
     3 - box on goal place
     4 - wall
     0,1 r reachable
     2,3,4 r unreachable
     */
 int px,py;//porter place
 int *reach;//mark the place where the porter now can reach
 int boxnumber;
 void dfsreach(int,int);
 void reachmap(int,int);
public:
 PorterMap(istream&);/*map data loaded from std input stream & its format(ascii) :
      first line two integers for width & height -
      W H
      following H lines are the datas,each line should be W integers -
      ... W ...
      ...
      H
      ...
      and the last line include two integers which means
      the porter place(x,y) when begin:
      PX PY
      */
      
 ~PorterMap();
 //int getMapData(int x,int y){return data[y*width+x];};
 //void getPorterPlace(int& ptx,int& pty){ptx=px;pty=py;};
 int nextbox(int&,int&);
 int pushbox(int bx,int by,int dir/*directions :
                                0,1,2,3 for left,right,up & down
           */);
 bool canReach(int rx,int ry){return reach[ry*width+rx]==1;};//place if the porter can reach
 void display(ostream&);
//friend:
 friend class State;
 friend class StatesList;
};

class State
{
 int boxnumber;
 struct Pos
 {
  int x,y;
 }*data/*boxs position*/,porter/*porter position & the most left the most up*/;
 unsigned int sign;
 State *parent;
public:
 State(PorterMap&);
 ~State();
 //int evaluate();
 int drawmap(PorterMap&);//draw the map & return the state is well done
 void cleanmap(PorterMap&);
 void setparent(State *pa){parent=pa;};
//friend:
 friend bool operator==(State&,State&);
 friend class StatesList;
};

struct HashNode//hash list node
{
 State *link;
 HashNode *next;
};

class StatesList
{
 HashNode **nodes;
public:
 StatesList();
 ~StatesList();
 bool exist(State&);
 void push(State*);
};
const int c_dx[8]={-1,1,0,0,1,-1,0,0};
const int c_dy[8]={0,0,-1,1,0,0,1,-1};//last 4 are opposite dir
const unsigned int nodenumber=167777;
#endif

//:PORTER.CPP
#include "porter.h"
#define legal(X,Y) (X>=0&&X<width&&Y>=0&&Y<height)

PorterMap::PorterMap(istream &in)
{
 in>>width>>height;
 data=new int[width*height];
 reach=new int[width*height];
 boxnumber=0;
 for(int h=0;h<height;++h)
  for(int w=0;w<width;++w)
  {
   int temp;
   in>>temp;
   data[h*width+w]=temp;
   if(temp==2||temp==3)++boxnumber;
  }
 in>>px>>py;
 if(legal(px,py)&&data[py*width+px]<2)
  reachmap(px,py);
 /*
 else
  cerr<<"Error Porter Place!"<<endl;
 */

}
void PorterMap::dfsreach(int x,int y)
{
 reach[y*width+x]=1;
 for(int i=0;i<4;++i)
 {
  int tx=x+c_dx[i],ty=y+c_dy[i];
  if(legal(tx,ty)&&data[ty*width+tx]<2&&reach[ty*width+tx]==0)
   dfsreach(tx,ty);
 }
}
void PorterMap::reachmap(int x,int y)
{
 for(int h=0;h<height;++h)
  for(int w=0;w<width;++w)
   reach[h*width+w]=0;
 dfsreach(x,y);
}
void PorterMap::display(ostream &out)
{
 static char MapGraph[]="　※□■★";
 out<<"Porter Map:"<<endl;
 for(int h=0;h<height;++h)
 {
  for(int w=0;w<width;++w)
  {
   int temp=data[h*width+w];
   out<<MapGraph[temp*2]<<MapGraph[temp*2+1];
  }
  out<<endl;
 }
 /*
 out<<"Porter Place:("<<px<<","<<py<<")"<<endl;
 out<<"Box Number:"<<boxnumber<<endl;
 out<<"Porter can reach:"<<endl;
 for(int hh=0;hh<height;++hh)
 {
  for(int ww=0;ww<width;++ww)
   if(reach[hh*width+ww]==1)out<<"◆";
   else out<<"◇";
  out<<endl;
 }
 */
}
int PorterMap::nextbox(int &bx,int &by)
{
 int bottom=width*height,index=by*width+bx+1;
 while(index<bottom)
 {
  if(data[index]==2||data[index]==3)break;
  ++index;
 }
 if(index==bottom)return 0;
 bx=index%width;
 by=index/width;
 return 1;
}
int PorterMap::pushbox(int bx,int by,int dir)
{
 int gx=bx+c_dx[dir],gy=by+c_dy[dir];//goal place
 int sx=bx+c_dx[(dir+4)%8],sy=by+c_dy[(dir+4)%8];

 if(dir<4&&(data[gy*width+gx]>1||reach[sy*width+sx]==0))return 0;
 data[by*width+bx]-=2;
 data[gy*width+gx]+=2;
 return 1;
}
PorterMap::~PorterMap()
{
 delete[] data;
 delete[] reach;
}

//---

State::State(PorterMap &map)
{
 boxnumber=map.boxnumber;
 data=new Pos[boxnumber];
 int box_index=0,tag=1;
 for(int h=0;h<map.height;++h)
  for(int w=0;w<map.width;++w)
  {
   if(map.data[h*map.width+w]==2||map.data[h*map.width+w]==3)
   {
    data[box_index].x=w;
    data[box_index].y=h;
    ++box_index;
   }
   if(tag&&map.reach[h*map.width+w]==1)
   {
    tag=0;
    porter.x=w;
    porter.y=h;
   }
  }
 unsigned int tempa=1,tempb=1;
 for(int i=0;i<boxnumber;++i)
 {
  tempa*=data[i].x;
  tempb*=data[i].y;
 }
 sign=tempa+tempb;
 //cout<<"ID:"<<sign<<" State is created."<<endl;
}
int State::drawmap(PorterMap &map)
{
 int tag=1;
 for(int i=0;i<boxnumber;++i)
 {
  int tx=data[i].x,ty=data[i].y;
  if((map.data[ty*map.width+tx]+=2)!=3)tag=0;;
 }
 map.px=porter.x;
 map.py=porter.y;
 map.reachmap(porter.x,porter.y);
 return tag;
}
void State::cleanmap(PorterMap &map)
{
 for(int i=0;i<boxnumber;++i)
 {
  int tx=data[i].x,ty=data[i].y;
  map.data[ty*map.width+tx]-=2;
 }
}
bool operator==(State &a,State &b)
{
 //if(a.boxnumber!=b.boxnumber)return false;
 if(a.sign!=b.sign)return false;
 for(int i=0;i<a.boxnumber;++i)
  if(a.data[i].x!=b.data[i].x||a.data[i].y!=b.data[i].y)return false;
 return true;
}
State::~State()
{
 delete[] data;
}

//---

StatesList::StatesList()
{
 nodes=new HashNode*[nodenumber];
 for(int i=0;i<nodenumber;++i)
  nodes[i]=NULL;
}
bool StatesList::exist(State &st)
{
 int index=st.sign%nodenumber;
 if(nodes[index]==NULL)return false;
 for(HashNode *p=nodes[index];p!=NULL;p=p->next)
  if(*(p->link)==st)return true;
 return false;
}
void StatesList::push(State *st)
{
 int index=st->sign%nodenumber;
 //cout<<"StatesList get a new state,Store Index:"<<index<<" State ID:"<<st->sign<<endl;
 if(nodes[index]==NULL)
 {
  nodes[index]=new HashNode;
  nodes[index]->link=st;
  nodes[index]->next=NULL;
  return;
 }
 for(HashNode *p=nodes[index];p->next!=NULL;p=p->next);
 HashNode *q=new HashNode;
 q->link=st;
 q->next=NULL;
 p->next=q;
}
StatesList::~StatesList()
{
 for(int i=0;i<nodenumber;++i)
 {
  if(nodes[i]==NULL)continue;
  for(HashNode *p=nodes[i];p!=NULL;)
  {
   HashNode *q=p->next;
   delete p->link;
   delete p;
   p=q;
  }
 }
 delete[] nodes;
}

//:TESTFILE.CPP
#include "porter.h"

class queue
{
 struct que_node
 {
  void *link;
  que_node *next;
  que_node(void* data){link=data;next=NULL;};
  que_node(){link=next=NULL;};
 }*head,*tail;
 int length;
public:
 queue();
 ~queue();
 bool empty(){return length==0;};
 void enqueue(void*);
 void* dequeue();
};
queue::queue()
{
 head=tail=NULL;
 length=0;
}
queue::~queue()
{
 que_node *p=head,*q;
 while(p)
 {
  q=p->next;
  delete p;
  p=q;
 }
}
void queue::enqueue(void *data)
{
 que_node *p=new que_node(data);
 if(head==NULL)
 {
  head=tail=p;
 }
 else
 {
  tail->next=p;
  tail=p;
 }
 ++length;
}
void* queue::dequeue()
{
 if(length==0)return NULL;
 que_node *p=head;
 void *q=head->link;
 head=p->next;
 delete p;
 return q;
}
void main()
{
 PorterMap map(cin);
 State *s_now=new State(map);
 StatesList slist;
 queue que;
 que.enqueue((void*)s_now);
 s_now->setparent(NULL);//roots
 s_now->cleanmap(map);
 while(!que.empty())
 {
  s_now=(State*)que.dequeue();
  if(s_now->drawmap(map))break;
  map.display(cout);
  slist.push(s_now);
  int x=0,y=0;
  for(;map.nextbox(x,y);)
  {
   for(int dir=0;dir<4;++dir)
   {
    if(map.pushbox(x,y,dir))
    {
     State *p=new State(map);
     if(slist.exist(*p))
      delete p;
     else
     {
      que.enqueue((void*)p);
      p->setparent(s_now);//set it's parent node
     }
     map.pushbox(x+c_dx[dir],y+c_dy[dir],dir+4);
     //map.display(cout);
    }
   }
  }
  s_now->cleanmap(map);
 }
}

算是把框架完成了，现在还不能解决什么问题，海量的搜索当然解决不了什么问题，还有那个hash表似乎也需要改进，后面的任务是如何剪枝，今后补上。

阅读(6446) | 评论(4)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

loading...
您需要登录后才能评论，请 登录 或者 注册