Mô tả và yêu cầu

Trò chơi di chuyển trên bảng
Cho một bảng ký tự kích thước 𝑚 × 𝑛, các hàng được đánh số từ 1 đến 𝑚 (từ trên xuống), các cột
được đánh số từ 1 đến 𝑛 (từ trái sang phải). Ô nằm giao giữa hàng 𝑖 và cột 𝑗 là ô (𝑖, 𝑗). Mỗi ô chứa
một ký tự thuộc tập [‘A’..’Z’, ‘*’]. Nhiệm vụ của người chơi là: xuất phát từ một ô (𝑥, 𝑦) cần tìm
đường đi tới một ô chứa ký 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à l.

Yêu cầu: Cho bảng ký tự và ô (𝑥, 𝑦), hãy tính chi phí của đường đi từ ô (𝑥, 𝑦) đến một ô chứa ký
tự ‘*’.

Dữ liệu vào

- Dòng đầu chứa ba số nguyên 𝑚, 𝑛, 𝑄.
- 𝑚 dòng tiếp theo, mỗi dòng chứa một xâu độ dài 𝑛 mô tả bảng ký tự.
- 𝑄 dòng tiếp theo, mỗi dòng chứa hai số nguyên 𝑥, 𝑦.

Dữ liệu ra

- Gồm 𝑄 dòng, mỗi dòng ghi một số là chi phí của đường đi từ ô (𝑥, 𝑦) đến một ô chứa ký
tự ‘*’.

PATHGAME.INP PATHGAME.OUT
4 5 3 1
*ACCB 2
AACCB 2
AACBA
AAAAA
3 5
1 5
3 3

Subtask 1: 𝑚, 𝑛 ≤ 100; 𝑄 ≤ 3;
Subtask 2: 𝑚, 𝑛 ≤ 1000; 𝑄 ≤ 3;
Subtask 3: 𝑚, 𝑛 ≤ 1000; 𝑄 ≤ 𝑚 × 𝑛;