poj 1027(dfs,偏向实际应用)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char c[10][20];
int data[10][20],idx[10][20],k,score;
struct Node{
    int x,y,sum,mscore;
    char c;
}move[100];
void print(){
    int i,j; 
    for(i=0;i<10;i++){
        for(j=0;j<15;j++)
            printf("%3d",data[i][j]);
        cout<<endl;
    }
    cout<<endl;
} 
int deep(int i,int j,int id){
    int t = data[i][j],s=0;
    if(data[i][j]==-1)return 0;
    idx[i][j] = id;
    if(j<14&&data[i][j+1]==t&&idx[i][j+1]==0){
        s += deep(i,j+1,id);
    }
    if(i>0&&data[i-1][j]==t&&idx[i-1][j]==0){
        s += deep(i-1,j,id);
    }
    if(j>0&&data[i][j-1]==t&&idx[i][j-1]==0){
        s += deep(i,j-1,id);
    }
    if(i<14&&data[i+1][j]==t&&idx[i+1][j]==0){
        s += deep(i+1,j,id);
    }
    return s+1;
}
void del(int i,int j){
    int p,q,r,ss;
    for(p=0;p<10;p++){
        for(q=0;q<15;q++){
            if(idx[i][j]==idx[p][q])
                data[p][q] = -2;
        }
    }
    for(p=0;p<15;p++){
        for(q=9,r=q-1;r>=0;q--,r--){
            if(data[q][p]==-2){
                while(r>=0&&data[r][p]==-2)r--;
                if(r==-1)break;
                data[q][p] = data[r][p];
                data[r][p] = -2;
            }
        }
        for(q=9;q>=0;q--){
            if(data[q][p]==-2){
                data[q][p] = -1;
            }
        }
    }
    for(p=j,q=j+1;q<15;p++,q++){
        if(data[9][p]==-1){
            while(q<15&&data[9][q]==-1)q++;
            if(q==15)break;
            for(r=0;r<10;r++){
                data[r][p] = data[r][q];
                data[r][q] = -1;
            }
        }
    }
}
int main(){
    int t,kase,i,j,count,maxn,maxi,maxj,maxid,tmp,n;
    scanf("%d",&t);
    for(kase=1;kase<=t;kase++){
        for(i=0;i<10;i++){
            scanf("%s",c[i]);
            for(j=0;j<15;j++)
                if(c[i][j]=='R')
                    data[i][j] = 1;
                else if(c[i][j]=='G')
                    data[i][j] = 2;
                else
                    data[i][j] = 3;
        }
        score = 0; 
        n = 0;
        do{
            memset(idx,0,sizeof(idx));
            count = 0;
            maxn = -1;
            for(j=0;j<15;j++)
                for(i=9;i>=0;i--)        
                    if(idx[i][j]==0&&data[i][j]!=-1){
                        tmp = deep(i,j,++count);
                        if(maxn<tmp){
                            maxn = tmp;
                            maxi = i;
                            maxj = j;
                        }
                    }
            if(maxn<2)break;
            else{
                if(data[maxi][maxj]==1)
                    move[n].c = 'R';
                else if(data[maxi][maxj]==2)
                    move[n].c = 'G';
                else 
                    move[n].c = 'B';
                move[n].x = maxi;
                move[n].y = maxj;
                move[n].mscore = (maxn-2)*(maxn-2);
                move[n].sum = maxn;
                n++;
            }
            del(maxi,maxj);
        }while(maxn>1);
//        for(i=0;i<n;i++){
//            cout<<move[i].c<<" "<<move[i].x<<" "<<move[i].y<<" "<<move[i].sum<<endl;
//        }
        score = 0;
        maxn = 0;
        for(i=0;i<n;i++){
            score += move[i].mscore;
            maxn += move[i].sum;
        }
        if(maxn==150)score+=1000;
        printf("Game %d: \n\n",kase);
        for(i=0;i<n;i++){
            printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points. \n",
                    i+1,10-move[i].x,move[i].y+1,move[i].sum,move[i].c,move[i].mscore);
        }
        printf("Final score: %d, with %d balls remaining. \n\n",score,150-maxn);
    }
    return 0;
}

 

上一篇:Ubuntu20.04 Deep-wine容器下载地址


下一篇:树链抛分小记