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

Bài tập huấn luyện: Trò chơi bong bóng

Nhìn kìa, có nhiều bong bóng đang bay trên trời.
Ta hãy cùng thổi chúng nào!

Cho một lưới ô vuông kích thước N x N, mỗi ô của lưới được biểu diễn bởi một ký tự với ý nghĩa là:

Ký tự Ý nghĩa
. ô trống
* ô đích
N một bong bóng đang bay về phía Bắc
E một bong bóng đang bay về phía Đông
W một bong bóng đang bay về phía Tây
S một bong bóng đang bay về phía Nam
một bong bóng đang lơ lửng và không di chuyển

Các bong bóng được đánh số 1, 2, 3… từ Bắc xuống Nam rồi từ Tây sang Đông.

Các dòng và các cột của lưới đuợc đánh số từ 0 đến N – 1, ô tại dòng i cột j được gọi là ô (i, j). Biết rằng góc Tây-Bắc của lưới là (0, 0), góc Đông-Nam là (N – 1, N – 1).

Ví dụ hình dưới đây có 2 bong bóng, bong bóng 1 đang ở ô (1, 2), bong bóng 2 đang ở ô (2, 2):

…*.

..-..

..-..

*….

…..

Ta xem một lần “thổi bong bóng” gồm 2 giá trị: hướng bay và cột/dòng tác động. Đây là bảng mô tả:

Ký tự Hướng Dòng / Cột Tác động
N Bắc Cột thứ c Tất cả các bong bóng trên cột c bay về phía Bắc
E Đông Dòng thứ r Tất cả các bong bóng trên dòng r bay về phía Đông
W Tây Dòng thứ r Tất cả các bong bóng trên dòng r bay về phía Tây
S Nam Cột thứ c Tất cả các bong bóng trên cột c bay về phía Nam

Trong cùng một thời gian ta chỉ được thực hiện một lần thổi duy nhất làm thay đổi hướng của bong bóng. Sau lần thổi đó tất cả các bong bóng sẽ bay một bước theo hướng của nó đang bay. Nếu tọa độ của một bong bóng đang là (i, j) thì sau một đơn vị thời gian nó sẽ ở vị trí mới như sau:

Ký tự Hướng bay Vị trí mới
Không bay (i, j)
N Bắc ( (i – 1 + N) mod N, j)
E Đông (i, (j + 1) mod N)
W Tây (i, (j – 1 + N) mod N)
S Nam ( (i + 1) mod N, j)

Ta có thể thấy một số bong bóng sẽ bay vòng lại từ đầu khi chạm phải các đường biên của lưới.

Khi một bong bóng đến được ô có ký tự ‘*’ thì nó sẽ biến mất (về đến đích rồi mà !!). Nếu có nhiều bong bóng bay về một đích trong cùng một đơn vị thời gian thì chỉ có bong bóng có số thứ tự nhỏ nhất biến mất.

Thời gian bay của một bong bóng được tính từ thời điểm ban đầu đến khi bong bóng này về đến đích. Gọi tổng thời gian bay của tất cả các bong bóng là T.

Bạn hãy thổi bong bóng để cho chúng về đích với T nhỏ nhất có thể.

Input: BALLOONS.INP

  • Dòng đầu tiên ghi số nguyên dương N là kích thước của lưới.
  • N dòng tiếp theo ghi N xâu mô tả lưới, mỗi xâu có độ dài N.

Output:            BALLOONS.OUT

  • Dòng đầu tiên ghi số tự nhiên K là số lần thổi bong bóng.
  • Dòng thứ i trong K dòng tiếp theo ghi một ký tự d và một số tự nhiên c để mô tả lần thổi tại thời điểm thứ i. Với d là ký tự biểu diễn hướng thổi, c là số thứ tự của dòng/cột bị tác động. d và c được ghi cách nhau 1 ký tự trống (space). Nếu không cần thổi bóng tại thời điểm này thì bạn cần ghi ra
    xâu ‘– 0’ (tức là d = ‘–’ và c = 0).

Giới hạn:

  • 1 ≤ N ≤ 100
  • Thời gian: 2 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

BALLOONS.INP BALLOONS.OUT
5

…*.

..-..

..-..

*….

…..

4

E 2

E 1

N 3

S 0

 

Giải thích ví dụ:

Thời điểm Trạng thái Thổi Giải thích
0 …*.

..-..

..-..

*….

…..

1 …*.

..-..

…E.

*….

…..

E 2 Thổi bong bóng ở dòng 2 về phía Đông
2 …*.

…E.

….E

*….

…..

E 1 Thổi bong bóng ở dòng 1 về phía Đông

Bong bóng ở dòng 2 vẫn tiếp tục bay

3 …*.

…..

E….

*….

…..

N 3 Thổi bong bóng ở cột 3 về phía Bắc để đưa bong bóng 1 về đích tại thời điểm 3

Bong bóng ở dòng 2 bay vòng lại cột 0

4 …*.

…..

…..

*….

…..

S 0 Thổi bong bóng ở cột 0 về phía Nam để đưa bong bóng 2 về đích tại thời điểm 4
Tổng thời gian để đưa cả 2 bong bóng về đích là 3 + 4 = 7

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ả

Danh mục

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

NCT Computer

Flickr Photos

Livin' on an Island

A better future...

The Last Hurrah

More Photos

Thống kê

  • 95,498 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: