Hugo daovang1
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