//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Các tuyến xe buýt

 

Năm 2050, thành phố Hà Nội thiết lập một hệ thống xe buýt rất độc đáo. Thành phố được chia thành M × N khu vực và các tuyến xe buýt được thiết kế để chạy giữa M × N khu vực đó. Các khu vực được xác định bằng chỉ số dòng và chỉ số cột, các dòng được đánh số từ 1 đến M từ trên xuống dưới, các cột được đánh số từ 1 đến N từ trái sang phải, khu vực (U, V) là khu vực ô tại dòng U, cột V. Các tuyến xe bus được chia thành 6 loại như sau:

A (Aduka) B (Bomber) T (Trico) R (Rayon) M (Mage) N (Nak Machine)

Tại mỗi khu vực, sẽ chỉ có 1 trong 6 loại tuyến xe xuất phát từ đó nhưng một tuyến xe đó sẽ có 4 hướng xuất phát như hình đã mô tả nhưng được quay đi các góc 90°. Ví dụ tại khu vực (U, V) chỉ có tuyến xe A xuất phát. Sẽ có 4 cách đi như hình bên. Ô in đậm là ô xuất phát (U, V). Ta quy ước rằng nếu một tuyến xe mà lộ trình của nó đi ra ngoài khu vực Hà Nội rồi lại quay lại và kết thúc tại một khu vực trong Hà Nội thì vẫn được phép. Nếu tuyến xe đi ra ngoài khu vực Hà Nội rồi không quay lại (kết thúc tại một khu vực ngoài Hà Nội) thì coi như không có tuyến xe đó.

Bạn cần đi từ khu vực (X1, Y1) đến khu vực (X2, Y2), hãy tìm một cách đi sao cho phải chuyển xe buýt ít lần nhất. Lưu ý rằng xe buýt sẽ không dừng dọc đường, chỉ dừng ở điểm đầu và điểm cuối.

InputBUS.INP

  • Dòng thứ nhất ghi 6 số M, N, X1, Y1, X2, Y2 nguyên dương.
  • M dòng tiếp theo, mỗi dòng ghi một xâu gồm N kí tự thuộc 1 trong 6 ký tự ‘A’, ‘B’, ‘T’, ‘R’, ‘M’, ‘N’. Kí tự thứ V của xâu thứ U thể hiện tuyến xe buýt xuất phát từ ô (U, V).

Output:            BUS.OUT

  • Dòng đầu tiên ghi số P là số chuyến xe buýt ít nhất mà bạn đi.
  • P dòng tiếp theo, mỗi dòng ghi 1 cặp số thể hiện địa điểm mà bạn lên xe buýt.

Giới hạn:

  • 1 ≤ M, N ≤ 1000
  • Thời gian: 1 s/test
  • Bộ nhớ: 8MB

Ví dụ:

BUS.INP BUS.OUT
3 4 1 2 1 4

AAAA

BBBB

TTTT

2

1 2

3 3

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: