Lưới Di Chuyển

Trong quá trình sưu tầm các bài toán thú vị, FullHouse Dev đã tìm thấy một bài toán về di chuyển trên lưới. Họ quyết định thêm bài toán này vào bộ sưu tập của mình và chia sẻ với cộng đồng lập trình.

Bài toán

Cho một lưới \(A\) kích thước \(N × M\) và \(Q\) truy vấn. Mỗi truy vấn chứa hai số nguyên \((x, y)\). Mỗi ô trong lưới hoặc là ô trống (được ký hiệu bằng O) hoặc là ô bị chặn (được ký hiệu bằng *). Ban đầu, bạn đang ở vị trí \((x_s, y_s)\). Hãy tìm số bước tối thiểu để di chuyển từ \((x_s, y_s)\) đến \((x, y)\) mà không đi qua các ô bị chặn.

Trong một bước, bạn có thể di chuyển từ ô \((i,j)\) đến 4 ô lân cận: \((i+1,j)\), \((i-1,j)\), \((i,j+1)\) và \((i,j-1)\) với điều kiện các ô này nằm trong lưới \(A\).

INPUT FORMAT:

• Dòng đầu tiên chứa 3 số nguyên \(N\), \(M\) và \(Q\) - kích thước của lưới và số lượng truy vấn.
• \(N\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(M\), ký tự thứ \(j\) của dòng thứ \(i\) là O hoặc * thể hiện ô \((i,j)\) trống hay bị chặn.
• Dòng tiếp theo chứa 2 số nguyên \(x_s\) và \(y_s\) - vị trí xuất phát.
• \(Q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(x\) và \(y\) - vị trí đích cần đến.

OUTPUT FORMAT:

• In ra \(Q\) dòng, mỗi dòng là số bước tối thiểu cần di chuyển cho mỗi truy vấn. Nếu không tồn tại đường đi, in ra -1.

Ràng buộc:

• \(1 \leq N, M \leq 1000\)
• \(1 \leq Q \leq 10^5\)

Ví dụ:

INPUT

3 3 2
O*O
OOO
*OO
2 2
1 1
1 2

OUTPUT

2
-1

Giải thích:

• Với truy vấn đầu tiên: đường đi ngắn nhất từ (2,2) đến (1,1) là (2,2)->(2,1)->(1,1), cần 2 bước.
• Với truy vấn thứ hai: không tồn tại đường đi từ (2,2) đến (1,2), vì vậy kết quả là -1.