Untitled
plain_text
23 days ago
29 kB
3
Indexable
Never
Hugo Đào Vàng 2 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: X 1 2 X: Vị trí Gold Đá Đườ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: X X X Thời gian là 4 Thời gian là 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] 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] - 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 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1 #include <iostream> #define MIN 99999999 using namespace std; int n, g; int arr[21][21]; int visited[21][21]; int dR[4] = { -1, 0, 1, 0 }; int dC[4] = { 0, 1, 0, -1 }; int arrTG[5][21][21]; typedef struct Point{ int x, y; }; Point G[5]; typedef struct Queue { int front, rear; Point data[10001]; }; void init(Queue& Q) { Q.front = Q.rear = -1; } void push(Queue& Q, Point value) { Q.rear++; Q.data[Q.rear] = value; } Point top(Queue& Q) { Point temp; Q.front++; temp = Q.data[Q.front]; Q.front--; return temp; } void pop(Queue& Q) { Q.front++; } bool empty(Queue& Q) { if (Q.front == Q.rear) return true; return false; } Queue Q; void BFS(int index, Point P){ init(Q); push(Q, P); visited[P.x][P.y] = 1; arrTG[index][P.x][P.y] = 0; while(!empty(Q)){ Point P1; P1 = top(Q); pop(Q); for(int k=0; k<4; k++){ int x = P1.x + dR[k]; int y = P1.y + dC[k]; if(x>=1 && x<=n && y>=1 && y<=n && visited[x][y] == 0 && arr[x][y] != 0){ visited[x][y] = 1; arrTG[index][x][y] = arrTG[index][P1.x][P1.y] + 1; Point P2; P2.x = x; P2.y = y; push(Q, P2); } } } } void reset1(){ for(int v=1; v<=g; v++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ arrTG[v][i][j] = -1; } } } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ arr[i][j] = 0; } } } void reset2(){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ visited[i][j] = 0; } } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n >> g; reset1(); int r, c; for(int i=1; i<=g; i++){ cin >> r >> c; G[i].x = r; G[i].y = c; arr[r][c] = 1; } int g1 = 0; int m; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ cin >> m; arr[i][j] += m; if(arr[i][j] == 2) g1++; } } for(int v=1; v<=g; v++){ reset2(); Point P; P.x = G[v].x; P.y = G[v].y; BFS(v, P); } int sumV = -1; int MinTG = MIN; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(arr[i][j] == 1){ int countV = 0; int MaxTG = -1; for(int v=1; v<=g; v++){ if(arrTG[v][i][j] >= 1){ countV++; MaxTG = max(MaxTG, arrTG[v][i][j]); } } if(countV > sumV){ sumV = countV; MinTG = MaxTG; } if(countV == sumV){ if(MinTG > MaxTG){ MinTG = MaxTG; } } } } } cout << "Case #" << tc << endl; if(sumV == g1){ cout << MinTG << endl; } else{ cout << "-1" << endl; } } return 0; } 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