Giả sử một số hình trên giấy bình phương. Sides của hình đi thẳng trên các dòng giấy bình phương. Hình có thể có bất kỳ hình dạng nào (thậm chí không lồi). Cách tìm số lượng domino tối đa (1x2 hình chữ nhật) có thể được đặt trong hình đó. Nó không được phép để domino hơn một số khác. Chỉ được phép đặt domino theo cách như vậy, khi các mặt của nó rơi chính xác trên các dòng giấy bình phương.số lượng tối đa các domino có thể được đặt bên trong một hình
Trông giống như maximum cardinality matching problem in a bipartite graph. Các ô vuông là các đỉnh và các domino là các cạnh thuộc về khớp.
Để thấy rằng biểu đồ là hai mặt, hãy tưởng tượng các ô vuông được vẽ cờ bàn. Màu đen chỉ có màu trắng láng giềng và ngược lại.
+1 Tuyệt đẹp. Tôi đang đá chính mình vì không thấy điều này. :-) – templatetypedef
wow, đẹp! có vẻ đúng! –
Giải pháp này có thể được tổng quát hóa không? Điều gì nếu các domiNos là 3x1 hoặc 4x2, ví dụ? – templatetypedef
Bạn có thể phân loại hình vuông bằng của số hàng xóm vuông free as type 0, 1, 2, 3 hoặc 4.
tôi tin rằng sẽ làm việc:
tìm một hình vuông loại 1, đặt có một ứng domino trong cách duy nhất có thể và lặp lại
khác, hãy tìm một góc tự do được hình thành bởi hai loại tiếp giáp 2 và loại 3 hình vuông, nơi có một ứng domino và đi đến 1
khác, đặt một ứng domino trong bất kỳ vuông tuýp 2 và đi đến 1
bạn đang thực hiện
Vâng, đây là cơ bản những gì các thuật toán kết hợp tối đa đơn giản nhất. –
những gì bạn đã cố gắng để tìm hiểu chính mình? những gì chính xác là vấn đề của bạn ở đây? Bạn có thể cho một số ví dụ? là bài tập về nhà này? – oezi
nó không phải là một bài tập về nhà, tôi nhận được vấn đề này từ bạn của tôi, đã cố gắng giải quyết nó bằng bút chì và giấy và có thể không. Bây giờ tôi không biết giải pháp nào ngoại trừ sức mạnh vũ phu. Tôi đã thử một số thông thường, nhưng luôn có một ví dụ khi giải pháp của tôi không tốt nhất. –
@Sega: bạn cần nêu rõ câu hỏi chính xác hơn hoặc có thể nó sẽ bị đóng. Ví dụ, ranh giới được xác định như thế nào? –