Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

150题,贴AC代码纪念

Posted by yc5_yc at 2012-08-13 15:33:41 on Problem 1027
#include <cstdio>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct area {int cntDot;pair<int,int> Leftmost;pair<int,int> Dot[200];};
char A[15][16];
bool fw[15][16];
int tot;
area tmp,best;
bool operator<(const pair<int,int>a,const pair<int,int>b)
{return a.second<b.second||(a.second==b.second&&a.first<b.first);}
void DFS(int x,int y) {
    if(x<0 || y<0 || x>9 || y>14 || fw[x][y]) return ;
    fw[x][y]=1;tot++;
    if(make_pair(x,y)<tmp.Leftmost) tmp.Leftmost=make_pair(x,y);
    tmp.Dot[tmp.cntDot++]=make_pair(x,y);
    if(x>0 && A[x-1][y]==A[x][y])DFS(x-1,y);
    if(A[x+1][y]==A[x][y])DFS(x+1,y);
    if(y>0 && A[x][y-1]==A[x][y])DFS(x,y-1);
    if(A[x][y+1]==A[x][y])DFS(x,y+1);
}
bool Have_Ball() {
    best.cntDot=-1;best.Leftmost=make_pair(20,20);
    memset(fw,0,sizeof(fw));
    for(int i=0;i<10;i++)
        for(int j=0;j<15;j++) if(A[i][j]!=0 && !fw[i][j]) {
            tot=0;
            tmp.Leftmost=make_pair(20,20);tmp.cntDot=0;
            DFS(i,j);
            if(tmp.cntDot>best.cntDot ||
               (tmp.cntDot==best.cntDot && tmp.Leftmost<best.Leftmost)) 
                best=tmp;
        }
    return best.cntDot>1;
}
void Delete_y() {
    for(int i=1;i<10;i++)
        for(int j=0;j<15;j++) for(int I=1;I<=20;I++) if(A[i-1][j]==0)
            for(int k=i;k<10;k++) {A[k-1][j]=A[k][j];A[k][j]=0;}
}
void Delete_x() {
    for(int i=0;i<15;i++) {
        bool flag=1;
        for(int j=0;j<10;j++) if(A[j][i]!=0) {flag=0;break;}
        for(int I=1;I<=20;I++)if(flag){
            for(int j=i+1;j<15;j++) {
                for(int k=0;k<10;k++) A[k][j-1]=A[k][j];
                for(int k=0;k<10;k++) A[k][j]=0;
            }
            flag=1;
            for(int j=0;j<10;j++) if(A[j][i]!=0) {flag=0;break;}
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int I=1;I<=T;I++) {
        for(int i=9;i>=0;i--) scanf("%s",A[i]);
        printf("Game %d:\n\n",I);
        int cntpoint=0,cntball=150,moveT=1;
        while(Have_Ball()) {
            printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",
                   moveT,
                   best.Leftmost.first+1,best.Leftmost.second+1,
                   best.cntDot,A[best.Leftmost.first][best.Leftmost.second],
                   (best.cntDot-2)*(best.cntDot-2));
            cntpoint+=(best.cntDot-2)*(best.cntDot-2);
            cntball-=best.cntDot;
            for(int i=0;i<best.cntDot;i++) A[best.Dot[i].first][best.Dot[i].second]=0;
            Delete_y();Delete_x();
            //for(int i=0;i<10;i++) {
            //    for(int j=0;j<15;j++)
            //        printf("%c",A[i][j]==0?' ':A[i][j]);
            //    puts("");
            //}
            //getchar();getchar();getchar();getchar();
            moveT++;
        }
        if(cntball==0) cntpoint+=1000;
        printf("Final score: %d, with %d balls remaining.\n\n",
               cntpoint,cntball);
    }
    return 0;
}
刷水好爽!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator