Untitled
unknown
plain_text
a year ago
28 kB
9
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.
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]
- Hugo có thể đi theo 4 hướng (trên/dưới/trái/phải)
- Hugo không thể cắm trại ở vị trí mỏ vàng hoặc
- Hugo có thể đi qua mỏ vàng để đến mỏ vàng
- Hugo cần đặt vị trí trại để tối đa hóa số lượng mỏ vàng có thể khai thác
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
#include<iostream>
using namespace std;
int map_way[30][30], visit[30][30];
int G, N;
int result[400][3];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct node{
int r, c;
} Queue[10000];
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]=100000;
}
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);
int _cnt = 0;
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+dx[i];
int tempy = cur.c+dy[i];
if(tempx>=1 && tempx<=N && tempy>=1 && tempy<=N && visit[tempx][tempy]==100000 && map_way[tempx][tempy]==1){
push(tempx, tempy);
visit[tempx][tempy] = visit[cur.r][cur.c] + 1;
}
}
_cnt++;
if(_cnt==3*N){
//write something
return 0;
}
}
return 0;
}
int main()
{
int T;
ios::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
cin >> T;
for(int test_case = 1; test_case <= T; ++test_case)
{
//reset
for(int i=0; i<400; i++)
for(int j=0; j<3; j++)
result[i][j]=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];
}
}
int q=0;
int u=0, sum=0, _max=0;
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
bool check = false;
u=0; sum=0; _max=0; //so mo vang co the lay
//kiem tra neu trung mo vang thi exit
for(int k=0; k<G; k++){
if(i==mine[k].r && j==mine[k].c){
check = true;
break;
}
}
//k phai vang vs k phai da
if(check==false && map_way[i][j]==1){
for(int k=0; k<G; k++){
int kq;
kq = bfs(i, j, k);
if(kq>0) u+=1;
if(kq>_max) _max = kq;
sum+=kq;
}
}
if(u>0){
if(u>result[q-1][0] || sum<result[q-1][1]){
result[q][0] = u;
result[q][1] = sum;
result[q][2] = _max;
q++;
}
}
}
}
//read data
if(result[0][0]==0)
cout << "Case #" << test_case << " " << -1 << endl;
else{
int index_best_value = 0;
int best = result[0][0];
for(int i=0; i<=q; i++){
if(result[i][0] > best);
}
}
}
return 0;//Your progrsam should return 0 on normal termination.
}Editor is loading...
Leave a Comment