Elearning CodePath – CTP Online Judge

GAME (game.\*)

GAME_GAME

🟢 Hard #String #Graph #Dynamic Programming #Simulation

## 💻 Đề Bài:

### 📌 **Thông tin chương trình**

---

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

Một trò chơi trên một bảng chữ kích thước $3 \times N$. Các dòng được đánh số từ $1$ đến $3$, các cột được đánh số từ $1$ đến $N$. Ô nằm ở dòng $i$ và cột $j$ được gọi là ô $A_{i,j}$. Mỗi ô chứa một kí tự từ 'a' đến 'z'.

**Luật chơi:**

1.  **Bắt đầu:** Người chơi chọn một ô xuất phát $A_{i_1, 1}$ (cột 1) và nhận được xâu $S$ gồm kí tự $A_{i_1, 1}$.
2.  **Di chuyển:** Mỗi lượt, người chơi có thể:
    * Thông báo kết thúc việc di chuyển.
    * Chọn một ô $A_{i_2, j+1}$ (cột tiếp theo bên phải, $j+1$) **chung cạnh hoặc chung đỉnh** với ô hiện tại $A_{i_1, j}$ để di chuyển.
3.  **Cập nhật xâu:** Kí tự ở ô di chuyển đến sẽ được thêm vào cuối xâu $S$.

**Yêu cầu:** Cho bảng chữ, hãy tìm cách chơi để nhận được xâu $S$ là **xâu đối xứng dài nhất**.

### 📥 **Định dạng Input**

* **Dòng 1:** Chứa số nguyên $N$ ($1 \le N \le 1000$).
* **3 dòng tiếp theo:** Mỗi dòng chứa $N$ kí tự từ 'a' đến 'z', mô tả bảng chữ (3 hàng).

**Giới hạn:**
$$1 \le N \le 1000$$

### 📤 **Định dạng Output**

Gồm một dòng chứa một số là **độ dài xâu $S$ là xâu đối xứng dài nhất** tìm được.

### ✨ **Ví dụ**

| Input | Output |
| :--- | :--- |
| **8** | **6** |
| dazympah | |
| dxbznbnh | |
| dyxccmph | |

---

#### **Subtask 1 ($N \le 10\%$)**

* Sử dụng **Quy hoạch động**.
    * **Cấu trúc dữ liệu:** Mảng **4 chiều** ($N \times 3 \times N \times 3$).

#### **Subtask 2 ($N \le 1000$)**

* Tiếp tục sử dụng **Quy hoạch động** nhưng phải tối ưu hóa.
    * **Cấu trúc dữ liệu:** Mảng **3 chiều** ($N \times 3 \times 3$).
    * **Độ phức tạp:** $O(N \times 3 \times 3 \times 9) = O(N)$. Đây là độ phức tạp cần thiết cho $N \le 1000$.

✅ Đã AC: 0 / 0 submissions