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

Bài tập huấn luyện: Bắn bi

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


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


Đề bài


(Thi HSG Quốc gia năm 1999- Bảng A)

Trò chơi bắn bi trên một bảng vuông N dòng, N cột được thực hiện như sau: Các viên bi được bắn từ mép trái phí bên ngoài bẳng theo những dòng nào đấy. Tại những vị trí giao của dòng và cột của bảng có thể đặt một số vật cản. Các vật cản có hai trạng thái 1 và 2. Nếu không gặp vật cản, bi sẽ chuyển động không đổi hướng, nếu gặp vật cản trạng thái 1, bi sẽ rẽ trái (vuông góc) với hướng đang chuyển động và làm vật cản chuyển sang trạng thái 2, còn nếu gặp vật cản trạng thái 2, bi sẽ rẽ phải (vuông góc) với hướng chuyển động và làm vật cản chuyển sang trạng thái 1. Viên bi sẽ ra khỏi bảng tại một vị trí nào đấy thuộc một trong bốn mép của bảng. Một mục tiêu làm đích được đặt ở ngoài bảng phía mép phải, tại một vị trí thẳng hàng với một dòng nào đấy của bảng. Yêu cầu của trò chơi là phải hạ được mục tiêu bằng cách bắn lần lượt một số ít nhất viên bi (viên bi trước phải ra khỏi bảng mới được bắn viên bi tiếp), những viên bi đầu (nếu cần phải có) dùng để thay đổi trạng thái của bảng và viên bi cuối cùng dùng để bắn trúng đích.

Dữ liệu: Thông tin ban đầu của bảng vào từ file văn bản BI.INP:

  • Dòng đầu tiên ghi giá trị N (1£N£30
  • N dòng tiếp theo ghi lần lượt các dòng của bảng, mỗi dòng gồm N giá trị thuộc tập hợp {0,1,2} ghi cách nhau ít nhất một dấu trắng, trong đó 0 là vị trí không có vật cản, 1 và 2 là vị trí có vật cản với trạng thái tương ứng.
  • Dòng cuối cùng ghi chỉ số dòng của bảng mà thẳng hàng với nó là vị trí đặt mục tiêu. Các dòng của bảng được đánh số từ 1 đến N theo chiều từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến N theo chiều từ trái sang phải.

Kết quả: Ghi ra file văn bản BI.OUT:

  • Dòng đầu tiên ghi M là số viên bi cần bắn (qui ước M=0 nếu không có cách nào hạ được mục tiêu).
  • Nếu M>0 thì dòng tiếp theo ghi M số (cách nhau ít nhất một dấu trắng) lần lượt là chỉ số dòng tại đó các viên bi được bắn

Giới hạn số các vật cản không quá 15

Ví dụ:

BI.INP BI.OUT
4

0 0 0 2

0 2 1 0

0 1 1 0

0 0 0 1

2

4

3 2 3 2

 

 


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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

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

NCT Computer

Flickr Photos

Thống kê

  • 148,943 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: