Problem
Thợ săn kho báu Vasya tình cờ thấy bản đồ của một hầm ngục cổ đại. Hầm ngục là một mê cung cỡ NM (1NM100 , NM100). Mỗi ô của mê cung đều trống và có thể đi qua hoặc có một bức tường. Bạn chỉ có thể di chuyển từ một ô sang một ô liền kề với bức tường (ví dụ: mỗi ô có thể có không quá 4 ô liền kề).
Ở một trong các phòng giam có một kho báu mà Vasya muốn lấy. Mê cung có K lối vào để Vasya có thể bắt đầu cuộc hành trình của mình.
Cần xác định xem Vasya cần bắt đầu hành trình từ lối vào nào để quãng đường di chuyển đến kho báu là ít nhất. Nếu có nhiều đầu vào như vậy, hãy in đầu vào có số lượng nhỏ nhất.
Đầu vào
Dòng đầu tiên chứa 2 số N và M xác định kích thước của mê cung. Mô tả mê cung như sau: N dòng với M ký tự mỗi dòng. 0 có nghĩa là ô trống; 1 rằng có một bức tường trong lồng. Biểu tượng * biểu thị một ô chứa kho báu (chỉ có đúng một ô như vậy trong mê cung).
Dòng thứ (N+2) chứa số K (1<=K<= NxM) -- số lối vào mê cung. Tiếp theo, K dòng chứa tọa độ của các đầu vào. Do đó, dòng thứ i chứa các số xi và yi, nghĩa là đầu vào thứ i nằm ở dòng thứ xi và trong cột thứ yi (1xiN1yiM). Đảm bảo rằng tọa độ của các đầu vào khác nhau theo từng cặp và tất cả các đầu vào đều nằm trong các ô trống. Không có lối vào nào nằm trong lồng kho báu.
Đầu ra
Cần hiển thị một số - số đầu vào mong muốn (đánh số bắt đầu từ 1). Nếu không lấy được kho báu, hãy in -1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
|
1 |
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1 |