DFS算，五分钟如果答案没有更新，那个解一般来说就很优了。
#include <cstdio> #include <iostream> #include <string.h> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <cmath> #include <map> #include <stack> using namespace std; int const uu[4] = {1,-1,0,0}; int const vv[4] = {0,0,1,-1}; typedef long long ll; int const inf = 0x3f3f3f3f; ll const INF = 0x7fffffffffffffffll; double eps = 1e-10; double pi = acos(-1.0); #define rep(i,s,n) for(int i=(s);i<=(n);++i) #define rep2(i,s,n) for(int i=(s);i>=(n);--i) #define mem(v,n) memset(v,(n),sizeof(v)) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 struct node{int x,y; }tempAns[205],Ans[205];char FIRST[101][101]; bool VIS[101][101]; int bestScore; int STEP;bool check(char mp[101][101],int x,int y){rep(k,0,3){int xx=x+uu[k], yy=y+vv[k];if(xx>=1&&xx<=100 && yy>=1&&yy<=100 && mp[xx][yy]==mp[x][y]) return true;}return false; } int color1(char mp[101][101],bool vis[101][101],int x,int y){vis[x][y]=true;int res=1;rep(k,0,3){int xx=x+uu[k], yy=y+vv[k];if(xx>=1&&xx<=100 && yy>=1&&yy<=100 && vis[xx][yy]==false && mp[xx][yy]==mp[x][y]) res+=color1(mp,vis,xx,yy);}mp[x][y]=0;return res; } void proc1(char mp[101][101]){rep(j,1,10) rep2(i,9,1){int g=i,h=j;while(g+1<=10 && mp[g+1][h]==0) ++g;mp[g][h]=mp[i][j];if(g!=i) mp[i][j]=0;}rep(j,2,10){if(mp[10][j]==0) continue;int k;for(k=j-1;k>=1;--k) if(mp[10][k]!=0) break;if(k+1<j){rep(i,1,10){mp[i][k+1]=mp[i][j];mp[i][j]=0;}}} }void print(){char ms[101][101];bool vs[101][101]; mem(vs,false);rep(i,1,10) rep(j,1,10) ms[i][j]=FIRST[i][j];rep(i,1,10){rep(j,1,10)if(Ans[1].x==i&&Ans[1].y==j)printf("#");else{if(ms[i][j]==0)printf(" ");elseprintf("%d",ms[i][j]);}cout<<endl;}rep(i,1,STEP){printf("step%d = (%d,%d)\n",i,Ans[i].x,Ans[i].y); cout<<endl<<endl;color1(ms,vs,Ans[i].x,Ans[i].y);proc1(ms);if(i!=STEP){rep(k,1,10){rep(j,1,10)if(Ans[i+1].x==k&&Ans[i+1].y==j)printf("#");else{if(ms[k][j]==0)printf(" ");elseprintf("%d",ms[k][j]);}cout<<endl;}}} }//mp[][]:current state step:current step score:current score void dfs(char mp[101][101],bool vis[101][101],int tx,int ty,int step,int score){ //printf("step=%d score=%d click on (%d,%d) of last image.\n",step,score,tx,ty);/*rep(i,1,10){rep(j,1,10) if(mp[i][j]!=0) printf("%d ",mp[i][j]); else printf(" ");cout<<endl;}*/tempAns[step].x=tx;tempAns[step].y=ty;rep(i,1,10) rep(j,1,10){if(mp[i][j]==0) continue; //这个位置是空的，跳过if(vis[i][j]) continue; //计算过，跳过if(check(mp,i,j)==false){ //点击这个位置没法消去块vis[i][j]=true;continue;}char temp_mp[101][101];bool temp_vis[101][101]; mem(temp_vis,false);rep(i1,1,10) rep(j1,1,10) temp_mp[i1][j1]=mp[i1][j1];int ts=color1(temp_mp,vis,i,j);proc1(temp_mp);dfs(temp_mp,temp_vis,i,j,step+1,score+5*ts*ts);}if(score>bestScore){STEP=step;rep(i,0,step) Ans[i]=tempAns[i];bestScore=score;cout<<"bestScore = "<<bestScore<<endl;//print();rep(i,1,step) printf("step%d = (%d,%d)\n",i,Ans[i].x,Ans[i].y); cout<<endl<<endl;} }void read(){rep(i,0,10) rep(j,0,10) FIRST[i][j]=-1;freopen("c:\\hello.in","r",stdin);rep(i,1,10) rep(j,1,10) scanf("%d",&FIRST[i][j]);fclose(stdin); } void init(){bestScore=0;mem(VIS,false); } int main(){read();init();dfs(FIRST,VIS,-1,-1,0,0); }
