1258.cpp

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

#include<string>
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int p[8][2]={1,0,0,1,-1,-1,1,-1,-1,1,1,1,0,-1,-1,0};
int binarySearch(vector<string> & data,string 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");
  vector<char> vecchar(4); vector<int> vecnum(4);
  vector<vector<char> > vecca(4,vecchar),veccb(4,vecchar);
  vector<vector<int> >  vecna(4,vecnum), vecnb(4,vecnum);
  int i,j,k,l1,l2,l3,c=0;
  while(1){
	  vector<string> s1,s2;

      for(i=0;i<4;i++){
		  for(j=0;j<4;j++){
              cin>>vecca[i][j];
			  if(vecca[0][0]=='#') goto end;
			  if(vecca[i][j]=='A'||vecca[i][j]=='E'||vecca[i][j]=='I'||vecca[i][j]=='O'||vecca[i][j]=='U'||vecca[i][j]=='Y') vecna[i][j]=1;
			  else vecna[i][j]=0;
		  }
		  for(j=0;j<4;j++){
			  cin>>veccb[i][j];
			  if(veccb[i][j]=='A'||veccb[i][j]=='E'||veccb[i][j]=='I'||veccb[i][j]=='O'||veccb[i][j]=='U'||veccb[i][j]=='Y') vecnb[i][j]=1;
			  else vecnb[i][j]=0;
		  }
	  }
	  if(c!=0) cout<<endl;
	  c=1;
	  /*for(i=0;i<4;i++){
		  for(j=0;j<4;j++){
             cout<<vecna[i][j]<<" ";
		  }
		  cout<<endl;
	  }
	  for(i=0;i<4;i++){
		  for(j=0;j<4;j++){
             cout<<vecnb[i][j]<<" ";
		  }
		  cout<<endl;
	  }*/
	  for(i=0;i<4;i++){
		  for(j=0;j<4;j++){
              for(l1=0;l1<8;l1++)
				  for(l2=0;l2<8;l2++)
					  for(l3=0;l3<8;l3++){
                          int i1=i+p[l1][0],j1=j+p[l1][1],i2=i1+p[l2][0],j2=j1+p[l2][1],i3=i2+p[l3][0],j3=j2+p[l3][1];
                          if(i1>=0&&i1<4&&i2>=0&&i2<4&&i3>=0&&i3<4&&j1>=0&&j1<4&&j2>=0&&j2<4&&j3>=0&&j3<4){
							  if(!(i==i1&&j==j1)&&!(i==i2&&j==j2)&&!(i==i3&&j==j3)&&!(i1==i2&&j1==j2)&&!(i1==i3&&j1==j3)&&!(j2==j3&&i2==i3)){
                                  k=vecna[i][j]+vecna[i1][j1]+vecna[i2][j2]+vecna[i3][j3];
								  if(k==2){
                                      string temp="    ";
									  temp[0]=vecca[i][j];temp[1]=vecca[i1][j1];temp[2]=vecca[i2][j2];temp[3]=vecca[i3][j3];
									  k=binarySearch(s1,temp);
									  if(k==s1.size()||s1[k]!=temp){
									     s1.insert(s1.begin()+k,temp);
									  }
								  }
							  }
						  }
					  }
		  }
	  }
	  for(i=0;i<4;i++){
		  for(j=0;j<4;j++){
              for(l1=0;l1<8;l1++)
				  for(l2=0;l2<8;l2++)
					  for(l3=0;l3<8;l3++){
                          int i1=i+p[l1][0],j1=j+p[l1][1],i2=i1+p[l2][0],j2=j1+p[l2][1],i3=i2+p[l3][0],j3=j2+p[l3][1];
                          if(i1>=0&&i1<4&&i2>=0&&i2<4&&i3>=0&&i3<4&&j1>=0&&j1<4&&j2>=0&&j2<4&&j3>=0&&j3<4){
							  if(!(i==i1&&j==j1)&&!(i==i2&&j==j2)&&!(i==i3&&j==j3)&&!(i1==i2&&j1==j2)&&!(i1==i3&&j1==j3)&&!(j2==j3&&i2==i3)){
                                  k=vecnb[i][j]+vecnb[i1][j1]+vecnb[i2][j2]+vecnb[i3][j3];
								  if(k==2){
                                      string temp="    ";
									  temp[0]=veccb[i][j];temp[1]=veccb[i1][j1];temp[2]=veccb[i2][j2];temp[3]=veccb[i3][j3];
									  k=binarySearch(s1,temp);
									  if(k!=s1.size()&&s1[k]==temp){
										  k=binarySearch(s2,temp);
									      if(k==s2.size()||s2[k]!=temp){
									         s2.insert(s2.begin()+k,temp);
										  }
									  }
								  }
							  }
						  }
					  }
		  }
	  }
	  //cout<<s1.size()<<" "<<s2.size()<<endl;
	  sort(s2.begin(),s2.end());
	  if(s2.size()==0) cout<<"There are no common words for this pair of boggle boards.\n";
	  else {
          for(i=0;i<s2.size();i++)
			  cout<<s2[i]<<endl;
	  }
  }
end:return 0;
}