2013年湘潭大学程序设计比赛

/*B题类型：动态规划，思考由后往前，代码，由前往后。。。注意边界。。。 */ #include<iostream>#include<cstdio>#include<string>#include<cmath>using namespace std;#define manx 1009string x;int z[manx];int main(){    int n;    while(cin>>n){        char s[109];        for(int i=0;i<manx;i++) z[i]=0;        x.clear();        for(int i=0;i<n;i++){            cin>>s;            x += s[0];        }        for(int i=0;i<x.size();i++){            for(int j=i-1;j>=0;j--){                z[i]=max(z[i],z[j]);                              if(x[i]==x[j] && j>=1) z[i]=max(z[i],z[j-1]+1);                 if(x[i]==x[j] && j==0) z[i]=max(z[i],1);            }        }        cout<<z[x.size()-1]<<endl;    }}/*4shaoshanerzhongshangxiadongmen5shaoshanshangxiaertianerzhongdongmen*/

/*G题 类型：状态压缩搜索思路，因为状态特殊，每一个状态都可以用一个数字来代替 */#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<queue>using namespace std;#define manx 600000int flag,mark;bool s[manx];struct node{    int ans;    int temp;};queue<node>que;void init(){    while(!que.empty()) que.pop();    for(int i=0;i<manx;i++) s[i]=0;}void bfs(int xx,int yy){    node te = que.front();    s[te.ans]=1;    while(!que.empty()){        te=que.front();        que.pop();     //   cout<<te.ans<<endl;      //  system("pause");        if(te.ans==mark){ flag=1; cout<<te.temp<<endl; break; }        int x[2][3];        x[0][0]=te.ans/100000%10;        x[0][1]=(te.ans/10000)%10;        x[0][2]=(te.ans/1000)%10;        x[1][0]=(te.ans/100)%10;        x[1][1]=(te.ans/10)%10;        x[1][2]=te.ans%10;        for(int i=0;i<2;i++){            for(int j=0;j<3;j++)                if(x[i][j]==0) xx=i,yy=j;        }                if(xx+1<2){            node qe=te;            swap(x[xx][yy],x[xx+1][yy]);            qe.temp++;            int sum=0;                        for(int i=0;i<2;i++){                for(int j=0;j<3;j++){                    sum=sum*10+x[i][j];                }            }            qe.ans=sum;            if(!s[sum]) { s[sum]=1; que.push(qe); }            swap(x[xx][yy],x[xx+1][yy]);        }        if(xx-1>=0){            node qe=te;            swap(x[xx][yy],x[xx-1][yy]);            qe.temp++;            int sum=0;                        for(int i=0;i<2;i++){                for(int j=0;j<3;j++){                    sum=sum*10+x[i][j];                }            }            qe.ans=sum;            if(!s[sum]) { s[sum]=1; que.push(qe); }            swap(x[xx][yy],x[xx-1][yy]);        }        if(yy+1<3){            node qe=te;            swap(x[xx][yy],x[xx][yy+1]);            qe.temp++;            int sum=0;                        for(int i=0;i<2;i++){                for(int j=0;j<3;j++){                    sum=sum*10+x[i][j];                }            }            qe.ans=sum;            if(!s[sum]) { s[sum]=1; que.push(qe); }            swap(x[xx][yy],x[xx][yy+1]);        }        if(yy-1>=0){            node qe=te;            swap(x[xx][yy],x[xx][yy-1]);            qe.temp++;            int sum=0;                        for(int i=0;i<2;i++){                for(int j=0;j<3;j++){                    sum=sum*10+x[i][j];                }            }            qe.ans=sum;            if(!s[sum]) { s[sum]=1; que.push(qe); }            swap(x[xx][yy],x[xx][yy-1]);        }    }}int main(){    int t;    cin>>t;    while(t--){        init();        int a,sum=0;        flag=0;        node te;        int st,ed,val;        for(int i=0;i<2;i++){            for(int j=0;j<3;j++){                scanf("%d",&val);                if(val==0) st=i,ed=j;                sum=sum*10+val;            }        }        te.ans=sum;        sum=0;        for(int i=0;i<2;i++){            for(int j=0;j<3;j++){                scanf("%d",&a);                sum=sum*10+a;             }        }        mark=sum;        te.temp=0;        que.push(te);        bfs(st,ed);        if(!flag) cout<<"Impossible!"<<endl;    }   //  while(1);}/*20 1 23 4 51 2 03 4 51 2 04 5 31 2 34 0 5*/