Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
150题,贴AC代码纪念#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator