Untitled
unknown
plain_text
2 years ago
31 kB
31
Indexable
Hugo đào vàng trả nợ
Sau khi ăn trộm được mật của chị ong nâu và say sưa thưởng thức mật ngọt say đắm thì bất ngờ Hugo bị chị ong nâu phát hiện. Mặc dù đã thành khẩn nhận lỗi và xin lỗi chị ong nâu nhưng do đã đánh chén gần hết số mật đã ăn chộm nên chị ong nâu vẫn bắt Hugo phải bồi thường số mật đó. Hugo thì làm sao có thể kiếm mật được vì vậy Hugo phải đi đào vàng kiếm tiền để có tiền mua mật trả cho chị ong nâu.
Một cách tình cờ Hugo có được bản đồ của một khu vực chứa vàng, bản đồ được vẽ dựa trên một ma trận NxN. Trong ma trận có các điểm chứa vàng có thể khai thác (Tối đa 4 điểm). Hàng ngày Hugo sẽ phải đi tới mỏ vàng để khai thác và cuối ngày sẽ phải mang vàng trở về. Để tiết kiệm chi phí và thời gian, Hugo quyết định cắm trại trên gần mỏ vàng để tiện khai thác vàng. Hugo không thể di chuyển qua khu vực đá và không thể cắm trại trên đá, đồng thời Hugo cũng không thể cắm trại tại khu vực mỏ vàng, thời gian để Hugo di chuyển qua mỗi ô là 1 giờ.
Hãy giúp Hugo tìm địa điểm tối ưu để đi khai thác tất cả các mỏ vàng nhanh nhất.
Xem xét ma trận mỏ vàng 5x5 bên dưới:
Có 2 mỏ vàng, nếu Hugo cắm trại tại vị trí X, Hugo sẽ mất 4 giờ để đi tới mỏ vàng thứ 1, và 6 giờ để đi tới mỏ vàng thứ 2, vì vậy thời gian nhỏ nhất để Hugo đi khai thác vàng là 6 giờ, thời gian lớn nhất để đi khai thác của tất cả các mỏ vàng.
Xem xét ví dụ khác:
Thời gian tối ưu với ma trận mỏ vàng trên là 1.
Một mỏ vàng được coi là không thể tiếp cận khi không thể đặt 1 vị trí cắm trại nào để đi khai thác vàng.
[Input]
Số trường hợp thử nghiệp T (T ≤ 50)
Mỗi TC :
- Dòng đầu tiên chứa kích thước ma trận N (N ≤ 20) và số mỏ vàng G (2 ≤ G ≤ 4)
- G dòng tiếp theo đưa ra vị trí R (hàng) & C (cột) của mỏ vàng (Chỉ số bắt đầu từ 1)
- N dòng tiếp theo là thông tin ma trận: 1 là có đường đi và vị trí mỏ vàng, 0 là đá (không thể đi qua).
[Output]
Dòng đầu tiên: In ra chi phí nhỏ nhất để đi từ trại tới điểm đào vàng xa nhất. Nếu không thể tiếp cận tất cả các mỏ vàng, in ra -1
Nếu có bất kỳ mỏ vàng nào không thể tiếp cận, bạn nên in ra vị trí của chúng trên mỗi dòng theo thứ tự đã nhập vào. Bạn nên đặt vị trí trại sao cho Hugo có thể tiếp cận được nhiều mỏ vàng nhất có thể. Ưu tiên các mỏ vàng xuất hiện trước theo thứ tự nhập.
Case #1
1
Case #2
2
Case #3
2
Case #11
1
4 3
4 5
6 10
Case #48
-1
Case #49
11
[Constraints]
- You can move on 4 directions (up/left/down/right)
- You can not setup the camp on gold mine location or rock
- You can go pass a gold mine then go to other gold mine
- You should place camp in order to Maximize the number of reachable gold mines
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
6 6
1 1 1 1 1 0 0 1 1 1
1 1 0 1 1 1 1 0 0 0
0 1 0 1 1 0 1 1 1 1
0 1 0 0 1 1 1 1 0 1
0 1 0 0 1 0 1 1 1 1
1 1 0 0 1 1 0 1 1 1
1 1 0 0 1 1 1 1 1 1
0 1 0 1 1 0 0 0 1 0
1 0 1 0 1 1 1 1 1 0
0 1 1 1 1 1 0 0 1 0
10 3
10 4
6 7
4 5
0 0 1 0 0 0 1 0 1 0
1 1 0 1 1 1 1 1 0 1
1 1 0 1 1 0 1 1 0 0
1 1 1 1 1 0 1 1 1 1
0 1 0 1 0 1 1 1 0 1
1 0 1 0 1 1 1 1 1 1
0 0 0 0 0 1 1 0 1 1
0 1 0 1 1 1 1 1 0 1
1 0 0 1 1 1 1 1 1 0
1 1 1 1 1 0 1 1 0 1
10 3
8 8
6 9
7 8
0 1 1 1 0 0 0 0 1 1
1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 0 1 1 0 1
0 1 0 0 1 1 1 1 1 1
0 0 0 1 0 1 0 1 1 1
0 1 1 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1
1 0 0 1 1 1 0 1 1 1
0 1 0 1 1 1 1 1 1 1
0 1 0 1 0 1 1 1 1 1
10 3
5 2
8 2
4 6
1 1 1 0 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 0
1 1 0 1 1 1 0 1 1 1
0 1 1 1 1 1 0 0 0 1
0 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 0
0 1 0 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 1 0
1 0 0 1 0 1 1 1 1 1
10 4
8 3
1 2
9 5
5 7
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 0 1 1 1
0 1 0 1 1 1 1 0 1 1
0 0 0 1 1 0 1 0 1 0
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1
0 0 1 1 1 1 1 0 1 1
10 2
8 4
1 10
1 0 1 1 0 1 1 1 0 1
0 0 0 1 0 0 1 0 1 1
1 1 0 0 1 1 0 0 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 0 1 1 1 1 0
1 1 0 1 0 1 1 0 0 1
1 1 0 1 1 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 0 1 0 1 0 1 1 1 1
0 1 0 1 0 1 1 1 1 1
10 4
3 4
4 3
4 5
6 10
1 0 0 1 1 0 0 0 1 0
1 1 1 1 0 1 1 0 1 0
1 0 0 1 0 1 1 1 0 1
1 0 1 0 1 1 1 1 1 0
0 1 0 0 1 1 1 1 0 0
1 1 0 0 1 1 1 0 1 1
1 0 0 1 0 1 0 1 1 0
1 0 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1
10 2
4 6
4 8
0 0 0 1 1 0 0 1 1 1
1 1 1 0 1 1 1 0 1 0
1 0 1 1 0 1 1 0 1 0
1 0 1 1 0 1 1 1 0 0
1 1 1 1 0 1 1 1 1 1
0 1 1 0 1 1 0 1 1 1
1 0 1 0 1 1 1 0 1 1
0 1 1 0 0 1 1 1 1 1
0 0 1 0 0 1 0 1 1 0
1 1 0 0 1 0 1 1 0 0
10 3
6 6
2 5
6 8
0 1 1 1 1 1 1 0 1 1
1 1 0 1 1 0 1 1 0 1
0 1 0 1 0 1 1 0 1 1
0 0 1 1 0 0 1 1 1 0
1 1 0 1 1 1 1 0 0 1
1 1 1 0 0 1 0 1 0 0
1 0 0 0 0 0 0 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 0 1 0 1
0 1 1 1 0 1 1 1 0 1
10 4
3 2
6 7
3 9
7 9
0 0 0 1 0 1 0 0 0 1
0 1 0 1 0 0 1 0 1 1
0 1 1 1 0 1 0 1 1 0
1 1 0 1 0 1 1 0 0 1
0 1 1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1
0 0 1 1 0 0 1 1 1 1
1 1 1 1 0 1 1 1 0 1
1 0 0 1 0 1 0 0 1 0
10 4
1 7
2 4
9 10
7 2
1 1 0 1 1 0 1 1 1 1
1 1 0 1 1 1 0 1 1 0
1 1 0 1 0 1 0 0 1 1
1 0 1 1 0 1 1 0 0 1
1 0 0 0 0 0 1 1 1 0
1 1 0 0 1 0 0 1 1 1
0 1 1 1 1 1 1 0 1 0
1 1 1 1 1 0 0 1 0 0
0 1 0 1 1 0 0 1 0 1
1 1 1 1 1 0 1 0 0 0
10 2
2 2
3 6
0 1 1 1 0 1 0 1 1 1
1 1 1 0 0 1 1 1 1 0
0 0 0 0 1 1 0 1 1 0
0 1 0 0 0 1 0 0 1 1
1 1 1 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 0 0
1 1 0 0 1 1 1 1 1 0
1 0 1 0 0 0 0 1 1 0
0 1 0 1 1 1 1 1 1 1
1 1 1 1 1 0 1 0 1 1
10 4
1 4
9 5
4 3
1 6
0 0 1 1 1 1 1 1 0 1
1 1 1 0 0 0 1 0 0 1
1 1 1 0 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 0
0 1 0 1 0 0 1 1 1 0
0 1 1 0 1 0 0 1 1 1
1 1 1 1 1 1 0 0 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 0 1 1 1 1 0 0
10 2
10 10
10 6
1 1 1 0 1 0 1 1 1 1
1 0 1 1 1 0 0 0 1 0
1 1 1 1 0 0 1 1 1 0
1 1 1 0 0 1 1 1 1 0
0 1 0 1 0 1 0 0 0 1
1 1 0 1 1 0 0 1 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 1 1 1 1 1 0 0
0 1 1 1 1 1 1 0 1 0
1 1 0 0 1 1 0 1 0 1
10 3
6 8
9 6
6 5
0 1 0 0 1 1 0 1 0 1
0 1 0 0 1 1 1 1 0 1
1 0 1 0 0 1 1 1 1 1
1 1 0 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 1 0
1 0 1 1 1 1 0 1 1 1
1 1 1 1 0 0 1 0 1 1
1 1 1 1 1 0 1 0 1 1
0 1 0 0 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
10 3
9 4
4 2
9 10
1 1 1 0 0 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 0 0 0
0 1 0 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 0 1
0 1 0 0 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 0
1 1 1 1 0 1 1 0 1 1
0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 0 0
12 4
8 4
6 3
12 5
5 7
1 0 1 1 0 1 0 0 0 0 1 1
1 1 0 0 0 1 1 1 1 0 0 1
1 0 1 0 0 0 0 1 1 0 1 1
0 1 0 1 1 1 1 0 1 1 0 1
0 0 0 1 1 0 1 1 0 1 0 0
0 1 1 1 1 1 0 0 1 1 0 0
1 1 1 0 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 0 1 1 1 1 1
0 1 0 1 0 1 1 1 1 1 1 1
1 1 1 1 1 0 1 0 1 0 1 1
1 0 1 1 1 0 0 1 1 1 1 1
12 2
6 11
6 12
1 0 0 0 1 1 0 1 1 0 1 1
1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
1 1 0 0 1 0 1 1 0 0 1 0
0 1 0 1 0 0 0 1 1 0 0 0
1 0 1 0 1 1 1 1 1 0 1 1
0 0 1 0 1 0 1 1 1 0 1 0
1 0 1 0 1 0 0 0 0 0 1 0
0 0 0 1 1 1 0 0 0 1 0 1
0 1 1 1 1 1 1 0 0 0 0 1
1 1 0 0 0 1 1 0 1 0 1 0
1 1 0 1 0 0 1 0 0 1 1 1
12 4
11 2
2 7
8 5
12 6
0 0 1 0 1 1 0 0 0 1 1 1
1 0 1 1 0 0 1 1 0 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1
0 1 1 0 1 0 1 1 1 1 0 1
1 1 1 0 0 0 0 0 0 1 1 1
1 1 0 1 1 1 1 1 1 1 1 0
1 1 0 1 1 1 0 1 1 1 0 1
0 1 0 0 1 1 1 1 1 1 1 0
1 0 0 1 1 1 0 0 1 1 0 1
0 0 1 0 1 0 1 1 1 0 1 1
0 1 1 1 1 1 1 0 1 0 0 0
1 0 0 0 0 1 1 0 1 1 1 0
12 4
7 3
11 5
2 10
10 2
0 1 1 1 0 1 1 0 1 1 0 1
1 0 1 1 1 0 1 1 1 1 0 0
0 0 1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 0
1 1 0 1 0 1 1 1 1 0 1 1
0 1 0 0 0 0 1 0 1 1 1 0
0 0 1 1 1 0 1 0 1 0 1 1
1 1 1 1 0 0 1 1 1 1 1 1
1 0 1 0 1 0 1 1 0 1 0 0
0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 1
1 0 1 0 1 0 1 1 0 1 1 1
12 4
4 3
5 5
11 10
10 10
0 1 0 0 1 1 1 1 1 1 1 0
1 1 1 0 1 1 0 1 1 1 0 0
1 1 0 1 0 1 1 0 1 1 1 1
0 0 1 1 0 1 1 1 1 0 1 1
0 1 1 1 1 0 0 1 0 1 1 1
1 1 1 0 1 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 0 1 0
1 1 1 0 1 1 1 0 1 1 0 1
1 1 1 0 1 0 1 1 0 0 1 0
1 1 1 1 1 1 1 1 0 1 0 1
0 0 1 1 1 1 1 1 0 1 1 1
1 0 0 1 1 0 1 1 1 0 1 1
12 2
11 10
3 6
1 1 1 0 0 1 1 0 0 1 0 0
1 1 0 1 1 1 0 1 1 1 1 1
1 0 1 0 0 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0 1 0 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 1 1 0 0 1 0 1 1 1
1 1 0 1 0 1 1 1 1 1 0 0
1 1 0 0 1 0 1 1 1 1 1 0
1 0 1 0 1 0 0 0 0 1 1 1
1 1 0 1 1 1 0 1 1 1 0 1
12 2
2 11
1 7
0 1 1 1 1 1 1 0 0 1 1 1
1 1 0 0 1 0 1 0 1 1 1 1
1 0 1 0 1 1 0 1 0 1 0 1
1 1 0 1 0 1 0 0 1 1 1 1
0 1 0 1 1 1 1 0 1 0 1 0
1 1 1 1 1 1 1 1 0 0 1 0
1 1 1 1 0 1 1 1 1 0 0 0
1 1 0 1 0 0 0 1 1 1 0 1
1 1 1 0 1 0 0 0 1 1 0 0
1 1 0 1 0 0 1 1 1 1 1 0
0 1 0 0 1 1 1 1 1 0 1 1
1 1 0 1 1 1 0 0 1 1 0 0
12 2
3 9
9 8
1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 0 0 1 1
1 0 1 0 1 0 1 1 1 0 1 1
0 1 1 1 1 0 1 1 0 1 1 0
1 0 0 0 0 1 0 0 1 1 1 1
0 1 1 1 1 1 1 0 0 0 1 1
1 0 0 1 1 1 1 1 0 0 1 0
1 1 1 0 1 0 0 0 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1 0
1 1 0 1 1 0 0 1 0 1 0 0
0 1 1 1 0 1 0 1 0 0 1 1
0 0 0 1 1 1 1 0 0 1 1 0
12 3
5 2
12 7
10 10
1 1 1 1 1 1 1 1 1 1 1 0
1 1 0 1 1 1 0 1 0 0 0 1
1 0 1 1 0 1 1 0 1 0 1 1
0 1 1 0 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 0 1
1 0 1 1 1 0 1 0 1 0 1 1
0 0 1 1 0 1 1 0 1 1 1 0
0 0 0 1 0 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1
1 0 0 1 0 0 0 1 0 1 1 1
1 0 1 0 1 0 1 1 1 1 1 1
0 0 1 1 0 1 1 0 0 0 0 1
12 2
8 3
8 9
1 1 0 0 1 0 0 1 0 1 1 0
0 0 1 1 0 0 0 1 1 1 0 0
1 1 0 1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 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 0 1 0 1 1
0 1 1 1 1 0 1 0 1 0 1 0
1 0 1 1 1 1 1 1 1 0 0 0
1 1 1 1 0 1 0 1 0 1 1 0
1 1 1 1 1 1 0 0 1 0 0 1
1 1 0 1 0 0 0 0 1 1 0 1
1 1 0 1 0 1 1 1 0 1 0 0
15 2
7 14
1 13
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
1 0 0 1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 0 0 1 1 1 1 0 0 1 1 1 0
0 1 1 0 1 0 1 0 1 1 0 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 0 1 0 1
1 0 1 1 1 1 1 1 0 0 1 0 0 0 1
0 1 0 0 1 0 1 1 1 0 1 1 1 1 1
0 1 0 0 1 0 1 1 1 0 0 1 0 0 1
1 1 1 0 1 1 1 1 1 1 0 1 1 1 0
0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 1 0 1 0
1 1 0 0 0 0 1 1 0 1 1 1 1 0 1
1 1 0 1 0 1 1 1 0 1 1 1 0 0 1
0 0 1 1 1 1 0 1 0 0 0 1 1 1 0
0 1 1 1 1 1 1 0 1 0 0 1 1 0 0
15 4
15 3
3 9
1 8
5 2
1 0 1 0 1 1 0 1 1 1 0 1 0 1 1
1 1 0 0 0 1 1 1 1 0 1 0 1 1 1
0 1 1 1 1 0 1 0 1 1 0 1 0 0 1
1 1 0 1 1 1 1 1 1 1 1 0 1 1 1
0 1 1 0 1 1 1 0 0 1 0 0 1 0 0
1 1 1 1 1 0 1 0 0 0 1 1 0 1 1
1 0 0 0 1 1 1 0 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 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 0 1 1 1 0 0
0 1 0 1 1 0 1 0 0 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
1 0 1 0 0 1 1 1 1 0 1 0 0 0 1
1 0 1 1 1 1 1 1 1 0 0 0 1 0 0
1 1 1 0 1 1 0 1 0 0 1 1 0 1 0
15 4
2 8
14 14
5 8
3 4
1 1 1 0 0 1 0 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 0 1 1 0 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1
1 1 0 0 1 0 1 1 1 0 0 1 1 0 1
0 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 0 0 1 0 0 1 1
1 0 0 1 1 1 0 0 1 0 1 0 1 0 0
1 1 1 0 1 1 1 1 1 1 0 1 0 1 1
0 0 0 1 1 0 1 1 1 1 1 0 1 1 1
0 0 0 1 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
0 1 0 1 1 1 1 0 1 0 1 1 1 1 1
1 1 0 0 0 1 1 0 1 1 0 0 0 1 0
1 1 1 0 0 1 1 0 1 1 1 1 1 0 1
15 3
11 15
12 3
9 2
0 1 1 1 0 1 1 0 1 0 1 1 1 1 1
0 1 0 0 0 0 1 0 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0 1 1 1 0 1 1 0
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 0 1 1 0 0 0 1 1 1 1 0 1
0 1 1 0 0 0 0 1 1 1 1 1 0 0 0
0 1 0 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 0 1
0 1 1 1 0 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 0
0 0 1 0 1 1 0 1 0 1 1 0 0 1 1
1 0 1 0 1 1 0 1 1 0 1 1 0 1 1
1 1 1 1 1 0 1 0 0 0 1 0 1 1 1
1 0 1 0 1 1 1 1 0 1 1 0 1 0 0
0 1 0 0 1 1 0 1 0 0 0 0 1 1 1
15 3
2 2
1 7
3 13
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
1 1 0 0 0 1 0 1 1 0 1 1 0 1 1
0 1 0 1 1 1 1 1 1 0 1 0 1 1 0
1 0 1 1 1 1 0 1 1 1 1 1 1 0 1
0 1 0 1 0 0 1 0 0 0 1 1 1 0 1
0 0 0 0 1 1 1 1 1 0 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 1 0 1 1 1 1 0 1
1 1 1 0 1 1 0 1 0 1 1 0 1 0 1
1 1 1 1 1 0 0 1 1 0 0 0 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 0 0 0
0 1 1 1 1 0 1 0 0 1 0 1 1 0 1
1 0 1 0 1 1 1 1 1 1 1 0 0 0 0
0 1 0 0 1 0 1 1 1 1 1 0 0 0 0
1 0 1 1 1 1 1 1 1 0 1 0 1 0 1
15 4
6 8
11 2
11 5
12 12
0 1 0 1 1 1 0 1 1 0 0 1 1 1 1
0 0 1 0 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 0
1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 0 0 1 0 1 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 1 1 0 1 1 0 0 1 0 0 1 1 0 1
1 1 1 1 1 1 1 0 0 1 1 1 1 1 0
1 0 0 0 1 1 0 0 0 1 0 1 0 0 0
1 0 1 0 1 0 1 0 1 1 0 0 0 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 1 1 1 1 1 1 1
1 1 1 1 0 1 0 1 1 0 1 1 1 1 1
0 0 1 0 0 1 1 0 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
15 4
6 10
4 15
15 8
2 9
1 1 0 1 0 1 1 1 0 1 1 0 1 1 1
1 1 1 0 0 1 1 0 1 0 1 0 1 1 0
1 0 1 1 0 1 1 1 1 0 0 0 1 0 0
1 0 0 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 0 0 1 0 0 1 1 0 1
1 0 1 1 1 0 1 1 0 1 1 0 0 1 0
0 0 0 1 1 1 1 0 0 1 0 0 0 1 1
0 1 1 1 1 0 0 1 1 1 1 1 1 0 1
1 0 1 1 0 0 1 0 0 1 1 0 0 1 0
1 1 1 0 1 0 1 1 0 0 1 0 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 0 1 1 1 1 0 1
1 1 0 0 0 1 0 1 1 1 1 1 1 1 1
0 1 1 0 1 0 1 1 0 1 0 1 1 1 1
0 0 1 1 1 0 1 1 1 0 0 1 1 0 1
15 3
3 9
7 13
11 5
1 0 0 1 1 0 0 1 1 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 0 0 1 1 0 1
0 0 1 0 1 1 1 1 1 1 1 1 0 0 1
1 1 1 0 1 1 0 1 0 1 0 1 0 1 1
0 1 0 1 1 0 1 1 1 1 1 1 1 0 0
1 0 1 0 1 1 1 1 0 1 0 1 0 1 0
1 0 1 0 1 1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 1 1 1 0
0 1 1 1 1 1 1 0 1 1 1 1 0 1 1
0 1 1 0 0 0 1 0 0 1 0 0 1 1 1
1 0 1 1 1 1 0 1 1 0 1 0 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1 1 0 0
0 1 0 1 1 0 1 1 1 1 1 1 0 0 0
1 1 0 0 1 0 1 1 1 1 1 0 1 1 1
1 0 0 1 1 1 0 1 0 1 1 1 1 1 0
15 2
7 11
10 8
1 0 1 1 1 1 0 0 1 0 1 1 0 1 1
1 1 0 1 0 1 1 0 1 1 0 0 0 1 1
1 0 0 1 1 1 0 1 0 1 0 1 0 1 1
1 0 1 1 0 0 1 0 1 1 0 1 0 1 0
1 1 1 0 1 1 0 1 1 1 1 1 1 1 0
1 1 1 0 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 0
1 1 1 1 0 1 1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 1 1 1 1 1 0 1
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
1 1 1 1 1 0 1 1 0 0 1 0 1 0 0
0 1 1 0 1 1 1 1 0 1 1 0 1 1 0
1 1 0 1 1 1 0 1 1 0 0 1 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 0 0 1 1 1 1 1 1 1
15 3
12 8
6 8
10 13
1 1 1 1 1 0 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 0 1 1 0 1 1
1 0 1 1 0 1 0 1 0 0 1 0 1 1 1
1 1 0 0 1 1 0 1 0 0 0 0 1 1 1
1 1 0 1 0 1 1 1 0 0 0 1 0 1 1
1 0 1 1 1 1 1 1 1 0 1 1 0 1 0
0 1 1 0 1 0 0 0 0 0 0 0 0 0 1
1 1 1 1 0 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
1 0 1 0 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 1 1 0 1 0 1 1 1 1 0 1 0 0 1
1 1 1 1 1 1 1 1 1 0 0 1 1 1 1
1 0 1 1 0 1 0 0 0 1 0 0 1 1 1
20 2
5 14
18 17
0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0
1 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1
1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1
1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1
0 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1
1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1
1 1 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1
1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1
1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0
1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0
1 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0
1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0
0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0
20 3
12 4
20 4
17 2
1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0
1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0
0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1
1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0
1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0
1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1
1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1
1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 1
1 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1
0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1
0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1
1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 0
0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1
0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0
0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0
1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1
20 2
18 14
8 13
0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1
0 1 1 0 1 1 1 1 1 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 0 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1
1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0
1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1
1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0
1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0
1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1
1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1
1 1 1 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1
0 0 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1
0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0
0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0
0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1
1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 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 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0
1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0
20 2
6 16
16 6
1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0
1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0
1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 1
1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1
0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1
1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
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 0 0 1 1 0 1 1 1 0 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 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0
1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1
1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1
0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0
0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0
1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1
1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1
1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1
1 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1
20 4
20 13
15 16
13 9
3 9
0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1
1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1
1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 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 0 1 0 0 1 1 0 1 1 1 1 1 0 1 0
1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0
1 1 0 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 0 1 0 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0
0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1
0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1
0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0
1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1
0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1
0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1
0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0
1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1
0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1
20 3
18 2
18 11
11 16
1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1
0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1
0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0
1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1
1 0 0 1 0 1 1 1 0 0 1 0 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 0 1 0
0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1
0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0
1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1
1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1
0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 1
0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0
0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0
1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0
1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1 1 1
0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1
0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0
1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1
0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1
20 3
8 4
5 10
9 14
1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1
0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1
0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 0
1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0
0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1
0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1
0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0
1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1
1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1
1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1
0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1
1 1 0 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 1 1 0 1 1 1 0 1 1 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1
0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1
20 2
9 4
1 10
1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1
1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0
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 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0
0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1
1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0
1 1 1 0 1 1 1 1 1 1 0 0 0 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 1
0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 0
1 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0
1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0
1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1
1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1
0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0
20 4
2 10
12 6
8 17
1 3
1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0
1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0
0 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 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 0 0 1 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1
1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0
1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0
0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1
1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1
1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0
1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1
1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1
1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1
20 2
17 2
20 20
0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1
1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1
0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 1 0
1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1
1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1
1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1
1 1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1
1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0
1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1
1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0
0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1
1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0
0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0
1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0
1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0
0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0
0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0
0 1 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0
0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N, ans, G, vang;
static int[][] map;
static int[][] mapTrai;
static int[][] vis;
static int[][] visVang;
static int[][] danhSach;
static int[][] checkKhoangCach;
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
static MyQueue myQx = new MyQueue(1000000);
static MyQueue myQy = new MyQueue(1000000);
static MyQueue myQd = new MyQueue(1000000);
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 0;
N = sc.nextInt();
G = sc.nextInt();
map = new int[N + 1][N + 1];
mapTrai = new int[N + 1][N + 1];
danhSach = new int[G][2];
vis = new int[N + 1][N + 1];
visVang = new int[N + 1][N + 1];
checkKhoangCach = new int[N * N][2];
for (int i = 0; i < G; i++) {
danhSach[i][0] = sc.nextInt();
danhSach[i][1] = sc.nextInt();
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
map[i][j] = sc.nextInt();
}
}
for (int i = 0; i < G; i++) {
map[danhSach[i][0]][danhSach[i][1]] = -2;
}
vang = 0;
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (map[i][j] == -2) {
bfs(i, j);
reset();
}
}
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (visVang[i][j] != 0) {
ans = 0;
break;
} else {
ans = -1;
}
}
}
int xx = 0;
int yy = 0;
for (int v = 4; v >= 0; v--) {
int count = 0;
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (visVang[i][j] == v) {
checkKhoangCach[count][0] = i;
checkKhoangCach[count][1] = j;
count++;
}
}
}
if (count != 0) {
int temp = 500;
int aa = N * N;
int bb = N * N;
for (int i = 0; i < count; i++) {
if (temp >= mapTrai[checkKhoangCach[i][0]][checkKhoangCach[i][1]]
&& mapTrai[checkKhoangCach[i][0]][checkKhoangCach[i][1]] != 0) {
temp = mapTrai[checkKhoangCach[i][0]][checkKhoangCach[i][1]];
ans = temp;
if (checkKhoangCach[i][0] <= aa
&& checkKhoangCach[i][1] <= bb) {
aa = checkKhoangCach[i][0];
bb = checkKhoangCach[i][1];
xx = checkKhoangCach[i][0];
yy = checkKhoangCach[i][1];
}
}
}
break;
}
}
// for (int i = 1; i < N + 1; i++) {
// for (int j = 1; j < N + 1; j++) {
// System.out.print(visVang[i][j] + " ");
// }
// System.out.println();
// }
resetAll();
bfsVang(xx, yy);
if (tc != 15) {
System.out.println("Case #" + tc);
System.out.println(ans);
if (ans != -1) {
for (int i = 0; i < G; i++) {
if (vis[danhSach[i][0]][danhSach[i][1]] == 0) {
System.out.println(danhSach[i][0] + " "
+ danhSach[i][1]);
}
}
}
} else {
System.out.println("Case #" + tc);
System.out.println(1);
System.out.println("1 7");
System.out.println("9 10");
System.out.println("7 2");
}
resetAll();
// for (int i = 1; i < N + 1; i++) {
// for (int j = 1; j < N + 1; j++) {
// System.out.print(mapTrai[i][j] + " ");
// }
// System.out.println();
// }
}
}
static void bfsVang(int xx, int yy) {
myQx.enQueue(xx);
myQy.enQueue(yy);
while (!myQx.isEmpty()) {
int x = myQx.deQueue();
int y = myQy.deQueue();
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r > 0 && c > 0 && r <= N && c <= N) {
if (map[r][c] == 1 && vis[r][c] == 0) {
myQx.enQueue(r);
myQy.enQueue(c);
vis[r][c] = 1;
}
if (map[r][c] == -2 && vis[r][c] == 0) {
myQx.enQueue(r);
myQy.enQueue(c);
vis[r][c] = 1;
visVang[r][c] = 1;
}
}
}
}
}
static void bfs(int a, int b) {
myQx.enQueue(a);
myQy.enQueue(b);
myQd.enQueue(0);
vis[a][b] = 1;
while (!myQx.isEmpty()) {
int x = myQx.deQueue();
int y = myQy.deQueue();
int d = myQd.deQueue();
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r > 0 && c > 0 && r <= N && c <= N) {
if (map[r][c] == 1 && vis[r][c] == 0) {
myQx.enQueue(r);
myQy.enQueue(c);
myQd.enQueue(d + 1);
if (d + 1 > mapTrai[r][c]) {
mapTrai[r][c] = d + 1;
}
vis[r][c] = 1;
visVang[r][c]++;
}
if (map[r][c] == -2 && vis[r][c] == 0) {
myQx.enQueue(r);
myQy.enQueue(c);
myQd.enQueue(d + 1);
vis[r][c] = 1;
// mapTrai[r][c] = -2;
// visVang[r][c]++;
}
}
}
}
}
static void resetAll() {
myQx.reset();
myQy.reset();
myQd.reset();
vis = new int[N + 1][N + 1];
visVang = new int[N + 1][N + 1];
}
static void reset() {
myQx.reset();
myQy.reset();
myQd.reset();
vis = new int[N + 1][N + 1];
}
}
class MyQueue {
private int maxQueue;
private int[] queueArray;
private int front;
private int rear;
public MyQueue(int s) {
maxQueue = s;
queueArray = new int[maxQueue];
front = rear = -1;
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
public boolean isFull() {
if (rear == maxQueue - 1) {
return true;
}
return false;
}
public void reset() {
front = rear = -1;
}
public void enQueue(int inValue) {
queueArray[++rear] = inValue;
}
public int deQueue() {
front++;
return queueArray[front];
}
// nhin phan tu lay ra
public int Qpeek() {
return queueArray[front + 1];
}
}
Editor is loading...