Xây Dựng Đường Trượt Tuyết

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một khu vực trượt tuyết gồm $M \times N$ ô vuông, mỗi ô có trạng thái 'R' (gồ ghề) hoặc 'S' (mịn). Để tạo ra khu vực này, người ta dùng một con dấu hình vuông kích thước $B \times B$ . Mỗi lần đóng dấu, toàn bộ vùng $B \times B$ được tô một màu duy nhất ('R' hoặc 'S'). Con dấu có thể đặt chồng lên nhau, và lần đóng sau sẽ ghi đè lên lần đóng trước.

Yêu cầu: mỗi ô phải được đóng dấu ít nhất một lần. Tìm giá trị $B$ lớn nhất để có thể tạo ra đúng bản đồ đã cho.

Dữ liệu vào

Dòng 1: Hai số nguyên $M$ và $N$ ( $1 \leq M, N \leq 100$ ).
$M$ dòng tiếp theo: mỗi dòng gồm $N$ ký tự 'R' hoặc 'S'.

Dữ liệu ra

Một số nguyên duy nhất — giá trị $B$ lớn nhất có thể.

Ràng buộc

$1 \leq M, N \leq 100$

Ví dụ

Input	Output	Giải thích
3 6 RSRSSS RSRSSS RSRSSS	3	Có thể dùng con dấu $3 \times 3$ : đóng vùng cột 4–6 bằng 'S', rồi đóng vùng cột 1–3 bằng 'R', rồi đóng các vùng khác. B=4 không khả thi vì một vùng $4 \times 4$ bất kỳ đều chứa cả 'R' lẫn 'S'.
4 4 RRSS RRSS SSRR SSRR	2	B=2: đóng $(0, 0)$ bằng 'R', $(0, 2)$ bằng 'S', $(2, 0)$ bằng 'S', $(2, 2)$ bằng 'R'. B=3 không khả thi vì mọi vùng $3 \times 3$ đều chứa cả hai màu.

Bình luận

Không có bình luận tại thời điểm này.