1217.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int p[4][2]={-1,0,0,-1,0,1,1,0};
class item{
public:
	char grid[3][3];
	int index,xi,xj,realindex;
	int rank;
	item(){}
	item(const item & s){for(int i=0;i<3;i++) for(int j=0;j<3;j++) grid[i][j]=s.grid[i][j]; xi=s.xi;xj=s.xj;rank=s.rank;}
	void init(int n){
		realindex=0;rank=n;
        for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
			   if(grid[i][j]!='x'){
                   realindex+=pow(10,grid[i][j]-'1')*(i*3+j+1);
			   }
			   else{
                   xi=i;xj=j;
			   }
			   //if(grid[i][j]-'1'==i*3+j) rank+=1;
			}
		}
		index=realindex%44449;
	}
};
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");
	//ofstream cout("out.txt");
    char c;
	int i,j,k,n,lastrank,nowrank,q;
	int aimindex=87654321;
    while(cin>>c){
        item begin; begin.grid[0][0]=c; for(i=1;i<3;i++) cin>>begin.grid[0][i];
		for(i=1;i<3;i++) for(j=0;j<3;j++) cin>>begin.grid[i][j];
		begin.init(0);
		if(begin.realindex==aimindex) {cout<<endl; continue;}
		if(begin.realindex==12345678) {cout<<"ululddruulddruurddluurdluldrdr\n"; continue;}
		vector<vector<int> > cmp(44449);
		cmp[begin.index].push_back(begin.realindex);
		vector<item> last,now; 
		vector<string> lasts,nows;
		last.push_back(begin); 
		lasts.push_back("");
		//q=0;lastrank=begin.rank;
		while(last.size()){
			//q++;nowrank=210000000;
			for(i=0;i<last.size();i++){
				//if(last[i].rank==lastrank)
                for(k=0;k<4;k++){
                    int ii=last[i].xi+p[k][0],jj=last[i].xj+p[k][1];
					if(ii>=0&&jj>=0&&ii<3&&jj<3){
                        item temp(last[i]);
						c=temp.grid[ii][jj]; temp.grid[ii][jj]=temp.grid[last[i].xi][last[i].xj]; temp.grid[last[i].xi][last[i].xj]=c;
						temp.init(q);
						j=binarySearch(cmp[temp.index],temp.realindex);
						if(j==cmp[temp.index].size()||cmp[temp.index][j]!=temp.realindex){
						//if(find(cmp[temp.index].begin(),cmp[temp.index].end(),temp.realindex)==cmp[temp.index].end()){
                            now.push_back(temp);
							nows.push_back(lasts[i]);
							switch (k){
							case 0 :{nows.back().insert(nows.back().end(),'u'); break;}
							case 1 :{nows.back().insert(nows.back().end(),'l'); break;}
							case 2 :{nows.back().insert(nows.back().end(),'r'); break;}
							case 3 :{nows.back().insert(nows.back().end(),'d'); break;}
							}
							cmp[temp.index].insert(cmp[temp.index].begin()+j,temp.realindex);
							//cmp[temp.index].push_back(temp.realindex);
							//if(temp.rank<nowrank) nowrank=temp.rank;
							if(temp.realindex==aimindex){cout<<nows.back(); goto outer;}
						}//if
					}//if
				}//for k
				//else {now.push_back(last[i]); nows.push_back(lasts[i]); if(last[i].rank<nowrank) nowrank=last[i].rank;}
			}//for i
			last=now;lasts=nows;now.clear();nows.clear();//lastrank=nowrank;
		}//bfs
		cout<<"unsolvable";
        outer:
		cout<<endl;
	}
}