Untitled
unknown
plain_text
2 years ago
29 kB
10
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.
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.
}Editor is loading...
Leave a Comment