lehuong168

các anh chị ơi em có 1 bài toán cô giáo ra mà không tài nào giải nổi các anh chị giúp em với ah!
đề bài:
Liệt kê toàn bộ các hoán vị của tập {1,2,...,n}. Có n con bọ được bố trí rải rác ngẫu nhiên trên các nút của 1 lưới ô vuông mà mỗi cạnh ô vuông bằng 1 đơn vị. Mỗi nút của lưới ô vuông được xác định bởi cặp tọa độ nguyên (x,y). các con bọ có thể di chuyển lên, xuống, trái, phải mỗi lần 1 đơn vị tương ứng với việc thay đổi các hoành độ hay tung độ 1 hay -1 đơn vị. các con bọ di chuyển sao cho cuối cùng chúng đứng thành thẳng nằm ngang, con bọ nọ cách con bọ kia: lúc đó vị trí các con bọ là (x,y) ; (x+1,y);...(x+n-1,y) với x,y nào đó. Giá trị Z của x,y cũng như thứ tự các con bọ kia là tùy ý. Yêu cầu: Tìm số lần di chuyển ít nhất để đạt được thỏa mãn yêu cầu trên tại mỗi nút của lưới ô vuông không thể có hơn 1 con bọ tại cùng 1 thời điểm.