Elearning CodePath – CTP Online Judge

Đường đi trên bảng

TABPATH

---

### 📝 Bài toán
Trên bảng kí tự kích thước $m \times n$, các hàng được đánh số từ 1 đến $m$ (từ trên xuống), các cột được đánh số từ 1 đến $n$ (từ trái sang phải). Ô nằm giao giữa hàng $i$ và cột $j$ là ô $(i, j)$. Mỗi ô chứa một kí tự thuộc tập {'A'..'Z', '*'}. Cụ thể, mỗi ô chứa kí tự chữ cái Latinh in hoa hoặc là kí tự '*'.
Xuất phát từ ô $(x, y)$ cần tìm đường đi tới một ô chứa kí tự '*' nào đó trên bảng với chi phí nhỏ nhất theo quy tắc di chuyển như sau:
+ Chỉ được di chuyển sang các ô chung cạnh;
+ Nếu di chuyển sang ô mới chứa kí tự giống với kí tự trong ô hiện tại thì không mất chi phí di chuyển, còn nếu di chuyển sang ô mới chứa kí tự khác với kí tự trong ô hiện tại thì mất chi phí là 1.

### Yêu cầu: 
Cho bảng kí tự và $Q$ ô $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{Q}, y_{Q})$. Với mỗi ô $(x_{i}, y_{i})$, hãy tính chi phí của đường đi từ ô $(x_{i}, y_{i})$ đến một ô chứa kí tự '*' nào đó trên bảng có chi phí nhỏ nhất ($i = 1, 2, \dots, Q$).

### 📥 Định dạng Đầu vào
Dữ liệu từ file TABPATH.INP:
* Dòng đầu tiên chứa ba số nguyên $m, n, Q$.
* $m$ dòng tiếp theo, mỗi dòng chứa một xâu độ dài $n$ mô tả bảng kí tự.
* $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x, y$ là tọa độ xuất phát.

### 📤 Định dạng Đầu ra
Ghi ra file TABPATH.OUT gồm $Q$ dòng, mỗi dòng là chi phí nhỏ nhất tìm được tương ứng với mỗi truy vấn.

### ✨ Ví dụ
| TABPATH.INP | TABPATH.OUT |
| :--- | :--- |
| 4 5 4 *ACCB AACCB AACBA AAAAA 3 5 1 5 3 3 2 4 | 1 2 2 2 |

### 🏷 Ràng buộc
* Subtask 1 (50%): $m, n \le 100; Q \le 3$.
* Subtask 2 (25%): $m, n \le 1000; Q \le 3$.
* Subtask 3 (25%): $m, n \le 1000; Q \le m \times n$.

✅ Đã AC: 6 / 15 submissions