1361.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int p[4][2]={1,0,0,1,-1,0,0,-1};
class point{
public:
	short x,y;
	point(){}
	point(short a,short b){x=a;y=b;}
};
class snake{
public:
	vector<point> vec;
	short len;
	int index,index1;
	snake(){}
	snake(short a){len=a;vec.resize(a);}
	snake(const snake & s){vec=s.vec;len=s.len;}
	void hash(short m,short n){
       int res=0,res1=0;
	   for(short i=0;i<len;i++){
           res+=(vec[i].x*n+vec[i].y);
		   res*=m;
		   if(res>=1000000) res%=99997;
           res1+=(vec[i].x*n+vec[i].y);
		   res1*=m;
		   if(res1>=2403431) res1%=44447;
	   }
	   res%=99997;
	   index=res;
	   res1*=index;
	   res1%=44447;
	   index1=res1;
	}
};
bool cango(short i,short j,const snake & s){
    for(short k=0;k<s.len;k++){
        if(i==s.vec[k].x&&j==s.vec[k].y) return false;
	}
	return true;
}
int binarySearch(vector<int> & data,int value){
 int low=0;
 int high=data.size();
 while(low<high){
   int mid=(low+high)/2;
   if(data[mid]==value) return mid;
   else if(data[mid]<value)
        low=mid+1;
   else high=mid;
 }
 return low;
}
int main(){
    //ifstream cin("in.txt");
	short i,j,m,n,l,a,b,k;
	int c=1;
	while(cin>>m>>n>>l&&m!=0){
		 cout<<"Case "<<c++<<": ";
         vector<char> _vec(n,'-');
		 vector<vector<char> > vec(m,_vec);
		 snake begin(l);
		 for(i=0;i<l;i++){
            cin>>a>>b;
			begin.vec[i].x=a-1;
			begin.vec[i].y=b-1;
		 }
		 cin>>j;
		 for(i=0;i<j;i++){
            cin>>a>>b;
			vec[a-1][b-1]='#';
		 }
		 if(begin.vec[0].x==0&&begin.vec[0].y==0) {cout<<"0\n";continue;}
		 begin.hash(m,n);
		 vector<vector<int> > cmp(99997);
		 cmp[begin.index].push_back(begin.index1);
		 vector<snake> last,now; last.push_back(begin); l=0;
		 while(last.size()){
			 l+=1;
			 if(l>=50) break;
			 for(i=0;i<last.size();i++){
				 for(k=0;k<4;k++){
                    short hi=last[i].vec[0].x+p[k][0],hj=last[i].vec[0].y+p[k][1];
					if(hi>=0&&hj>=0&&hi<m&&hj<n&&vec[hi][hj]=='-'&&cango(hi,hj,last[i])){
                        snake asnake(last[i]);
						asnake.vec.erase(asnake.vec.end()-1);
						asnake.vec.insert(asnake.vec.begin(),point(hi,hj));
						asnake.hash(m,n);
						int pzpz=binarySearch(cmp[asnake.index],asnake.index1);
						if(pzpz==cmp[asnake.index].size()||asnake.index1!=cmp[asnake.index][pzpz]){
                             now.push_back(asnake);
							 cmp[asnake.index].insert(cmp[asnake.index].begin()+pzpz,asnake.index1);
							 if(hi==0&&hj==0) {cout<<l; goto outer;}
						}
					}
				 }
			 }
             last=now; now.clear();
		 }
		 cout<<"-1";
         outer:
		 cout<<endl;
	}
}