//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Biểu diễn xiếc

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 15


Đề bài


Xe đạp một bánh là hình ảnh quen thuộc trong các tiết mục biểu diễn xiếc. Để tăng tính hấp dẫn cho tiết mục, đạo diên quyết định “tin học hoá” nó: chia bánh xe đạp đặc (không có nan hoa) thành 5 sector, mỗi sector 720 và sơn 1 trong 5 màu khác nhau đánh số từ 1 đến 5. Sàn diễn được chia thành lưới M x N ô vuông, mỗi ô vuông có cạnh bằng 1/5 chu vi của bánh xe. Như vậy khi bánh xe tiếp xúc với sàn tại tâm của ô vuông theo một màu nào đó, thì sang ô bên cạnh – màu khác sẽ tiếp xúc với nó.

Diễn viên phải xuất phát từ ô ban đầu S tiến tới ô đích T sau khoảng thời gian ngắn nhất theo các qui tắc sau:

  • Quay mặt về phía nào thì phải theo hướng đó.
  • Chỉ được phép đi qua các ô trống.
  • Tại tâm một ô có thể xoay 900 về phía phải hay trái.
  • Xuất phát ở trạng thái màu CS tiếp xúc với sàn và kết thúc ở T với màu cT tiếp xúc với sàn.
  • Mỗi thao tác xoay hoặc chuyển sang ô mới mất 1 giây.

 

dt15

  • Ban đầu, diễn viên quay mặt về phía Bắc (Các dòng được dánh số từ 1 đến M theo chiều Bắc – Nam và các cột được đánh số từ 1 đến N theo chiều Tây – Đông)

Dữ liệu: Vào từ file văn bản CIRCUS.INP:

  • Dòng đầu tiên chứa 4 số nguyên M, N, cS, cT (0<M,N <= 50)
  • M dòng sau: mỗi dòng chứa một xâu N ký tự mô tả trạng thái của các dòng tương ứng với S – ô xuất phát, T – ô đích, # – ô có vật cản, dấu chấm (.) – ô trống.

Kết quả: Đưa ra file văn bản CIRCUS.OUT thời gian hoặc -1, nếu không thể đi được.

Ví dụ:

CIRCUS.INP CIRCUS.OUT
10 10 1 1

#S…….#

#..#.##.##

#.##.##.##

.#….##.#

##.##..#.#

#..#.##…

#……##.

..##.##…

#.###…#.

#…..###T

40

 

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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ả

Danh mục

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Palouse Falls at Sunrise (Palouse, WA)

Dartford Warbler

Herbal face

More Photos

Thống kê

  • 137,116 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: