[USACO JAN14]建造滑雪场

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file skicourse.in Output file skicourse.out

【题目描述】


奶牛界的冬奥会即将开始,FJ正在帮忙把他巨大的牧场变成一个滑雪场地。这块地的尺寸为M*N(1<= M,N <=100),而最终的设想是把它变成一个M*N的由字符标记的网格,例如:

RSRSSS

RSRSSS

RSRSSS

每个字符表示该单元格里雪的光滑情况:字符'R'表示粗糙,字符'S'表示光滑,奶牛奥运会的组织者们认为滑雪场地中粗糙和光滑两种地形掺杂着,滑雪才会变得更有趣。

为了建成符合要求的场地,FJ决定要改进一下他的拖拉机,使其能像着盖印章一样一次压出来一个B*B(B <= M, B <= N)的区域,压过的地面要么全是光滑的,要么全是粗糙的。由于在每一次“盖章”期间重启拖拉机要等很久,因此FJ希望B越大越好。

当B=1时,显然他可以把任一个单元格都变成R或者S的,然而当B变大时,就不一定能建成符合要求的场地了。场地中的每一个单元格都必须要被FJ的拖拉机压过,不能有一个遗漏。

请帮FJ确定能成功完成任务的B的最大值。


【输入格式】


输入格式:

第1行:两个由空格隔开的整数M,N;

第2~M+1行:每行有N个字符(R或S),表示预期的滑雪场地。


【输出格式】

仅一行,即B的最大值。

【样例输入】

3 6 
RSRSSS 
RSRSSS 
RSRSSS 

【样例输出】

3

输出解释:
先把1-3列压成全R的,再把2-4列压成全S的,再把3-5列压成全R的,最后把4-6列压成全S的。

【提示】

在此键入。

【来源】

在此键入。