Untitled
unknown
plain_text
a year ago
26 kB
19
Indexable
Mỏ khai thác vàng
Cho bản đồ mỏ vàng có thể được biểu diễn dưới dạng ma trận NxN
Trong bản đồ này, có một số mỏ vàng nằm ở những vị trí ngẫu nhiên (tối đa 4 mỏ trên mỗi bản đồ). Một trại sẽ được thiết lập trên bản đồ để khai thác vàng. Hàng ngày, công nhân sẽ đi từ khu trại đến địa điểm mỏ vàng. Để giảm chi phí, công ty muốn thiết lập trại sao cho khoảng cách từ trại đến địa điểm khai thác được tối ưu hóa.
Hãy xem xét bản đồ 5x5 dưới đây:
- Công nhân không thể đi xuyên qua đá
- Mất 1 giờ để di chuyển một ô trên bản đồ
Có hai mỏ, từ điểm xuất phát (địa điểm cắm trại), đi đến mỗi mỏ vàng phải mất 4h. Giả sử chi phí cuối cùng sẽ là chi phí cao nhất trong số đó, thì nếu chúng ta đặt trại như hình trên thì chi phí cuối cùng sẽ là 4.
Bây giờ, chúng ta xem xét ví dụ khác:
Trong ví dụ thứ 3, chi phí cuối cùng sẽ tối thiểu (1)
[ Đầu vào ]
Dòng đầu tiên nhập vào sẽ là số test case T (T ≤ 50)
Trong mỗi TC:
- Dòng đầu tiên sẽ cho biết kích thước bản đồ N (N ≤ 20) và số lượng mỏ vàng G (2 ≤ G ≤ 4)
- Các dòng G tiếp theo sẽ là vị trí R (hàng) & C (cột) mỏ vàng (chỉ số 1 base)
- N dòng tiếp theo sẽ là số liệu của bản đồ: 1 tượng trưng cho đường đi & mỏ vàng, 0 tượng trưng cho tảng đá (không thể đi qua)
[ Đầu ra ]
Chương trình của bạn sẽ đưa ra Chi phí cuối cùng tối thiểu để đi từ trại đến mỏ vàng.
Trường hợp 1
1
Trường hợp số 2
2
Trường hợp số 3
2
Trường hợp số 4
7
Trường hợp số 5
6
[ Hạn chế ]
- Bạn có thể di chuyển theo 4 hướng (lên/trái/xuống/phải)
- Bạn không thể dựng trại ở vị trí mỏ vàng hoặc đá
- Bạn có thể đi qua mỏ vàng sau đó đi đến mỏ vàng khác
- Bạn phải cắm trại để công nhân có thể đi tới tất cả các mỏ vàng
50
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 3
8 2
5 3
7 1
0 0 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0
1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
8 3
1 2
2 8
5 8
0 1 0 0 0 0 0 0
0 1 0 1 1 1 1 1
0 1 0 1 0 0 0 1
0 1 1 1 0 0 0 1
0 1 0 1 0 0 0 1
0 1 0 1 1 1 1 1
0 1 0 0 1 0 0 0
0 1 0 0 1 0 0 0
10 4
9 6
1 9
7 5
7 3
1 1 1 1 1 1 0 1 1 0
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1
1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1 0 1
10 4
10 4
6 7
4 5
4 9
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0
0 0 1 1 1 0 1 0 1 1
10 3
10 5
6 9
7 8
1 0 0 1 1 0 0 0 0 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 0
10 3
5 2
4 6
6 5
1 0 1 1 1 1 1 0 1 1
1 1 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1
0 0 1 1 0 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
10 3
9 5
1 3
7 4
0 1 1 1 1 0 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 0 0 1 1 1
1 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1
0 0 0 1 0 1 1 0 1 1
0 0 0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 1 1
10 3
1 10
6 2
4 6
0 1 1 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 0 1
0 0 1 1 0 0 1 0 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 0
10 2
4 4
4 5
0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1
10 4
7 4
9 4
4 6
4 8
1 1 1 0 0 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 0 1 1
0 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 1 0 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
10 4
1 3
6 6
2 5
8 5
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
10 2
3 2
6 7
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 0
0 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1
1 1 0 0 0 0 1 1 1 1
10 4
7 5
1 7
2 4
9 10
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
10 2
4 5
2 2
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1
10 2
8 5
10 7
1 1 1 1 1 0 1 1 1 1
1 0 1 0 1 1 1 1 1 1
1 0 1 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1
10 2
2 4
10 5
0 0 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 0 0 1 0
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1
10 2
7 8
3 8
1 1 1 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1
0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 0 1 1 1
10 4
9 9
9 2
10 7
1 2
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
12 3
4 3
6 6
6 11
0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 0
0 1 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0
0 1 1 1 0 1 1 1 1 1 0 1
1 1 1 0 1 0 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1
12 3
10 2
4 9
4 10
1 0 1 0 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 0 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 0
12 4
12 12
2 8
8 5
7 4
1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0
0 1 1 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 0 1 1
12 4
11 3
10 5
6 12
12 7
1 0 0 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
12 4
11 2
2 10
5 11
5 12
1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1
12 2
9 8
7 9
1 1 1 1 1 1 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 1 0 0
1 1 1 1 1 0 0 1 1 0 0 1
1 1 1 1 1 0 1 0 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 0 1 1 1 1 1
1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 0
12 2
7 9
10 8
1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
12 2
6 5
1 2
1 1 1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 0 1 1 0
1 1 1 0 1 1 0 1 1 1 1 1
1 0 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1 0 1
12 4
7 6
7 12
5 5
5 4
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 1 0 1 1
0 0 0 1 1 1 1 1 1 1 0 1
0 1 0 1 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
12 4
12 4
6 7
3 8
11 9
1 1 1 0 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 0 1 1
1 1 0 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 0 1
1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 1 0
15 3
8 6
8 5
12 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 0 1 1 1 1 1 1
1 1 0 1 1 1 1 0 0 0 1 1 1 0 1
1 1 1 1 1 0 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 0 1 0 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
7 2
12 7
4 8
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 1 1 0 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
15 2
6 4
7 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 0 1 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 1 1 1 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 0 1 1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 2
4 2
3 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 0 1 0 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 0 1 1
0 1 1 1 1 0 0 1 0 1 1 1 1 1 1
15 4
1 8
10 6
9 7
9 8
1 1 1 0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 0 1 1 0 1 0
1 1 1 1 1 0 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 0 0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1 1 1 1 1
15 3
2 12
12 14
12 5
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0 1 0 0 1 1 1 1
1 0 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 0 1
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
9 6
11 4
1 3
1 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1 0 1 0 1 0
1 1 1 0 1 0 1 1 0 1 1 0 1 1 0
1 0 1 0 0 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 0 1 0 0 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
15 3
15 7
1 4
2 7
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 0 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 0 0 1 0 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 0
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0
1 0 1 1 1 1 1 0 0 0 0 1 1 1 0
15 4
8 8
1 5
1 12
6 12
1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 1 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 0 0 0 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 0 1 0
0 1 1 1 1 0 1 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
3 11
15 12
1 7
0 1 1 1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 0 0 1 0 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 0 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 0 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0
20 2
6 12
12 11
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1
1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0
1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1
1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1
20 4
8 20
17 17
2 18
2 13
1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1
1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1
20 2
18 6
5 17
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0
1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0
0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1
0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0
20 3
8 11
11 14
13 16
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1
1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1
0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
20 2
7 10
13 19
1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1
0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1
1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1
1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
20 3
6 2
10 7
14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0
1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
20 3
9 8
8 12
7 12
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0
1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1
0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1
20 3
7 12
9 8
14 5
1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0
1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1
1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1
20 3
17 4
19 15
17 18
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1
1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1
20 3
4 20
5 19
20 16
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0
1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0
import java.util.Scanner;
public class Solution {
static int n, g, min, count, cnt, cnt1;
static int[][] gold, mine, dist, gmap, tmp;
static Queue queue = new Queue(100000);
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args){
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
n = sc.nextInt();
g = sc.nextInt();
gold = new int[g][2];
gmap = new int[n][n];
tmp = new int[g][2];
for (int i = 0; i < g; i++) {
gold[i][0] = sc.nextInt() - 1;
gold[i][1] = sc.nextInt() - 1;
gmap[gold[i][0]][gold[i][1]] = 1;
}
mine = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mine[i][j] = sc.nextInt();
}
}
min = 10000;
count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mine[i][j] != 0 && gmap[i][j] == 0) {
cnt = 0;
dist = new int[n][n];
bfs(i, j);
}
}
}
System.out.println("Case #" + tc);
if (min == 10000) {
System.out.println(-1);
} else {
System.out.println(min - 1);
}
}
sc.close();
}
private static void bfs(int x, int y) {
// TODO Auto-generated method stub
queue.reset();
queue.push(x);
queue.push(y);
dist[x][y] = 1;
int r, c, d;
while (!queue.empty()) {
r = queue.pop();
c = queue.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == 0
&& mine[nr][nc] == 1) {
dist[nr][nc] = dist[r][c] + 1;
queue.push(nr);
queue.push(nc);
}
}
}
int max = -1;
for (int i = 0; i < g; i++) {
r = gold[i][0];
c = gold[i][1];
d = dist[r][c];
if (dist[r][c] == 0) {
return;
}
if (d > max) {
max = dist[r][c];
}
}
if (max != -1 && min > max) {
min = max;
}
}
}
class Queue {
static int f, r;
static int[] arr;
Queue(int c) {
f = r = 0;
arr = new int[c];
}
boolean empty() {
return f == r;
}
void reset() {
r = f = 0;
}
void push(int data) {
arr[r] = data;
r++;
}
int pop() {
f++;
return arr[f - 1];
}
}
Leave a Comment