[CF] 37 E. Trial for Chief

如果固定了一个中心，那么只需要考虑从它开始最远染到的那些点究竟染了几次。

上下左右不同的点连1边，相同的连0边，跑单源最短路就可以啦。

lyd讲的是统计到最远黑点+1的最小值，但是#58数据全是白点，嗯...应该这样考虑，黑点+1，白点不+1。

一开始数组开太大，导致memset时间暴增，没认真估计数据范围呢。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define id(x,y) (((x)-1)*m+(y))

using namespace std;

const int MAXN=;

inline int rd() {

    int ret=,f=;

    char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

int n,m;

struct Edge {

    int next,to,w;

} e[MAXN<<];

int ecnt,head[MAXN];

inline void add(int x,int y,int w) {

//    printf("Connect:(%d,%d) with (%d,%d) using %d\n",x/(m+1),x%(m+1),y/(m+1),y%(m+1),w);

    e[++ecnt].next = head[x];

    e[ecnt].to = y;

    e[ecnt].w = w;

    head[x] = ecnt;

//    e[++ecnt].next = head[y];

//    e[ecnt].to =x;

//    e[ecnt].w = w;

//    head[y] = ecnt;

}

char s[][];

int dx[]= {,,-,};

int dy[]= {,,,-};

int dis[MAXN],inq[MAXN];

queue<int> Q;

int cnt=;

int spfa(int st) {

    memset(dis,0x3f,sizeof(dis));

    int ret=;

    dis[st]=;

    Q.push(st);

    inq[st]=;

    while(!Q.empty()) {

        int top=Q.front();

        Q.pop();

        inq[top]=;

        for(int i=head[top]; i; i=e[i].next) {

            int v=e[i].to;

            if(dis[v]>dis[top]+e[i].w) {

                dis[v]=dis[top]+e[i].w;

                if(!inq[v]) Q.push(v),inq[v]=;

            }

        }

    }

    for(int i=;i<=n;i++) for(int j=;j<=m;j++)

    if(s[i][j]=='B') ret=max(ret,+dis[id(i,j)]);

    else ret=max(ret,dis[id(i,j)]);

    return ret;

}

int main() {

    n=rd();

    m=rd();

    for(int i=; i<=n; i++) {

        scanf("%s",s[i]+);

    }

    int x,y;

    for(int i=; i<=n; i++) {

        for(int j=; j<=m; j++) {

            for(int k=; k<=; k++) {

                x=i+dx[k],y=j+dy[k];

                if(x<||x>n||y<||y>m) continue;

                if(s[x][y]==s[i][j]) add(id(i,j),id(x,y),);

                else add(id(i,j),id(x,y),);

            }

        }

    }

    int ans=<<;

    for(int i=; i<=n; i++) {

        for(int j=; j<=m; j++) {

            ans=min(ans,spfa(id(i,j)));

        }

    }

    printf("%d",ans);

    cout<<endl;

    return ;

}