Trạm Tín Hiệu Trên Lưới · canuc80k4405

Một khu vực được chia thành $N$ hàng và $M$ cột. Mỗi ô mang một trong hai ký tự:

$P$ : có thể đặt một trạm tín hiệu;
$H$ : bị che chắn, không thể đặt trạm.

Hai trạm gây nhiễu cho nhau nếu chúng nằm trên cùng một hàng hoặc cùng một cột và khoảng cách giữa hai ô bằng $1$ hoặc $2$ . Hãy đặt nhiều trạm nhất có thể sao cho không có hai trạm nào gây nhiễu cho nhau.

Input

Dòng đầu chứa hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo, mỗi dòng là một xâu gồm $M$ ký tự $P$ hoặc $H$ , mô tả một hàng của khu vực.

Output

In số trạm lớn nhất có thể đặt.

Constraints

$1 \leq N \leq 100$ .
$1 \leq M \leq 10$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 8$ và $M \leq 6$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3 5
PHPHP
PPPPP
HPHPH

Output

Giải thích: Có thể đặt trạm tại các ô $(1, 3), (2, 2), (2, 5)$ và $(3, 4)$ . Không thể đặt thêm trạm nào mà vẫn tránh mọi cặp cùng hàng hoặc cùng cột cách nhau không quá hai ô.

Ý tưởng: Mỗi hàng được biểu diễn bằng một mask. Một mask hợp lệ không có hai bit 1 cách nhau một hoặc hai cột. Khi chọn mask cho hàng hiện tại, ngoài việc mask phải nằm hoàn toàn trên các ô P, nó còn phải không giao với mask của cả hàng trước và hàng cách hai hàng.
Ý tưởng: Dùng dp[prev][older] lưu số trạm lớn nhất sau phần lưới đã xét, trong đó prev và older là hai mask gần nhất. Thử mọi cur hợp lệ rồi chuyển sang trạng thái (cur, prev).
Đúng đắn: Điều kiện khi sinh mask loại chính xác mọi cặp xung đột trong cùng hàng. Hai trạm ở các hàng khác nhau chỉ có thể xung đột khi cách nhau một hoặc hai hàng và cùng cột, nên kiểm tra cur với prev và older là đủ. Mỗi cách đặt hợp lệ tạo ra đúng một dãy mask; quy nạp theo hàng cho thấy DP giữ giá trị lớn nhất cho mọi trạng thái biên.
Độ phức tạp: Gọi V là số mask hợp lệ của một hàng. Thời gian O(N·V³), bộ nhớ O(V²); với M ≤ 10, V nhỏ.