记录编号	144642	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]黑白染色	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.495 s
提交时间	2014-12-25 07:53:41	内存使用	0.48 MiB

/****************************************\
* Author : hzoi_ztx
* Title  :
* ALG    :
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH ;

inline void read(int& ret) {
    ret = 0 ; while (CH=getchar() , CH<'!') ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

#include <cstring>

#define  maxn  2600LL
#define  maxe  10500LL
#define  infi  0x3f3f3f3fLL
#define  min(x,y) ((x)<(y)?(x):(y))

struct FST { int to , next , w ; } e[maxe] ;
int star[maxn] = {0} , tote = {0} ;
inline void AddEdge(int u , int v , int w) {
	e[++tote].to = v ; e[tote].w = w ; e[tote].next = star[u] ; star[u] = tote ;
}

const int dx[4] = {1 , -1 , 0 , 0} ,
          dy[4] = {0 , 0 , 1 , -1} ;

int n , N , M ;
int dis[maxn] = {0} ;
bool black[maxn] = {0} , inq[maxn] = {0} ;

inline int hash(int i , int j) { return (i-1)*M+j ; }

#define  sizeque  20000LL
int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; } 
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; } 
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }

int p , t , ret ;
inline int SPFA(int s) {
	memset(dis , 0x3f , sizeof(dis)) ; clear() ;
	inq[s] = dis[s] = 1 ; push_back(s) ;
	while (!empty()) {
		s = front() , pop_front() ; inq[s] = false ;
		for (p = star[s] ; p ; p = e[p].next) {
			t = e[p].to ;
			if (dis[s]+e[p].w < dis[t]) {
				dis[t] = dis[s]+e[p].w ;
				if (!inq[t]) {
					inq[t] = true ;
					if (!empty() && dis[t]<dis[front()]) push_front(t) ;
					else push_back(t) ;
				}
			}
		}
	}
	ret = -infi ;
	for (t = 1 ; t <= n ; t ++ )
		if (black[t] && ret<dis[t]) ret = dis[t] ;
	return ret ;
}

int main() {
int i , j , d , ii , jj , ans ;
	#define READ
	#ifdef  READ
		freopen("nt2012_paint.in" ,"r",stdin ) ;
		freopen("nt2012_paint.out","w",stdout) ;
	#endif
	read(N) , read(M) ;
	n = N*M ;
	for (i = 1 ; i <= N ; i ++ ) {
		while (CH=getchar() , CH<'!') ;
		for (j = 1 ; j <= M ; j ++ , CH = getchar() )
			black[hash(i,j)] = CH=='B' ;
	}
	for (i = 1 ; i <= N ; i ++ )
		for (j = 1 ; j <= M ; j ++ )
			for (d = 0 ; d < 4 ; d ++ ) {
				ii = i+dx[d] , jj = j+dy[d] ;
				if (ii<1 || ii>N || jj<1 || jj>M) continue ;
				AddEdge(hash(i,j) , hash(ii,jj) , black[hash(i,j)]^black[hash(ii,jj)]) ;
			}
	ans = infi ;
	for (i = 1 ; i <= n ; i ++ ) ans = min(ans , SPFA(i)) ;
	printf("%d\n", ans ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}