Phủ Sàn Bằng Các Thanh Thẳng · canuc80k4443

Cho một bảng $N \times M$ . Mỗi ô là:

.: ô sàn cần được phủ;
#: cột chắn, không được phủ.

Một viên gạch là một thanh thẳng kích thước $1 \times K$ hoặc $K \times 1$ , với $K$ là một số nguyên dương tùy ý. Mỗi viên phải nằm trọn trên các ô .. Các viên không được chồng lên nhau và mọi ô . phải được phủ đúng một lần.

Hãy tìm số viên gạch ít nhất cần dùng.

Input

Dòng đầu chứa $N$ $M$ .
$N$ dòng tiếp theo mô tả bảng, mỗi dòng gồm $M$ ký tự . hoặc #.

Output

In số viên gạch ít nhất.

Constraints

$1 \leq N, M \leq 10$ .
Có thể không có ô .; khi đó đáp án bằng $0$ .

Scoring

Subtask $1$ ( $50%$ số điểm): Có không quá $20$ ô ..
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2 2
..
..

Output

Giải thích: Có thể dùng hai thanh ngang dài $2$ , mỗi thanh phủ một hàng; hoặc dùng hai thanh dọc dài $2$ . Không thể dùng một thanh duy nhất vì thanh không được uốn cong.

Ý tưởng: Gán cho mỗi ô trống một trong hai hướng: ngang hoặc dọc. Các ô liên tiếp trên cùng hàng cùng mang hướng ngang tạo thành đúng một viên; tương tự theo cột cho hướng dọc. Vì vậy cần tối thiểu số lần bắt đầu một run.
Ý tưởng: Duyệt ô theo hàng. Mask M bit lưu hướng của M ô gần nhất, nên trước khi xử lý một ô ta biết hướng của ô trái và ô trên. Nếu chọn ngang, chi phí chỉ tăng khi không thể nối với ô trái; nếu chọn dọc, chi phí chỉ tăng khi không thể nối với ô trên. Ô # cắt cả hai loại run.
Ý tưởng: Độ phức tạp O(N·M·2^M) và bộ nhớ O(2^M).