Codeforces Educational 1D - Igor In The Museum

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
Codeforces Educational Round 1
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Igor đang tham quan bảo tàng và anh ấy muốn được chiêm ngưỡng nhiều bức tranh nhất có thể.

Bảo tàng được biểu diễn dưới dạng hình chữ nhật kích thước ~n \times m~ ô. Mỗi ô có thể trống hoặc không thể đi qua. Các ô trống được đánh dấu là ., các ô không thể đi qua được đánh dấu là *. ~2~ ô khác loại kề nhau (~1~ trống và ~1~ không thể đi qua) được ngăn cách bởi bức tường chứa ~1~ bức tranh.

Ban đầu Igor đang đứng ở một ô trống nào đó. Tại mỗi thời điểm anh ấy có thể di chuyển sang một ô trống khác kề với ô hiện tại.

Cho trước một số ô xuất phát, với mỗi ô, hãy tính số lượng bức tranh tối đa mà Igor có thể chiêm ngưỡng. Igor chỉ có thể xem tranh khi anh ấy đứng tại vị trí kề bức tường chứa bức tranh đó. Igor có rất nhiều thời gian, vậy nên anh ấy sẽ chiêm ngưỡng các bức tranh mà mình có thể thấy.

Input

  • Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~ ~(3 \le n, m \le 1000, 1 \le k \le min(n \cdot m, 100\,000))~ ~-~ các kích thước của bảo tàng và số lượng ô xuất phát.

  • ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ kí tự ., * mô tả bảo tàng. Input đảm bảo rằng các ô ở biên đều không thể đi qua, tránh trường hợp Igor đi ra khỏi bảo tàng.

  • ~k~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(1 \le x \le n, 1 \le y \le m)~ ~-~ một trong các ô xuất phát của Igor. Các dòng được đánh số từ trên xuống dưới, các cột ~-~ từ trái qua phải. Input đảm bảo các vị trí xuất phát đều là ô trống.

Output

In ra trên ~k~ dòng ~-~ số bức tranh tối đa mà Igor có thể chiêm ngưỡng, nếu Igor xuất phát tại ô tương ứng.

Sample 1

Input
5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3
Output
6
4
10

Sample 2

Input
4 4 1
****
*..*
*.**
****
3 2
Output
8

Comments

Please read the guidelines before commenting.


There are no comments at the moment.