解题思路：这道题一开始我想用bfs，但这道题我感觉难的是每次消除后，怎么往下往左移动。此外还有就是要剪枝，不然是过不了的，可采用可行性剪枝，即当前的得分加上当前状态下可能得到的最大分，如果还不能够达到最优，那么就要剪枝。这道题看似不难，但有很多细节要处理。
这里参考了别人的代码，很多都是用dfs+剪枝。。关键还是位置移动的部分没有完全弄明白。。。
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int n,m,k;
int g[10][10];
int best;
int total;
int h[8]={1,-1,0,0,1,1,-1,-1};
int gg[8]={0,0,1,-1,1,-1,1,-1};int maxsum(){//计算此状态的最大获利（是一个剪枝）int res[10]={0},i,j;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(g[i][j])res[g[i][j]]++;int s=0;for(i=1;i<=k;i++)s+=res[i]*res[i];return s;
}void calsum(int u,int v,bool visit[10][10],int s){//DFS搜与某一点相邻的所有点int xx,yy,i;visit[u][v]=true;g[u][v]=0;total++;for(i=0;i<8;i++){xx=u+h[i];yy=v+gg[i];if(xx<=0 || xx>n || yy<=0 || yy>m)continue;if(!g[xx][yy] || visit[xx][yy])continue;if(g[xx][yy]!=s)continue;calsum(xx,yy,visit,s);}
}void change(){//根据题目要求需要没消一次方块就下移左移int k=n,i,j;bool flag[10]={0};for(i=1;i<=m;i++){k=n;for(j=n;j>=1;j--){g[k][i]=g[j][i];if(j<k)g[j][i]=0;if(g[k][i]){k--;flag[i]=true;}}}k=1;for(i=1;i<=m;i++){if(flag[i]){if(i>k){for(j=1;j<=n;j++){g[j][k]=g[j][i];g[j][i]=0;}}k++;}}
}void dfs(int now){//主搜函数bool visit[10][10];int i,j,p,q;int tem[10][10];if(maxsum()+now<=best)return;memcpy(tem,g,sizeof(tem));if(best<now)best=now;memset(visit,0,sizeof(visit));for(i=1;i<=n;i++)for(j=1;j<=m;j++){memcpy(g,tem,sizeof(g));total=0;if(g[i][j] && !visit[i][j]){ calsum(i,j,visit,g[i][j]);}if(total<3)continue;change();dfs(now+total*total);}
}int main(){int i,j;while(scanf("%d %d %d",&n,&m,&k)==3){for(i=1;i<=n;i++)for(j=1;j<=m;j++){scanf("%d",&g[i][j]);}best=0;dfs(0);printf("%d\n",best);}
}