Elearning CodePath – CTP Online Judge

Đường Đi Nguyên Tố

PRIMEPATH

### 📌 Thông tin chung

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

Cho một lưới số nguyên dương $A$ kích thước $N \times M$. Mỗi ô chứa một giá trị $A[i][j]$ với $0 \le A[i][j] \le 10^{12}$.

Bạn đứng ở ô $(1, 1)$ và muốn đi đến ô $(N, M)$.
* Bạn chỉ được đi vào các ô có giá trị là số nguyên tố.
* Bạn có thể di chuyển theo 4 hướng: Trái, Phải, Lên, Xuống (sang các ô kề cạnh).

Yêu cầu: Tìm độ dài đường đi ngắn nhất từ $(1, 1)$ đến $(N, M)$.

Quy ước: Nếu ô $(1, 1)$ hoặc ô $(N, M)$ không phải là số nguyên tố, hoặc không tồn tại đường đi, hãy in ra $-1$.

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

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

* Dòng 1: Hai số nguyên $N, M$ — kích thước lưới.
* $N$ dòng tiếp theo: mỗi dòng gồm $M$ số nguyên $A[i][j]$.

Giới hạn:
* $1 \le N, M \le 2000$.
* $1 \le N \times M \le 4 \times 10^6$.
* $0 \le A[i][j] \le 10^{12}$.

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

Ghi ra file `PRIMEPATH.OUT` một số duy nhất:
1.  Độ dài đường đi ngắn nhất, hoặc
2.  $-1$ nếu không thể đi được.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `3 4` <br> `2 4 5 7` <br> `11 6 8 13` <br> `17 19 23 29` | `6` |

---
### 🏷 Ràng buộc – Subtask theo thuật toán kiểm tra số nguyên tố

| Tỷ lệ điểm | Ràng buộc | 
| :--- | :--- | 
| $10\%$ | $A[i][j] \le 10^6$; $N \times M \le 10^5$ | 
| $25\%$ | $A[i][j] \le 10^7$ | 
| $30\%$ | Giá trị các ô trong mỗi test nằm trong đoạn $[L, R]$, $R - L \le 10^6$ | 
| $35\%$ | $A[i][j] \le 10^{12}$ không ràng buộc theo đoạn |

---

✅ Đã AC: 6 / 17 submissions