这是一道sb题，但是考场时我犯了傻逼错误，导致打的程序非常麻烦非常长。
想法很简单，对于每种颜色维护一个前向星，表示与当前联通块相连通且颜色为i的连通块。
然后每次找到这个连通块，暴力将这个连通块连向的点继续丢进桶里，因为每个连通块最多进一次桶，每个位置最多遍历一次，所以可以保证时间复杂度。
#include<cstdio> #include<cstring> #include<map> #include<algorithm> #define N 1010 #define M N*N using namespace std; int n,m,Q,k,x,y,i,j,s[N][N],cnt,tot,bz[N][N],q[M],sum[M],fa[N][N][3],fp[M][3],ans,bzk[N][N],fx[5][3],bzp[M]; struct edge{ int to,next; }e[M*10]; void dfs(int x,int y){ bz[x][y]=cnt; sum[cnt]++; int i,xx,yy; for (i=1;i<=4;i++){ xx=x+fx[i][1];yy=y+fx[i][2]; if (xx>0&&yy>0&&xx<=n&&yy<=m&&s[x][y]==s[xx][yy]&&bz[xx][yy]==0) fa[xx][yy][1]=x,fa[xx][yy][2]=y,dfs(xx,yy); } } void insert(int x,int y){ tot++; e[tot].to=y; e[tot].next=q[x]; q[x]=tot; } void solve(int x,int y){ int i,xx,yy; for (i=1;i<=4;i++){ xx=x+fx[i][1];yy=y+fx[i][2]; if (xx>0&&yy>0&&xx<=n&&yy<=m){ if (fa[xx][yy][1]==x&&fa[xx][yy][2]==y) solve(xx,yy); if (bzp[bz[xx][yy]]||s[xx][yy]==s[x][y]) continue; bzp[bz[xx][yy]]=1; insert(s[xx][yy],bz[xx][yy]); } } } int main(){ freopen("color.in","r",stdin); freopen("color.out","w",stdout); fx[1][1]=1;fx[1][2]=0; fx[2][1]=-1;fx[2][2]=0; fx[3][1]=0;fx[3][2]=1; fx[4][1]=0;fx[4][2]=-1; scanf("%d%d%d%d",&n,&m,&Q,&k); for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&s[i][j]); for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (!bz[i][j]){ cnt++; fp[cnt][1]=i;fp[cnt][2]=j; dfs(i,j); } bzp[1]=1; solve(1,1); ans=sum[1]; while (Q--){ scanf("%d",&x); for (i=q[x];i;i=e[i].next){ y=e[i].to; ans+=sum[y]; solve(fp[y][1],fp[y][2]); } q[x]=0; printf("%d ",ans); } return 0; }