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