思路：为了方便，当c1>c2时将0变为1，1变为0.
空格最多有10个，每个空格有3个状态，如果不状态压缩，会TLE的。所以最多有3^10种情况
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#define inf 1<<30
using namespace std;
struct point
{
int x,y;
point(){}
point(int _x,int _y):x(_x),y(_y){}
}pos[],s;
int move[][]={{-,},{,},{,-},{,}};
char str[][];
int x,y,n,sum,ret,dp[],p[];
map<int ,int>mm;
bool vis[][];
void dfs(int x,int y)
{
if(vis[x][y]) return ;
vis[x][y]=;
sum++;
for(int i=;i<;i++){
int a=x+move[i][];
int b=y+move[i][];
if(a>=&&a<n&&b>=&&b<n&&!vis[a][b]&&str[x][y]==str[a][b])
dfs(a,b);
}
}
int get_score()
{
memset(vis,,sizeof(vis));
int t1=,t2=;
for(int i=;i<n;i++)
for(int j=;j<n;j++){
if(!vis[i][j]){
sum=;
dfs(i,j);
if(str[i][j]=='') t1=max(t1,sum);
else t2=max(t2,sum);
}
}
return t1-t2;
}
int minimax(int ,int ,int ,int);
int maxmini(int state,int now,int d,int mi)
{
if(!state) return get_score();
if(dp[now]!=-inf) return dp[now];
int ma=-inf,st=state,k,j;
while(st){ //枚举所有的1的情况，也就是'.'的情况
k=st&(-st); // 找到st倒数第一个1
j=mm[k]; //1的位置
str[pos[j].x][pos[j].y]='';
int t=minimax(state-k,now+p[j],d+,ma);
str[pos[j].x][pos[j].y]='.';
ma=max(ma,t);
if(ma>=mi) return ma;
if(d==){ //更新结果
if(ret<ma||(ret==ma&&(s.x>pos[j].x||(s.x==pos[j].x&&s.y>pos[j].y)))){
s=pos[j];
ret=ma;
}
}
st-=k; //继续枚举下一个1
}
return dp[now]=ma;
}
int minimax(int state,int now,int d,int ma)
{
if(!state) return get_score();
if(dp[now]!=-inf) return dp[now];
int mi=inf,k,st=state,j;
while(st){
k=st&(-st);
j=mm[k];
str[pos[j].x][pos[j].y]='';
int t=maxmini(state-k,now+*p[j],d+,mi);
str[pos[j].x][pos[j].y]='.';
mi=min(mi,t);
if(mi<=ma) return mi;
st-=k;
}
return dp[now]=mi;
}
int main()
{
// freopen("1.txt","r",stdin);
p[]=;
for(int i=;i<=;i++) p[i]=*p[i-];
for(int i=;i<=;i++) mm[(<<i)]=i;
while(scanf("%d",&n)&&n){
int c1=,c2=,num=;
for(int i=;i<n;i++){
scanf("%s",str[i]);
for(int j=;j<n;j++){
if(str[i][j]=='') c1++;
else if(str[i][j]=='') c2++;
else pos[num++]=point(i,j);
}
}
if(c1>c2){ //始终让0先走
for(int i=;i<n;i++)
for(int j=;j<n;j++){
if(str[i][j]=='') str[i][j]='';
else if(str[i][j]=='') str[i][j]='';
}
}
for(int i=;i<p[num];i++) dp[i]=-inf;
ret=-inf;
maxmini((<<num)-,,,inf);
printf("(%d,%d) %d\n",s.x,s.y,ret);
}
return ;
}