zoj3781

zoj3781
赛场上堵在了缩点上emmmmm
把原始图相同颜色的方块缩成一个点,然后与它周围不同颜色的联通块连双向边,然后枚举每个点然后求最大深度的最小值
因为每次翻转都相当于深度+1(可以手动模拟一下

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 100010
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std;
int T;
int n,m;
int deep[];
char a[][];
bool b[][];
int col[][];
bool vis[][],v[];
int cnt;
int ans;
queue<int>q; struct node{
int n;
node *next;
}*e[]; void in(int &x){
int y=;
char c=g();x=;
while(c<''||c>''){
if(c=='-')y=-;
c=g();
}
while(c<=''&&c>=''){
x=(x<<)+(x<<)+c-'';c=g();
}
x*=y;
}
void o(int x){
if(x<){
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} void clean(){
For(i,,n)
For(j,,m){ vis[i][j]=;
col[i][j]=;
}
For(i,,n*m)
For(j,,n*m){
b[j][i]=;
b[i][j]=;
} For(i,,)
e[i]=;
cnt=;
ans=inf; } void push(int x,int y){
node *p;
p=new node();
p->n=y;
if(e[x]==)
e[x]=p;
else{
p->next=e[x]->next;
e[x]->next=p;
}
} void dfs(int x,int y,char f,int color){
if(x<||y<||x>n||y>m)
return;
if(vis[x][y])
return;
if(a[x][y]==f){
vis[x][y]=;
col[x][y]=color;
dfs(x-,y,f,color);
dfs(x,y-,f,color);
dfs(x,y+,f,color);
dfs(x+,y,f,color);
}
} void ccc(int x,int y){
if(x<||y<||x>n||y>m)
return;
vis[x][y]=;
if(x->&&!b[col[x][y]][col[x-][y]]){
if(col[x][y]!=col[x-][y]){
push(col[x][y],col[x-][y]);
push(col[x-][y],col[x][y]);
b[col[x][y]][col[x-][y]]=;
b[col[x-][y]][col[x][y]]=;
}
if(vis[x-][y])
ccc(x-,y);
}
if(y->&&!b[col[x][y]][col[x][y-]]){
if(col[x][y]!=col[x][y-]){
push(col[x][y],col[x][y-]);
push(col[x][y-],col[x][y]);
b[col[x][y]][col[x][y-]]=;
b[col[x][y-]][col[x][y]]=;
}
if(vis[x][y-])
ccc(x,y-);
}
if(x+<=n&&!b[col[x][y]][col[x+][y]]){
if(col[x][y]!=col[x+][y]){
push(col[x][y],col[x+][y]);
push(col[x+][y],col[x][y]);
b[col[x][y]][col[x+][y]]=;
b[col[x+][y]][col[x][y]]=;
}
if(vis[x+][y])
ccc(x+,y);
}
if(y+<=m&&!b[col[x][y]][col[x][y+]]){
if(col[x][y]!=col[x][y+]){
push(col[x][y],col[x][y+]);
push(col[x][y+],col[x][y]);
b[col[x][y]][col[x][y+]]=;
b[col[x][y+]][col[x][y]]=;
}
if(vis[x][y+])
ccc(x,y+);
}
} void bfs(int x){
deep[x]=;
q.push(x);
For(i,,cnt)
v[i]=;
v[x]=;
int ss=;
while(!q.empty()){
int t=q.front();q.pop();
for(node *i=e[t];i;i=i->next)
if(!v[i->n]){
v[i->n]=;
q.push(i->n);
deep[i->n]=deep[t]+;
ss=max(ss,deep[i->n]);
}
}
ans=min(ss,ans);
} int main(){
in(T);
while(T--){
in(n);in(m);
clean();
For(i,,n)
For(j,,m)
cin>>a[i][j];
For(i,,n)
For(j,,m)
if(!vis[i][j])
dfs(i,j,a[i][j],++cnt);
ccc(,);
For(i,,cnt)
bfs(i);
o(ans);p('\n');
}
return ;
}
上一篇:jvm 线程实现机制


下一篇:自然语言处理hanlp的入门基础