Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
29 kB
1
Indexable
Never
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.
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.


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 


Case #1
1
Case #2
2
Case #3
2
Case #4
7
Case #5
3
1 9
Case #6
8
Case #7
2
Case #8
4
Case #9
6
Case #10
1
8 4
Case #11
1
4 3
4 5
6 10
Case #12
1
Case #13
4
6 8
Case #14
6
3 9
Case #15
1
1 7
9 10
7 2
Case #16
1
3 6
Case #17
8
Case #18
1
10 10
Case #19
3
6 8
Case #20
7
Case #21
7
Case #22
2
Case #23
10
Case #24
9
Case #25
2
11 10
10 10
Case #26
6
Case #27
1
2 11
Case #28
1
9 8
Case #29
8
Case #30
3
Case #31
5
Case #32
10
Case #33
12
Case #34
12
Case #35
5
2 2
Case #36
13
Case #37
12
6 10
4 15
Case #38
8
Case #39
3
Case #40
11
Case #41
1
5 14


#include<iostream>

using namespace std;

int map_way[30][30], visit[30][30];
int G, N;
pair<int, int> Oxy[4]={make_pair(-1,0), make_pair(0,1), make_pair(1,0), make_pair(0,-1)};

struct node{
    int r, c;
} Queue[401];
int front, rear;
void init(){
    front = rear = -1;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            visit[i][j]=1000000;
}
void push(int r, int c){
    rear++;
    Queue[rear].r = r;
    Queue[rear].c = c;
}
node pop(){
    return Queue[++front];
}
bool isEmpty(){
    return front==rear;
}

node mine[4];

int bfs(int x, int y, int kk){
    // BFS
    init();
    visit[x][y] = 0;
    push(x, y);
    while(!isEmpty())
    {
        node cur = pop();
        if(cur.r==mine[kk].r && cur.c==mine[kk].c) 
            return visit[cur.r][cur.c];
        for(int i=0; i<4; i++)
        {
            int tempx = cur.r+Oxy[i].first;
            int tempy = cur.c+Oxy[i].second;
            if(tempx>=1 && tempx<=N && tempy>=1 && tempy<=N && visit[tempx][tempy]==1000000 && map_way[tempx][tempy]!=0){
                push(tempx, tempy);
                visit[tempx][tempy] = visit[cur.r][cur.c] + 1;
            }
        }
    }
    return 0;
}
int main()
{
    int T;
    int main_result[200][6], _p_result[4];

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("input.txt", "r", stdin);
    cin >> T;

    for(int test_case = 1; test_case <= T; ++test_case)
    {

        //reset
        main_result[0][0]=0;

        cin >> N >> G;
        //doc vi tri mo vang
        for(int i=0; i<G; i++)
            cin >> mine[i].r >> mine[i].c;
        //doc map duong di
        for(int ii=1; ii<=N; ii++)
            for(int jj=1; jj<=N; jj++)
                cin >> map_way[ii][jj];

        for(int i=0; i<G; i++)
            map_way[mine[i].r][mine[i].c]=2;

        int q=0;
        int u=0, _max=0, best_u=0;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                u=0; _max=0;
                //k phai vang vs k phai da
                if(map_way[i][j]==1){
                    for(int k=0; k<G; k++){
                        int kq = bfs(i, j, k);
                        if(kq>0){
                            u+=1;
                            _p_result[k]=1;
                        }else{
                            _p_result[k]=0;
                            continue;
                        }
                        if(kq>_max) _max = kq;
                    }
                    if(u>0){
                        if(u > best_u) best_u=u;
                        if(u>=best_u && q>0){
                            main_result[q][0] = u;
                            main_result[q][1] = _max;
                            for(int aa=0; aa<G; aa++)
                                main_result[q][2+aa]=_p_result[aa];
                            q++;
                        } else if(q==0){ //first
                            main_result[q][0] = u;
                            main_result[q][1] = _max;
                            for(int aa=0; aa<G; aa++)
                                main_result[q][2+aa]=_p_result[aa];
                            q++;
                        }
                    }
                }
            }
        }
        //read data & print
        if(best_u==0)
            cout << "Case #" << test_case << endl << -1 << endl;
        else{
            int best_answer=10000, index;
            for(int aa=0; aa<q; aa++){
                if(main_result[aa][0]==best_u && main_result[aa][1] < best_answer){
                    best_answer = main_result[aa][1];
                    index = aa;
                }
            }
            if(best_u==G)
                cout << "Case #" << test_case <<  endl << main_result[index][1] << endl;
            else{
                cout << "Case #" << test_case <<  endl << main_result[index][1] << endl;
                for(int _ct=0; _ct<G; _ct++){
                    if(main_result[index][2+_ct]==0){
                        cout << mine[_ct].r << " " << mine[_ct].c << endl;
                    }
                }
            }

        }
    }
    return 0;//Your progrsam should return 0 on normal termination.
}
Leave a Comment