[BZOJ2638] 黑白染色

2638: 黑白染色

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 174 Solved: 85
[Submit][Status][Discuss]

Description

　你有一个n*m的矩形，一开始所有格子都是白色，然后给出一个目标状态的矩形，有的地方是白色，有的地方是黑色，你每次可以选择一个连通块（四连通块，且不要求颜色一样）进行染色操作（染成白色或者黑色）。问最少操作次数。

Input

　　第一行两个数n，m表示矩形大小。
　　接下来n行描述目标状态，每行m个字符，’W’表示白色，’B’表示黑色。

Output

　　一行一个整数表示操作数。

Sample Input

3 3
WBW
BWB
WBW

Sample Output

HINT

数据规模和约定

　　100%的数据n<=50,m<=50

　　15%的数据n*m<=15

　　另外15%的数据m=1

Source

缩点后枚举起点找最小深度

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 int n,m;
 9 char s[100][100];
10 int a[100][100],dis[101][101],maxn,tmp=0;
11 int tox[5]={1,0,-1,0};
12 int toy[5]={0,-1,0,1};
13 bool vis[101][101];
14 struct data {
15     int x,y;
16 }q[10000];
17 int check(int x,int y) {
18     memset(dis,67,sizeof(dis));
19     maxn=0;
20     dis[x][y]=0;
21     int h=0,t=1;
22     q[0]=(data){x,y};
23     while(h!=t) {
24         int X=q[h].x,Y=q[h].y;h++;if(h==5000) h=0;
25         for(int i=0;i<4;i++) {
26             int tx=X+tox[i],ty=Y+toy[i];
27             if(tx<=0||ty<=0||tx>n||ty>m) continue;
28             if(dis[tx][ty]>dis[X][Y]+(a[X][Y]^a[tx][ty])) {
29                 dis[tx][ty]=dis[X][Y]+(a[X][Y]^a[tx][ty]);
30                 if(!vis[tx][ty]) {q[t++]=(data){tx,ty};vis[tx][ty]=1;if(t==5000) t=0;}
31             }
32         }
33         vis[X][Y]=0;
34     }
35     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) maxn=max(maxn,dis[i][j]);
36     return maxn;
37 }
38 int main() {
39     scanf("%d%d",&n,&m);
40     for(int i=1;i<=n;i++) {
41         scanf("%s",s[i]+1);
42         for(int j=1;j<=m;j++) if(s[i][j]=='B') a[i][j]=1;else tmp++;
43     }
44     if(tmp==n*m) {printf("0
");return 0;}
45     int ans=2147483647;
46     for(int i=1;i<=n;i++)
47         for(int j=1;j<=m;j++) ans=min(ans,check(i,j));
48     printf("%d
",ans+1);
49 }

View Code