Công ty LDK đang sản xuất robot vận chuyển hàng hóa tự động trên mặt phẳng. Để làm việc đó, công ty tiến hành huấn luyện các robot trên một địa hình phẳng được chia thành một lưới các ô vuông gồm dòng (đánh số từ đến theo chiều từ trên xuống dưới) và cột (đánh số từ đến theo chiều từ trái sang phải). Ô giao giữa dòng , cột được gọi là ô và thuộc một trong loại dưới đây:
Ô xuất phát, kí hiệu là
Ô kết thúc, kí hiệu là
Ô trồng, kí hiệu là
Ô cắm, kí hiệu là
Ô kém chất lượng, kí hiệu là
Một đường thử nghiệm cho robot là một dãy liên tiếp các ô chung cạnh, bắt đầu tại một ô , kết thúc tại một ô và thỏa mãn các điều kiện sau:
Không chứa ô cấm;
Không chứa ô nào khác;
Số ô kém chất lượng không quá một ô.
Yêu cầu: Cho biết thông tin các ô của lưới, hãy giúp công ty tìm phương án thiết kế có nhiều đường thử nghiệm nhất mà mỗi ô của lưới thuộc không quá một đường thử nghiệm.
Dữ liệu vào:
Dòng thứ nhất chứa một số nguyên dương ;
Dòng thứ trong số dòng tiếp theo chứa xâu mô tả thông tin các ô liên tiếp trên hàng thứ của lưới.
Dữ liệu ra:
Ghi ra một số nguyên là số đường thử nghiệm nhiều nhất tìm được.
Ví dụ:
Dữ liệu vào:
10
T.*S..##S#
**###T#T.S
.*S.*.##T#
Dữ liệu ra:
3
Giới hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: , không có ô kém chất lượng và các ô thuộc hàng và hàng của địa hình đều là ô cấm;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: và địa hình không có ô kém chất lượng;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: và các ô thuộc hàng của địa hình đều là ô cấm;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: và không có điều kiện gì thêm trên địa hình.
