| ||||||||||
| 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