Elearning CodePath – CTP Online Judge

Ăn tối

DINNER

🟢 Hard #Stack #Data Structure

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một căn phòng hình chữ nhật kích thước $R \times C$ được mô tả bằng lưới. Mỗi ô trong lưới có thể là ô trống (`.`) hoặc ô đã kê đồ (`X`).

Mirko muốn đặt một **bàn gỗ hình chữ nhật** vào các ô trống. Bàn chỉ được đặt vào các ô có ký tự `.`.

Nếu bàn có kích thước chiều rộng $W$ và chiều cao $H$:
* **Chu vi** của bàn (số người có thể ngồi) là $P = 2(W + H)$.
* Kích thước $W$ và $H$ được tính bằng số ô vuông.

Hãy xác định cái bàn lớn nhất có thể biết rằng bàn luôn được kê sao cho cạnh của nó song song với tường của căn phòng.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `DINNER.INP`:

* Dòng 1: Hai số nguyên $R$ và $C$ (kích thước căn phòng).
* $R$ dòng tiếp theo: Mỗi dòng chứa $C$ ký tự (`.` là ô trống, `X` là ô đã kê đồ).

Giới hạn:
* $1 \le R, C \le 400$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `DINNER.OUT` một số nguyên duy nhất là số khách tối đa mà Mirko có thể mời đến ăn tối.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `2 2` `..` `..` | **7** |
| `4 4` `X.XX` `X..X` `..X.` `..XX` | **9** |
| `3 3` `X.X` `.X.` `X.X` | **3** |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $R, C \le 50$ | $40\%$ |
| 2 | $R, C \le 400$ | $60\%$ |

---

✅ Đã AC: 4 / 9 submissions