1505.cpp

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

#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
int p[4][2]={1,0,-1,0,0,-1,0,1};
class point{
public:
	int x,y;
};
int pointcmp(const point & a,const point & b){
    if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}
class item{
public:
	vector<point> vecp;
	int index;
	item(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
        vecp.resize(4);
		vecp[0].x=x1; vecp[0].y=y1;
		vecp[1].x=x2; vecp[1].y=y2;
		vecp[2].x=x3; vecp[2].y=y3;
		vecp[3].x=x4; vecp[3].y=y4;
		sort(vecp.begin(),vecp.end(),pointcmp);
		index=vecp[0].x*pow(8,7)+vecp[0].y*pow(8,6)+vecp[1].x*pow(8,5)+vecp[1].y*pow(8,4)+vecp[2].x*pow(8,3)+vecp[2].y*pow(8,2)+vecp[3].x*8+vecp[3].y;
	}
};
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 deal(const vector<point> & s,int j,int k,int & f,int & x1,int & y1,int & x2,int & y2,int & x3,int & y3,int & x4,int & y4){
    vector<int> vect(8,0);
	vector<vector<int> > vecc(8,vect);
	x1=s[0].x;x2=s[1].x;x3=s[2].x;x4=s[3].x;
	y1=s[0].y;y2=s[1].y;y3=s[2].y;y4=s[3].y; //把x,y负上原来的直
	vecc[x1][y1]=vecc[x2][y2]=vecc[x3][y3]=vecc[x4][y4]=1;
	int ii=s[j].x+p[k][0],jj=s[j].y+p[k][1];
	if(ii<0||jj<0||ii>7||jj>7) {f=0; return;} //出界
    else{ //没出界
		if(vecc[ii][jj]==0){ //可以放
			switch (j){
			case 0: {x1=ii;y1=jj;break;}
			case 1: {x2=ii;y2=jj;break;}	
            case 2: {x3=ii;y3=jj;break;}
	        case 3: {x4=ii;y4=jj;break;}
			}
			f=1;return;
		}
        else{ //不能放
            ii+=p[k][0];jj+=p[k][1]; //跳一不
			if(ii<0||jj<0||ii>7||jj>7) {f=0; return;} //出界
			else{ //没出截
				if(vecc[ii][jj]==1) {f=0;return;}
			    switch (j){
			    case 0: {x1=ii;y1=jj;break;}
			    case 1: {x2=ii;y2=jj;break;}	
                case 2: {x3=ii;y3=jj;break;}
	            case 3: {x4=ii;y4=jj;break;}
				}
			    f=1;return;
			}
		}
	}
}
int minidis(const item & a,const item & b){
   //0123
   int res=abs(a.vecp[0].x-b.vecp[0].x)+abs(a.vecp[1].x-b.vecp[1].x)+abs(a.vecp[2].x-b.vecp[2].x)+abs(a.vecp[3].x-b.vecp[3].x)+
		   abs(a.vecp[0].y-b.vecp[0].y)+abs(a.vecp[1].y-b.vecp[1].y)+abs(a.vecp[2].y-b.vecp[2].y)+abs(a.vecp[3].y-b.vecp[3].y);
   //0132
   int tep=abs(a.vecp[0].x-b.vecp[0].x)+abs(a.vecp[1].x-b.vecp[1].x)+abs(a.vecp[3].x-b.vecp[2].x)+abs(a.vecp[2].x-b.vecp[3].x)+
		   abs(a.vecp[0].y-b.vecp[0].y)+abs(a.vecp[1].y-b.vecp[1].y)+abs(a.vecp[3].y-b.vecp[2].y)+abs(a.vecp[2].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //0213
   tep=abs(a.vecp[0].x-b.vecp[0].x)+abs(a.vecp[2].x-b.vecp[1].x)+abs(a.vecp[1].x-b.vecp[2].x)+abs(a.vecp[3].x-b.vecp[3].x)+
	   abs(a.vecp[0].y-b.vecp[0].y)+abs(a.vecp[2].y-b.vecp[1].y)+abs(a.vecp[1].y-b.vecp[2].y)+abs(a.vecp[3].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //0231
   tep=abs(a.vecp[0].x-b.vecp[0].x)+abs(a.vecp[2].x-b.vecp[1].x)+abs(a.vecp[3].x-b.vecp[2].x)+abs(a.vecp[1].x-b.vecp[3].x)+
	   abs(a.vecp[0].y-b.vecp[0].y)+abs(a.vecp[2].y-b.vecp[1].y)+abs(a.vecp[3].y-b.vecp[2].y)+abs(a.vecp[1].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //0312
   tep=abs(a.vecp[0].x-b.vecp[0].x)+abs(a.vecp[3].x-b.vecp[1].x)+abs(a.vecp[1].x-b.vecp[2].x)+abs(a.vecp[2].x-b.vecp[3].x)+
	   abs(a.vecp[0].y-b.vecp[0].y)+abs(a.vecp[3].y-b.vecp[1].y)+abs(a.vecp[1].y-b.vecp[2].y)+abs(a.vecp[2].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //0321
   tep=abs(a.vecp[0].x-b.vecp[0].x)+abs(a.vecp[3].x-b.vecp[1].x)+abs(a.vecp[2].x-b.vecp[2].x)+abs(a.vecp[1].x-b.vecp[3].x)+
	   abs(a.vecp[0].y-b.vecp[0].y)+abs(a.vecp[3].y-b.vecp[1].y)+abs(a.vecp[2].y-b.vecp[2].y)+abs(a.vecp[1].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //1023
   tep=abs(a.vecp[1].x-b.vecp[0].x)+abs(a.vecp[0].x-b.vecp[1].x)+abs(a.vecp[2].x-b.vecp[2].x)+abs(a.vecp[3].x-b.vecp[3].x)+
	   abs(a.vecp[1].y-b.vecp[0].y)+abs(a.vecp[0].y-b.vecp[1].y)+abs(a.vecp[2].y-b.vecp[2].y)+abs(a.vecp[3].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //1032
   tep=abs(a.vecp[1].x-b.vecp[0].x)+abs(a.vecp[0].x-b.vecp[1].x)+abs(a.vecp[3].x-b.vecp[2].x)+abs(a.vecp[2].x-b.vecp[3].x)+
	   abs(a.vecp[1].y-b.vecp[0].y)+abs(a.vecp[0].y-b.vecp[1].y)+abs(a.vecp[3].y-b.vecp[2].y)+abs(a.vecp[2].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //1203
   tep=abs(a.vecp[1].x-b.vecp[0].x)+abs(a.vecp[2].x-b.vecp[1].x)+abs(a.vecp[0].x-b.vecp[2].x)+abs(a.vecp[3].x-b.vecp[3].x)+
	   abs(a.vecp[1].y-b.vecp[0].y)+abs(a.vecp[2].y-b.vecp[1].y)+abs(a.vecp[0].y-b.vecp[2].y)+abs(a.vecp[3].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //1230
   tep=abs(a.vecp[1].x-b.vecp[0].x)+abs(a.vecp[2].x-b.vecp[1].x)+abs(a.vecp[3].x-b.vecp[2].x)+abs(a.vecp[0].x-b.vecp[3].x)+
	   abs(a.vecp[1].y-b.vecp[0].y)+abs(a.vecp[2].y-b.vecp[1].y)+abs(a.vecp[3].y-b.vecp[2].y)+abs(a.vecp[0].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //1302
   tep=abs(a.vecp[1].x-b.vecp[0].x)+abs(a.vecp[3].x-b.vecp[1].x)+abs(a.vecp[0].x-b.vecp[2].x)+abs(a.vecp[2].x-b.vecp[3].x)+
	   abs(a.vecp[1].y-b.vecp[0].y)+abs(a.vecp[3].y-b.vecp[1].y)+abs(a.vecp[0].y-b.vecp[2].y)+abs(a.vecp[2].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //1320
   tep=abs(a.vecp[1].x-b.vecp[0].x)+abs(a.vecp[3].x-b.vecp[1].x)+abs(a.vecp[2].x-b.vecp[2].x)+abs(a.vecp[0].x-b.vecp[3].x)+
	   abs(a.vecp[1].y-b.vecp[0].y)+abs(a.vecp[3].y-b.vecp[1].y)+abs(a.vecp[2].y-b.vecp[2].y)+abs(a.vecp[0].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //2013
   tep=abs(a.vecp[2].x-b.vecp[0].x)+abs(a.vecp[0].x-b.vecp[1].x)+abs(a.vecp[1].x-b.vecp[2].x)+abs(a.vecp[3].x-b.vecp[3].x)+
	   abs(a.vecp[2].y-b.vecp[0].y)+abs(a.vecp[0].y-b.vecp[1].y)+abs(a.vecp[1].y-b.vecp[2].y)+abs(a.vecp[3].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //2031
   tep=abs(a.vecp[2].x-b.vecp[0].x)+abs(a.vecp[0].x-b.vecp[1].x)+abs(a.vecp[3].x-b.vecp[2].x)+abs(a.vecp[1].x-b.vecp[3].x)+
	   abs(a.vecp[2].y-b.vecp[0].y)+abs(a.vecp[0].y-b.vecp[1].y)+abs(a.vecp[3].y-b.vecp[2].y)+abs(a.vecp[1].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //2103
   tep=abs(a.vecp[2].x-b.vecp[0].x)+abs(a.vecp[1].x-b.vecp[1].x)+abs(a.vecp[0].x-b.vecp[2].x)+abs(a.vecp[3].x-b.vecp[3].x)+
	   abs(a.vecp[2].y-b.vecp[0].y)+abs(a.vecp[1].y-b.vecp[1].y)+abs(a.vecp[0].y-b.vecp[2].y)+abs(a.vecp[3].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //2130
   tep=abs(a.vecp[2].x-b.vecp[0].x)+abs(a.vecp[1].x-b.vecp[1].x)+abs(a.vecp[3].x-b.vecp[2].x)+abs(a.vecp[0].x-b.vecp[3].x)+
	   abs(a.vecp[2].y-b.vecp[0].y)+abs(a.vecp[1].y-b.vecp[1].y)+abs(a.vecp[3].y-b.vecp[2].y)+abs(a.vecp[0].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //2301
   tep=abs(a.vecp[2].x-b.vecp[0].x)+abs(a.vecp[3].x-b.vecp[1].x)+abs(a.vecp[0].x-b.vecp[2].x)+abs(a.vecp[1].x-b.vecp[3].x)+
	   abs(a.vecp[2].y-b.vecp[0].y)+abs(a.vecp[3].y-b.vecp[1].y)+abs(a.vecp[0].y-b.vecp[2].y)+abs(a.vecp[1].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //2310
   tep=abs(a.vecp[2].x-b.vecp[0].x)+abs(a.vecp[3].x-b.vecp[1].x)+abs(a.vecp[1].x-b.vecp[2].x)+abs(a.vecp[0].x-b.vecp[3].x)+
	   abs(a.vecp[2].y-b.vecp[0].y)+abs(a.vecp[3].y-b.vecp[1].y)+abs(a.vecp[1].y-b.vecp[2].y)+abs(a.vecp[0].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //3012
   tep=abs(a.vecp[3].x-b.vecp[0].x)+abs(a.vecp[0].x-b.vecp[1].x)+abs(a.vecp[1].x-b.vecp[2].x)+abs(a.vecp[2].x-b.vecp[3].x)+
	   abs(a.vecp[3].y-b.vecp[0].y)+abs(a.vecp[0].y-b.vecp[1].y)+abs(a.vecp[1].y-b.vecp[2].y)+abs(a.vecp[2].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //3021
   tep=abs(a.vecp[3].x-b.vecp[0].x)+abs(a.vecp[0].x-b.vecp[1].x)+abs(a.vecp[2].x-b.vecp[2].x)+abs(a.vecp[1].x-b.vecp[3].x)+
	   abs(a.vecp[3].y-b.vecp[0].y)+abs(a.vecp[0].y-b.vecp[1].y)+abs(a.vecp[2].y-b.vecp[2].y)+abs(a.vecp[1].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //3102
   tep=abs(a.vecp[3].x-b.vecp[0].x)+abs(a.vecp[1].x-b.vecp[1].x)+abs(a.vecp[0].x-b.vecp[2].x)+abs(a.vecp[2].x-b.vecp[3].x)+
	   abs(a.vecp[3].y-b.vecp[0].y)+abs(a.vecp[1].y-b.vecp[1].y)+abs(a.vecp[0].y-b.vecp[2].y)+abs(a.vecp[2].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //3120
   tep=abs(a.vecp[3].x-b.vecp[0].x)+abs(a.vecp[1].x-b.vecp[1].x)+abs(a.vecp[2].x-b.vecp[2].x)+abs(a.vecp[0].x-b.vecp[3].x)+
	   abs(a.vecp[3].y-b.vecp[0].y)+abs(a.vecp[1].y-b.vecp[1].y)+abs(a.vecp[2].y-b.vecp[2].y)+abs(a.vecp[0].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //3201
   tep=abs(a.vecp[3].x-b.vecp[0].x)+abs(a.vecp[2].x-b.vecp[1].x)+abs(a.vecp[0].x-b.vecp[2].x)+abs(a.vecp[1].x-b.vecp[3].x)+
	   abs(a.vecp[3].y-b.vecp[0].y)+abs(a.vecp[2].y-b.vecp[1].y)+abs(a.vecp[0].y-b.vecp[2].y)+abs(a.vecp[1].y-b.vecp[3].y);
   if(tep<res) res=tep;
   //3210
   tep=abs(a.vecp[3].x-b.vecp[0].x)+abs(a.vecp[2].x-b.vecp[1].x)+abs(a.vecp[1].x-b.vecp[2].x)+abs(a.vecp[0].x-b.vecp[3].x)+
	   abs(a.vecp[3].y-b.vecp[0].y)+abs(a.vecp[2].y-b.vecp[1].y)+abs(a.vecp[1].y-b.vecp[2].y)+abs(a.vecp[0].y-b.vecp[3].y);
   if(tep<res) res=tep;
   return res;
}
int main(){
    //ifstream cin("in.txt");
	int i,j,k,f,x1,y1,x2,y2,x3,y3,x4,y4;
	while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4){
		 bitvector veccmp(pow(8,8));
         item begin(x1-1,y1-1,x2-1,y2-1,x3-1,y3-1,x4-1,y4-1);
		 veccmp.set(begin.index);
         cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
         item aim(x1-1,y1-1,x2-1,y2-1,x3-1,y3-1,x4-1,y4-1);
		 if(veccmp.test(aim.index)) {cout<<"YES\n"; continue;}
		 if(minidis(aim,begin)>16)  {cout<<"NO\n";  continue;}
         vector<item> lastitem,newitem; lastitem.push_back(begin);
		 for(int loop=0;loop<8;loop++){
             for(i=0;i<lastitem.size();i++){
				 for(j=0;j<4;j++){
                     for(k=0;k<4;k++){
                         deal(lastitem[i].vecp,j,k,f,x1,y1,x2,y2,x3,y3,x4,y4);
						 if(f==1){
                             item temp(x1,y1,x2,y2,x3,y3,x4,y4);
							 int dis=minidis(temp,aim);
							 if((dis<=(14-2*loop))&&!veccmp.test(temp.index)){
								 if(temp.index==aim.index){cout<<"YES"; goto outer;}
                                 newitem.push_back(temp);
                                 veccmp.set(temp.index);
							 }
						 }
					 }//方向
				 }//lastitem[i].vecp[j]
			 }//lastitem[i]
			 lastitem=newitem;
			 newitem.clear();
		 }//bfs
		 cout<<"NO";
         outer:
		 cout<<endl;
	}
}