这题我出的，因为邀请赛时候出了道题意有点问题的模板题，所以这次决定出一道题意清楚的非模板题。
那天躺在床上玩ipad，突然玩到了《终极宝石》，于是乎就动了给这个游戏写外挂的想法，也就变成了一道题，本来是想出给网赛的，但谁知道最后变成了现场赛题目。
judge们看了现场赛最后的题目之后，给这题定为的是第三题，结果由于题目太长＋水题太坑＋神队带歪了board，这题最后也没几个人过。。。
其实就是一道搜索而已，而且数据很小，时限很松，随手加点剪枝就可以过。
这题明显不存在局部最优解，所以我们想到的解题方法是模拟+搜索+剪枝。
模拟+搜索：对于每一个局面，用bfs穷举出下一步所有可能存在的消除宝石的方法，每发现这样的一个方法就dfs进入下一层。
（即通过floodfill的方法进行bfs，每得到一个大小大于2的连通块的时候就dfs递归深入下去。这样可以让下面的剪枝得到很好的效果，可以将搜索树的size大大减小。）
剪枝：对于每一个局面，记录它通过之前的步骤已经得到的分数，然后维护它还可能得到的最大的分数（比如已经得到了120分，还有5个红色宝石，4个蓝色宝石，2个黑色宝石，那此局面可能得到的分数一定不超过120+5*5+4*4），通过用这个分数与当前已经得到的最大分数进行比较来进行剪枝。对于大多数数据这个剪枝能剪掉99.9%的节点，所以有时可以跑过10*9的数据，但是这个剪枝也是不稳定的，存在不少数据能把它卡掉。不过对于题目的最大上限8*8，这个剪枝已经足够了。
至于整体的复杂性分析等我有空或者哪位大牛有空可以详细写一下，在这里就不写出了。
我在当judge的时候看到最快的做法是除了以上剪枝之外，还把当前局面hash掉，每次判一下hash，虽然常数会稍微增大，但是重复状态会减少很多。没准加了hash之后可以跑过原来游戏中12*12的解也未可知呢。
话说自己写的标被挂掉了，因为常数太大。。。我在这里就放出我的小队友claire大神的标吧。等我有空也许会去写一份加上神优化hash的标呢。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=14;
int a[N][N],v[N][N],t[N];
int d[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
int m,n,o,ans;
int bfs(int p,int q,int a[][N],int id[][N],int w)
{
int f[N*N][2];
int i,l=1,r=1,x,y;
f[1][0]=p; f[1][1]=q;
v[p][q]=1;
while (l<=r)
{
p=f[l][0]; q=f[l][1];
id[p][q]=w;
for (i=0; i<8; i++)
{
x=p+d[i][0];
y=q+d[i][1];
if (x>=1 && x<=m && y>=1 && y<=n && a[x][y]==a[p][q] && v[x][y]==0)
{
r++; v[x][y]=1;
f[r][0]=x; f[r][1]=y;
}
}
l++;
}
return r;
}
void change(int b[][N])
{
int temp1[N],temp2[N],i,j,x,y,s=0;
for (j=1; j<=n; j++)
{
x=0; y=m;
for (i=1; i<=m; i++)
if (b[i][j]>0) temp1[++x]=i;
if (x>0) temp2[++s]=j;
while (x>0)
{
if (y!=temp1[x]){ b[y][j]=b[temp1[x]][j]; b[temp1[x]][j]=0;}
x--;
y--;
}
}
x=1; y=1;
while (x<=s)
{
if (y!=temp2[x]) for (i=1; i<=m; i++) {b[i][y]=b[i][temp2[x]]; b[i][temp2[x]]=0;}
x++;
y++;
}
}
void dfs(int s,int a[][N],int sum)
{
if (s>ans) ans=s;
int c[N*N],e[N*N],id[N][N]={0},w=0;
memset(v,0,sizeof(v));
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
if (a[i][j]>0 && t[a[i][j]]>=3 && v[i][j]==0 )
{
w++;
c[w]=bfs(i,j,a,id,w);
e[w]=a[i][j];
}
int b[N][N];
for (int k=1; k<=w; k++)
if (c[k]>=3)
{
int sum1=sum-t[e[k]]*t[e[k]];
if (t[e[k]]-c[k]>=3) sum1=sum1+(t[e[k]]-c[k])*(t[e[k]]-c[k]);
if (sum1+s+c[k]*c[k]>ans)
{
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
if (id[i][j]==k)
b[i][j]=0; else b[i][j]=a[i][j];
change(b);
t[e[k]]-=c[k];
dfs(s+c[k]*c[k],b,sum1);
t[e[k]]+=c[k];
}
}
}
int main()
{
int i,j,k;
while (scanf("%d%d%d",&m,&n,&o)==3)
{
int sum=0;
memset(t,0,sizeof(t));
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
t[a[i][j]]++;
}
for (int i=1; i<=o; i++)
if (t[i]>=3) sum+=t[i]*t[i];
ans=0;
dfs(0,a,sum);
printf("%d\n",ans);
}
}