Hugo daovang1

 avatar
quoc14
c_cpp
23 days ago
28 kB
5
Indexable
Never
DFS and BFS
Level 3
Hugo Đào Vàng 2
Hugo đào vàng trả nợ (BFS theo so mo vang)

Sau khi ăn trộm được mật của chị ong nâu và say sưa thưởng thức mật ngọt say đắm thì bất ngờ Hugo bị chị ong nâu phát hiện. Mặc dù đã thành khẩn nhận lỗi và xin lỗi chị ong nâu nhưng do đã đánh chén gần hết số mật đã ăn chộm nên chị ong nâu vẫn bắt Hugo phải bồi thường số mật đó. Hugo thì làm sao có thể kiếm mật được vì vậy Hugo phải đi đào vàng kiếm tiền để có tiền mua mật trả cho chị ong nâu.

Một cách tình cờ Hugo có được bản đồ của một khu vực chứa vàng, bản đồ được vẽ dựa trên một ma trận NxN. Trong ma trận có các điểm chứa vàng có thể khai thác (Tối đa 4 điểm). Hàng ngày Hugo sẽ phải đi tới mỏ vàng để khai thác và cuối ngày sẽ phải mang vàng trở về. Để tiết kiệm chi phí và thời gian, Hugo quyết định cắm trại trên gần mỏ vàng để tiện khai thác vàng. Hugo không thể di chuyển qua khu vực đá và không thể cắm trại trên đá, đồng thời Hugo cũng không thể cắm trại tại khu vực mỏ vàng, thời gian để Hugo di chuyển qua mỗi ô là 1 giờ.

Hãy giúp Hugo tìm địa điểm tối ưu để đi khai thác tất cả các mỏ vàng nhanh nhất.

Xem xét ma trận mỏ vàng 5x5 bên dưới:

Có 2 mỏ vàng, nếu Hugo cắm trại tại vị trí X, Hugo sẽ mất 4 giờ để đi tới mỏ vàng thứ 1, và 6 giờ để đi tới mỏ vàng thứ 2, vì vậy thời gian nhỏ nhất để Hugo đi khai thác vàng là 6 giờ, thời gian lớn nhất để đi khai thác của tất cả các mỏ vàng.

Xem xét ví dụ khác:

Thời gian tối ưu với ma trận mỏ vàng trên là 1.

Một mỏ vàng được coi là không thể tiếp cận khi không thể đặt 1 vị trí cắm trại nào để đi khai thác vàng.

[Input]

Số trường hợp thử nghiệp T (T ≤ 50)

Mỗi TC :

 - Dòng đầu tiên chứa kích thước ma trận N (N ≤ 20) và số mỏ vàng G (2 ≤ G ≤ 4)

 - G dòng tiếp theo đưa ra vị trí R (hàng) & C (cột) của mỏ vàng (Chỉ số bắt đầu từ 1)

- N dòng tiếp theo là thông tin ma trận: 1 là có đường đi và vị trí mỏ vàng, 0 là đá (không thể đi qua).

 

[Output]

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

Case #1

1

Case #2

2

Case #3

2

 

 

[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

Case #1
1
Case #2
2
Case #3
2
Case #4
7
Case #5
-1
Case #6
8
Case #7
2
Case #8
4
Case #9
6
Case #10
-1
Case #11
-1
Case #12
1
Case #13
-1
Case #14
-1
Case #15
-1
Case #16
-1
Case #17
8
Case #18
-1
Case #19
-1
Case #20
7
Case #21
7
Case #22
2
Case #23
10
Case #24
9
Case #25
-1
Case #26
6
Case #27
-1
Case #28
-1
Case #29
8
Case #30
3
Case #31
5
Case #32
10
Case #33
12
Case #34
12
Case #35
-1
Case #36
13
Case #37
-1
Case #38
8
Case #39
3
Case #40
11
Case #41
-1
Case #42
8
Case #43
-1
Case #44
10
Case #45
-1
Case #46
-1
Case #47
7
Case #48
-1
Case #49
11
Case #50
-1
Time: 0.17200 s.

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
    
#include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, g, mp[21][21], vs[401][5], gold[5][2];
int result;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int q[401][2], head, tail;

void bfs(int X, int Y, int index){
	head = 0, tail = 0;
	vs[X*n+Y][index]++;
	q[tail][0] = X, q[tail++][1] = Y;

	while(head != tail){
		int x = q[head][0];
		int y = q[head][1];
		head++;
		for(int d = 0; d < 4; d++){
			int xx = x + dx[d];
			int yy = y + dy[d];
			if(xx >= 0 && yy >= 0 && xx < n && yy < n && vs[xx*n+yy][index] == 0){
				vs[xx*n+yy][index] = vs[x*n+y][index] + 1;
				q[tail][0] = xx, q[tail++][1] = yy;
			}
		}
	}
}

void update(int x, int y){
	int cnt = n, ans = -oo;
	for(int i = 0; i < g; i++){
		if(vs[x*n+y][i] == 0){
			cnt--;
		} else{
			if(ans < vs[x*n+y][i] - 1) ans = vs[x*n+y][i] - 1;
		}
	}
	if( cnt == n && ans < result){
		result = ans;
	}
}


int main(){

	freopen("input.txt", "r", stdin);

	// Calc clock
	clock_t time_start, time_end; 
	time_start = clock(); 
	
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		cin >> n >> g;
		for(int i = 0; i < g; i++){
			cin >> gold[i][0] >> gold[i][1];
			gold[i][0]--, gold[i][1]--;
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cin >> mp[i][j];
				for(int t = 0; t < g; t++){
					if(mp[i][j] == 0) vs[i*n+j][t] = -1;
					else vs[i*n+j][t] = 0;
				}
			}
		}
		for(int i = 0; i < g; i++){
			mp[gold[i][0]][gold[i][1]] = 2;
		}
		result = oo;

		// Solve Problem 
		for(int i = 0; i < g; i++){
			bfs(gold[i][0], gold[i][1], i);
			/*
			for(int u = 0; u < n*n; u++){
				cout << vs[u][i] << " ";
				if((u+1)%n == 0) cout << endl;
			}
			cout << endl;
			*/
		}

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(mp[i][j] == 1){
					update(i, j);
				}
			}
		}


		// Output
		cout << "Case #" << tc << endl << (result == oo ? -1 : result) << endl;
	}

	// Calc Time
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(5);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }
Leave a Comment