Cặp ghép với số đỉnh rất lớn

Cặp ghép với số đỉnh rất lớn

Võ Xuân Sơn

Trong số 26 (11/2001), tác giả Lê Văn Chương đã giới thiệu cho chúng ta thuật toán Kuhn

− Munkres giải bài toán tìm cặp ghép có tổng trọng số lớn nhất, nhỏ nhất nhưng với số

đỉnh rất bé. Sau đây, dựa theo thuật toán Kuhn − Munkres tôi trình bày bài toán cặp ghép

với số đỉnh rất lớn (nhỏ hơn 5000 đỉnh).

Ví dụ minh hoạ.

Bài toán xếp hình:

1 trò chơi xếp hình trên máy tính từ những ô hình vuông kích thước giống nhau. Mỗi ô

hình vuông này được chia thành 4 tam giác, mỗi tam giác có thể nhận 1 trong 4màu đỏ,

xanh, vàng, trắng. (quy ước: 0 − đỏ; 1 − xanh; 2 − vàng; 3− trắng)

như hình vẽ:

Người chơi cần dùng chuột kéo những ô vuông đã cho vào một lưới ô vuông M hàng, N

cột đến khi đầy lưới sau đó có thể nhấn chuột để quay ô. Mỗi lần nhấn chuột ô quay 1 góc

900

theo chiều kim đồng hồ. Giả thiết mỗi lần kéo một ô vuông vào một vị trí của lưới mất

1s và mỗi lần nhấn chuột mất 1s. Bằng những thao tác như vậy, người chơi cần tạo ra một

hình giống như hình mẫu cho trước với thời gian nhanh nhất.

Các ô vuông đã cho được đánh số từ 1. Trạng thái của ô vuông được mã hoá bằng 1 byte (8

bit) như sau: hai bit trái nhất mô tả giá trị mầu của tam giác phía Bắc, lần lượt các nhóm 2

bit tiếp theo mô tả giá trị mầu của các tam giác phía Đông, Nam, Tây của ô vuông.

Dữ liệu vào: Xephinh.inp (m, n ≤ 50)

Dữ liệu ra: Xephinh.out

Nếu không có cách xếp thì ghi -1

Ví dụ: