Untitled
unknown
plain_text
2 years ago
28 kB
6
Indexable
*** De ***
Hugo Đào Vàng
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:
1 1 0 0 0
1 x 0 0 0
1 1 0 0 0
1 1 1 2 1
1 1 1 0 2
X: Vị trí
2-Gold
0-Đá
1-Đường
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:
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0
1 1 1 2 1
x 1 2 0 1
Thời gian là 4
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0
1 1 x 2 1
1 1 2 0 1
Thời gian là 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0
1 1 1 2 x
1 1 2 0 1
Thời gian là 3
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
*** input ***
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
*** output ***
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
Case #42
8
Case #43
1
18 14
Case #44
10
Case #45
10
20 13
Case #46
8
18 2
Case #47
7
Case #48
-1
Case #49
11
Case #50
1
17 2
*** code ***
#include<iostream>
using namespace std;
#define cons 25
int n,so_movang;
int gold_x[cons];
int gold_y[cons];
int arr_map[cons][cons];
int index_gold[cons][cons];
int maxmax,minmin;
bool kiem_tra[cons];
bool kiemtra_temp[cons];
int min_index;
int dem_gold;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct Queue
{
int rear,front;
int arr_data[100000];
Queue()
{
rear = front = 0;
}
bool isEmpty()
{
return rear == front;
}
void push(int a)
{
arr_data[rear] = a;
rear++;
rear = rear % 100000;
}
int pop()
{
int a = arr_data[front];
front++;
front = front % 100000;
return a;
}
};
void BFS(int vt_hang,int vt_cot)
{
for (int i = 0; i < so_movang; i++)
{
kiemtra_temp[i] = false;
}
maxmax = 0;
dem_gold = 0;
int check_BFS[cons][cons];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
check_BFS[i][j] = -1;
}
}
Queue Q = Queue();
Q.push(vt_hang);
Q.push(vt_cot);
check_BFS[vt_hang][vt_cot] = 0;
while (!Q.isEmpty())
{
int x = Q.pop();
int y = Q.pop();
for (int i = 0; i < 4; i++)
{
int hang = x + dx[i];
int cot = y + dy[i];
if(hang>=1 && hang<=n && cot>= 1 && cot<=n && arr_map[hang][cot] !=0 && check_BFS[hang][cot] == -1)
{
check_BFS[hang][cot] = check_BFS[x][y] + 1;
Q.push(hang);
Q.push(cot);
if(arr_map[hang][cot] == 9)
{
dem_gold++;
kiemtra_temp[index_gold[hang][cot]] = true;
if(check_BFS[hang][cot] > maxmax )
{
maxmax = check_BFS[hang][cot];
}
}
}
}
}
}
int main()
{
// freopen("input.txt","r",stdin);
int th;cin>>th;
for (int tc = 1; tc <= th; tc++)
{
cin >> n >> so_movang;
for (int i = 0; i < so_movang; i++)
{
cin >> gold_x[i] >> gold_y[i];
index_gold[gold_x[i]][gold_y[i]] = i;
kiem_tra[i] = false;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr_map[i][j];
}
}
for (int i = 0; i < so_movang; i++)
{
arr_map[gold_x[i]][gold_y[i]] = 9;
}
maxmax =0;
minmin = 999999;
int sl = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if(arr_map[i][j] == 1)
{
BFS(i,j);
if(dem_gold > sl)
{
sl = dem_gold;
minmin = maxmax;
for (int k = 0; k < so_movang; k++)
{
kiem_tra[k] = kiemtra_temp[k];
}
}
else if(dem_gold == sl)
{
if(maxmax != 0)
{
if(minmin > maxmax)
{
minmin = maxmax;
for (int k = 0; k < so_movang; k++)
{
kiem_tra[k] = kiemtra_temp[k];
}
}
}
}
}
}
}
cout << "Case #" << tc << endl;
if(minmin == 999999)
{
cout << -1 << endl;
}
else
{
cout << minmin << endl;
for (int i = 0; i < so_movang; i++)
{
if(kiem_tra[i] == false)
{
cout << gold_x[i] << " " << gold_y[i] << endl;
}
}
}
}
return 0;
}
Editor is loading...