MÁY ĐỔI THẺ TỰ ĐỘNG CÓ MỘT MÁY GIẢI TRÍ TỰ ĐỘNG CÓ M CỬA DÙ...
Bài 3. Máy đổi thẻ tự động
Có một máy giải trí tự động có M cửa dùng để đổi thẻ. Có các thẻ mã số từ 1,..,N. Nếu ta bỏ
thẻ có mã số i vào một cửa nào đó thì máy sẽ thu thẻ đó và cho ra một thẻ có mã số nào đó
trong khoảng 1..N. Máy đổi thẻ hoạt động theo thông tin ghi trong tệp văn bản THE.INP:
- Dòng đầu tiên ghi các số N, M, x, y (1 M, N 200, 1 x,y N);
- N dòng tiếp theo, mỗi dòng chứa M số tạo thành một bảng có kích thước N x M. Phần
tử nằm trên dòng i, cột j của bảng này cho biết nếu ta bỏ thẻ có số hiệu i vào cửa j thì sẽ thu
được thẻ có số hiệu chính là giá trị của phần tử đó;
- Các số trên mỗi dòng của tệp ghi cách nhau ít nhất là một ký tự trống.
Với mỗi cặp thẻ có số hiệu x và y cho trước (x<>y), hãy cho biết có cách nào nhanh nhất để
dùng thẻ có số hiệu x thu được thẻ có số hiệu y hay không?
Dữ liệu ra là tệp văn bản THE.OUT trình bày theo dạng:
Bỏ thẻ x vào cửa ... thu được thẻ ...
...
Bỏ thẻ ... vào cửa ... thu được thẻ y
Nếu không tìm được cách để từ thẻ có số hiệu x thu được thẻ có số hiệu y thì ghi vào tệp
thông báo ‘Tu the x khong thu duoc the y’.
Ví dụ:
Tệp
THE.INP
Tệp
THE.OUT
Tệp
THE.OUT
Bo the 2 vao cua 1 thu duoc the 3
5 4 2 1
Tu the 4 khong thu duoc the 5
5 4 4 5
2 2 2 4
Bo the 3 vao cua 1 thu duoc the 1
2 3 5 1
3 4 4 3
1 4 4 4
1 5 2 4
5 3 2 1
1 1 2 2
3 4 2 4