2
分析：1.把相通且颜色相同的的联通块缩成一个点
2.把相连的联通块之间连边
3.以每个点为根，bfs求树的深度，最小的深度即为最少的翻转次数
技能：1.有环的图求“直径”不能用dfs
2.矩阵初始化边界注意 0~n+1
代码：
#include<bits/stdc++.h> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;++i) #define dep(i,j,k) for (int i=j;i>=k;--i) #define to e[i].v #define Cl(a) memset(a,0,sizeof(a)) #define N 60 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; struct node{ int v,next; }e[N*N*2]; bool vis[N][N],link[N*N][N*N],v[N*N]; int a[N][N],dist[N*N],head[N*N],q[N*N]; int id,scc,n,m,pos,t; char s[N]; int read() { int f=1,x=0;char ch=getchar(); for (;ch>'9'||ch<'0';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; } void dfs(int x,int y,int scc,int pd) { vis[x][y]=1; a[x][y]=scc; rep(i,0,3) { int nx=x+dx[i],ny=y+dy[i]; if (a[nx][ny]==pd && !vis[nx][ny]) dfs(nx,ny,scc,pd); } } void bfs(int u) { int l=0,r=1; for (v[q[1]=u]=1,dist[u]=0;l^r;) for (int i=head[u=q[++l]];i;i=e[i].next) if (!v[to]) v[q[++r]=to]=1,dist[to]=dist[u]+1; } void add(int u,int v) { e[id].v=v; e[id].next=head[u]; head[u]=id++; } int main() { t=read(); for (;t--;) { n=read(); m=read(); rep(i,0,n+1) rep(j,0,m+1) a[i][j]=-1,vis[i][j]=0; Cl(head); Cl(link); rep(i,1,n) { scanf("%s",s+1); rep(j,1,m) if (s[j]=='X') a[i][j]=1; else a[i][j]=0; } scc=0; rep(i,1,n) rep(j,1,m) if (!vis[i][j]) { ++scc; dfs(i,j,scc,a[i][j]); } // rep(i,1,n) {rep(j,1,m) printf("%d ",a[i][j]);puts("");} id=1; rep(i,1,n) rep(j,1,m) { int x=i+1,y=j; if ((x<=n) && (a[i][j]^a[x][y]) && (!link [a[i][j]] [a[x][y]])) { add(a[i][j],a[x][y]); add(a[x][y],a[i][j]); link [a[i][j]] [a[x][y]] = link [a[x][y]] [a[i][j]] = 1; } x=i,y=j+1; if ((y<=m) && (a[i][j]^a[x][y]) && (!link [a[i][j]] [a[x][y]])) { add(a[i][j],a[x][y]); add(a[x][y],a[i][j]); link [a[i][j]] [a[x][y]] = link [a[x][y]] [a[i][j]] = 1; } } // Cl(v); bfs(1); dist[0]=-1; pos=0; rep(i,1,scc) if (dist[i]>dist[pos]) pos=i; // Cl(v); bfs(pos); dist[0]=-1; pos=0; rep(i,1,scc) if (dist[i]>dist[pos]) pos=i; int as=1234567890; rep(i,1,scc) { Cl(v); bfs(i); dist[0]=-1; pos=0; rep(j,1,scc) if (dist[j]>dist[pos]) pos=j; as=min(as,dist[pos]); } printf("%d\n",as); } return 0; }
