[Usaco2014 Jan]Building a Ski Course

时间限制:10s      空间限制:128MB

题目描述

 Farmer John is helping to turn his large field into a ski course for the upcoming winter Moolympics. The field has dimensions M x N (1 <= M,N <= 100), and its intended final composition is described by an M x N grid of characters like this: RSRSSS RSRSSS RSRSSS Each character describes how the snow in a unit square of the field should be groomed: either 'R' for 'rough' or 'S' for 'smooth' (the Moolympics organizers think that a course is more interesting if it has a mixture of rough and smooth patches). To build the desired course, Farmer John plans to modify his tractor so that it can stamp any B x B patch of the field (B <= M, B <= N) with either entirely smooth snow or entirely rough snow. Since it takes a long time to reset the tractor between each of these stamps, FJ wants to make B as large as possible. With B = 1, he can clearly create the desired ski course by stamping each individual square with either R or S, as intended. However, for larger values of B, it may no longer be possible to create the desired course design. Every unit square of the course must at some point be stamped by FJ's tractor; it cannot be left in its default state. Please help FJ determine the largest possible value of B he can successfully use.

定一个n*m的矩阵的目标状态(每个格子是R或S的一种),初始时格子状态未知,为了达到目标状态,你可以选择一个数b,可以多次将一个b*b的的子矩阵全部改成R或S,问能从初始达成目标状态的最大的b是多少。注意每个格子至少要被修改一次。


输入格式

* Line 1: Two space-separated integers M and N.

* Lines 2..M+1: M lines of exactly N characters (each R or S), describing the desired ski course design.


输出格式

* Line 1: The maximum value of B Farmer John can use to create the desired course pattern.


样例输入

3 6 
RSRSSS 
RSRSSS 
RSRSSS

样例输出

3 

OUTPUT DETAILS: FJ can stamp a rough patch spanning columns 1-3, followed by a smooth
 patch spanning columns 2-4, then a rough patch spanning columns 3-5, and finally a smooth 
patch spanning columns 4-6.

提示

没有写明提示


题目来源

Gold