1249.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<vector>
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int p[4][2]={1,0,0,1,-1,0,0,-1};
class point{
public:
	int x,y;
	point(){}
	point(int a,int b){x=a;y=b;}
};
int index(const point & pz,const point & box,int m,int n){
    return box.y+box.x*n+pz.y*n*m+pz.x*n*m*n;
}
int indexdirect(int x1,int y1,int x2,int y2,int m,int n){
    return y2+x2*n+y1*n*m+x1*n*m*n;
}
class bitvector{
  public:
    bitvector(int num):bitvalues((num+7)/8,0){}
    bitvector(const bitvector & s):bitvalues(s.bitvalues){}
    bitvector(){}
    int size() const{return 8*bitvalues.size();}
    void set(int index){bitvalues[bytenumber(index)]|=mask(index);}
    void clear(int index){bitvalues[bytenumber(index)]&=(~mask(index));}
    int test(int index) const{return 0!=(bitvalues[bytenumber(index)]&mask(index));}
    void flip(int index){bitvalues[bytenumber(index)]^=mask(index);}
  protected:
    vector<char> bitvalues;
    int bytenumber(int index) const{return index>>3;}
    int mask(int index) const{return 1<<(index&07);}
};
void dfs(vector<vector<char> > & map,int m,int n,int x,int y,int im,int jm,int & l){
    if(x==im&&y==jm) {l=1;return;}
	int i,k,j;
	for(k=0;k<4;k++){
		i=x+p[k][0];j=y+p[k][1];
        if(i>=0&&j>=0&&i<m&&j<n&&map[i][j]=='.'){
            map[i][j]='#';
			dfs(map,m,n,i,j,im,jm,l);
			if(l==1) break;
		}
	}
}
int main(){
   //ifstream cin("in.txt");
   int i,j,m,n,l,k,no=1;
   char c;
   while(cin>>m>>n&&!(m==0&&n==0)){
	  cout<<"Maze #"<<no++<<endl;
      vector<char> _vec(n,'.');
	  vector<vector<char> > vec(m,_vec),map;
	  bitvector veccmp(n*n*m*m);
	  point box,pz,aim;
	  for(i=0;i<m;i++){
		  for(j=0;j<n;j++){
              cin>>c;
			  if(c=='#') vec[i][j]='#';
			  else if(c=='S') {pz.x=i;pz.y=j;}
			  else if(c=='B') {box.x=i;box.y=j;}
			  else if(c=='T') {aim.x=i;aim.y=j;}
		  }
	  }  
	  veccmp.set(index(pz,box,m,n));
	  vector<point> lastpz,nowpz,lastbox,nowbox;
	  vector<string> lastpath,nowpath;
	  lastpz.push_back(pz); lastbox.push_back(box); lastpath.push_back("");
	  string res,fres;
	  while(lastbox.size()){
           for(i=0;i<lastbox.size();i++)
			   for(k=0;k<4;k++){
                   int ib=lastbox[i].x+p[k][0],jb=lastbox[i].y+p[k][1],im=lastbox[i].x-p[k][0],jm=lastbox[i].y-p[k][1];
				   if(ib>=0&&jm>=0&&jb>=0&&im>=0&&ib<m&&jb<n&&im<m&&jm<n&&vec[ib][jb]=='.'&&vec[im][jm]=='.'&&!veccmp.test(indexdirect(im,jm,ib,jb,m,n))){
                         l=0; map=vec; map[lastbox[i].x][lastbox[i].y]=map[lastpz[i].x][lastpz[i].y]='#';
						 dfs(map,m,n,lastpz[i].x,lastpz[i].y,im,jm,l);
						 if(l==1){//能走
							      veccmp.set(indexdirect(im,jm,ib,jb,m,n));
								  nowpz.push_back(point(im,jm));
								  nowbox.push_back(point(ib,jb));
                                  string temps=lastpath[i];
							      switch (k){
                                  case 0 :{temps.insert(temps.end(),'S');break;}
							      case 1 :{temps.insert(temps.end(),'E');break;}
							      case 2 :{temps.insert(temps.end(),'N');break;}
							      case 3 :{temps.insert(temps.end(),'W');break;}
								  }                                                       
                                  nowpath.push_back(temps);
								  if(ib==aim.x&&jb==aim.y) {res=temps; goto outer1;}
						 }
				   }
			   }
		  lastpz=nowpz; lastbox=nowbox; lastpath=nowpath;
		  nowpz.clear();nowbox.clear(); nowpath.clear();
	  }
      outer1:
	  if(res=="") {cout<<"Impossible.\n\n";continue;}
	  int lastim=pz.x,lastjm=pz.y,nowim,nowjm,lastib=box.x,lastjb=box.y;
	  for(i=0;i<res.length();i++){
          switch (res[i]){
		  case 'S': {k=0;break;}	  
          case 'E': {k=1;break;}
	      case 'N': {k=2;break;}
		  case 'W': {k=3;break;}
		  }
          nowim=lastib-p[k][0];nowjm=lastjb-p[k][1];
		  if(!(lastim==nowim&&lastjm==nowjm)){
		  bitvector cmp(m*n);
		  cmp.set(lastim*n+lastjm);
		  vector<int> lim,lin,nim,nin;
		  vector<string> lstr,nstr;
          lim.push_back(lastim); lin.push_back(lastjm); lstr.push_back("");
		  map=vec; map[lastib][lastjb]='#';
          while(lim.size()){
              for(j=0;j<lim.size();j++){
                  for(l=0;l<4;l++){
                      int inim=lim[j]+p[l][0],inin=lin[j]+p[l][1];
					  if(inim>=0&&inin>=0&&inim<m&&inin<n&&map[inim][inin]=='.'&&!cmp.test(inim*n+inin)){
                          nim.push_back(inim); nin.push_back(inin); string tempss=lstr[j];
						  switch (l){
                                  case 0 :{tempss.insert(tempss.end(),'s');break;}
							      case 1 :{tempss.insert(tempss.end(),'e');break;}
							      case 2 :{tempss.insert(tempss.end(),'n');break;}
							      case 3 :{tempss.insert(tempss.end(),'w');break;}
						  }
						 cmp.set(inim*n+inin);
						 nstr.push_back(tempss);		  
						 if(inim==nowim&&inin==nowjm) { fres.insert(fres.end(),tempss.begin(),tempss.end()); goto outer2;}
					  }
				  }
			  }
			  lstr=nstr;lin=nin;lim=nim;
			  nstr.clear();nin.clear();nim.clear();
		  }
		  }
          outer2:
		  fres.insert(fres.end(),res[i]);
		  lastim=lastib;lastjm=lastjb;lastib+=p[k][0];lastjb+=p[k][1];
	  }
	  cout<<fres<<endl<<endl;
   }
}