taylorbilly
02-11-2010, 17:24
Bài này áp dụng thuật toán loang sao ạ?
Rút gọn (rutgon.pas)
Cho một hình vuông H kích thước 2x2 được ghép từ 4 hình vuông đơn vị. Mỗi hình vuông đơn vị chứa một chữ cái khác nhau trong 4 chữ cái A, B, C, D. Trạng thái ban đầu của H là một trạng thái bất kỳ nào đó (hình 1 là một ví dụ).
Xét hai phép biến đổi trên H:
- Phép S - Đổi chỗ 2 hình vuông bên trên
- Phép R - Đổi chỗ vòng tròn theo chiều kim đồng hồ các hình vuông đi một vị trí
ví dụ
1234 --------> biến đổi S ----------------> 2134
1234 --------> biến đổi R ----------------> 4123
Yêu cầu: Cho dãy phép biến đổi, hãy tìm dãy biến đổi ngắn nhất cho cùng kết quả. Nếu có nhiều dãy kết quả thoả mãn thì đưa ra dãy có thứ tự từ điển nhỏ nhất.
Dữ liệu: Trong file văn bản RUTGON.INP gồm một chuỗi biểu diễn dãy biến đổi, độ dài chuỗi không quá 255 kí tự.
Kết quả: Ra file văn bản RUTGON.OUT ứng với mỗi bộ dữ liệu vào là xâu biến đổi ngắn nhất theo yêu cầu tương ứng. Nếu không phải biến đổi, ghi ra dòng trống.
Ví dụ:
RUTGON.INP RUTGON.OUT
RRRRSRRRR S
Gợi ý:
Số trạng thái tối đa của hình vuông H là 4! = 24 trạng thái. Như vậy xuất phát từ một trạng thái bất kì, không mất tổng quát ta giả sử là trạng thái S1 luôn là "1234". Với mỗi dãy biến đổi trong file RUTGON.INP ta thực hiện các thao tác để thu được trạng thái S2 tương ứng. Sau đó ta dùng thuật toán loang theo chiều rộng để tìm bước biến đổi ngắn nhất từ trạng thái S1 sang trạng thái S2.
Rút gọn (rutgon.pas)
Cho một hình vuông H kích thước 2x2 được ghép từ 4 hình vuông đơn vị. Mỗi hình vuông đơn vị chứa một chữ cái khác nhau trong 4 chữ cái A, B, C, D. Trạng thái ban đầu của H là một trạng thái bất kỳ nào đó (hình 1 là một ví dụ).
Xét hai phép biến đổi trên H:
- Phép S - Đổi chỗ 2 hình vuông bên trên
- Phép R - Đổi chỗ vòng tròn theo chiều kim đồng hồ các hình vuông đi một vị trí
ví dụ
1234 --------> biến đổi S ----------------> 2134
1234 --------> biến đổi R ----------------> 4123
Yêu cầu: Cho dãy phép biến đổi, hãy tìm dãy biến đổi ngắn nhất cho cùng kết quả. Nếu có nhiều dãy kết quả thoả mãn thì đưa ra dãy có thứ tự từ điển nhỏ nhất.
Dữ liệu: Trong file văn bản RUTGON.INP gồm một chuỗi biểu diễn dãy biến đổi, độ dài chuỗi không quá 255 kí tự.
Kết quả: Ra file văn bản RUTGON.OUT ứng với mỗi bộ dữ liệu vào là xâu biến đổi ngắn nhất theo yêu cầu tương ứng. Nếu không phải biến đổi, ghi ra dòng trống.
Ví dụ:
RUTGON.INP RUTGON.OUT
RRRRSRRRR S
Gợi ý:
Số trạng thái tối đa của hình vuông H là 4! = 24 trạng thái. Như vậy xuất phát từ một trạng thái bất kì, không mất tổng quát ta giả sử là trạng thái S1 luôn là "1234". Với mỗi dãy biến đổi trong file RUTGON.INP ta thực hiện các thao tác để thu được trạng thái S2 tương ứng. Sau đó ta dùng thuật toán loang theo chiều rộng để tìm bước biến đổi ngắn nhất từ trạng thái S1 sang trạng thái S2.