//: PORTER.H - PORTER HEADER - 2006.2 rickone#include<iostream.h>#ifndef _PORTER_HEADERFILE#define _PORTER_HEADERFILEclass 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 dirconst 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表似乎也需要改进，后面的任务是如何剪枝，今后补上。

评论